AtCoder Regular Contest 086 D - Non-decreasing

問題ページ
D - Non-decreasing

考えたこと

• 各時点で数列の最大値と最小値をもっておく。a[i-1]とa[i]で減少してたら条件を満たすまでa[i-1]に最小値を足す or a[i]に最大値を足すでよさそうな方をするを繰り返す。
  → a[i]に最大値を足した後で最小値を足して条件を満たさない意味不明ムーブをする入力がある
• 正の値だけを足すか負の値だけを足すかでできるのでは？
  → 無理
• 何もわからないので上2つを組み合わせる
  → 落ちる(はい)

------解説を見た------
符号を合わせれば累積和でできるのそれはそう。解説見たら一瞬をやめたいし構築ゲーをいい加減解けるようになりたい。あとa_xにa_yを加算すると思って謎のWAを出していた。

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[55], b[55];
int n;

bool check() {
  FOR(i, 1, n) {
    if(a[i-1] > a[i]) return true;
  }
  return false;
}

signed main(void)
{
  cin >> n;
  REP(i, n) cin >> a[i];

  int maidx = max_element(a, a+n) - a, miidx = min_element(a, a+n) - a;
  int ma = a[maidx], mi = a[miidx];

  vector<PII> v;

  if(abs(ma) > abs(mi)) {
    REP(i, n) {
      if(a[i] < 0) {
        a[i] += ma;
        v.PB({maidx, i});
      }
    }
    FOR(i, 1, n) {
      a[i] += a[i-1];
      v.PB({i-1, i});
    }
  } else {
    REP(i, n) {
      if(a[i] > 0) {
        a[i] += mi;
        v.PB({miidx, i});
      }
    }
    for(int i=n-1; i>=1; --i) {
      a[i-1] += a[i];
      v.PB({i, i-1});
    }
  }

  if(v.size() > 2*n) assert(false);
  cout << v.size() << endl;
  REP(i, v.size()) {
    cout << v[i].first+1 << " " << v[i].second+1 << endl;
  }

  return 0;
}