is this tournament correct? [Kodamanと愉快な仲間たち I]

https://www.hackerrank.com/contests/kodamanwithothers/challenges/i-is-this-tournament-correct

解説

https://www.hackerrank.com/contests/kodamanwithothers/challenges/i-is-this-tournament-correct/submissions/code/1316477775

クエリ問題になっている。 O(N)くらいで解くのが想定なんだろう。

初戦を考えると、初戦は勝数が1と2以上となるのは明らか。 というかどんな場面でも1と2以上となるはず。 最後だけ例外的に1と1になるはず。 2以上の数というのは制約がゆるめなので、なるべく1を作りながら構築していきたい気がする。 この貪欲はできそうな気がする。 ちなみに、毎回1人敗退していくので、試合の回数はN-1で固定。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
#define ngout printf("invalid\n")
void solve() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    vector<pair<int,int>> v;
    rep(i, 0, N) v.push_back({A[i], i});
    sort(all(v));

    int R = 0;
    vector<pair<int, int>> ans;
    rep(L, 0, N - 2)
    {
        while(R <= L) R++;
        while(R < N and v[R].first == 1)
            R++;
        
        if (N <= R) {
            ngout;
            return;
        }

        v[L].first--;
        v[R].first--;

        ans.push_back({v[L].second, v[R].second});
    }
    vector<int> rest;
    rep(i, 0, N) {
        if(1 < v[i].first) {
            ngout;
            return;
        }
        if(1 == v[i].first) {
            rest.push_back(v[i].second);
        }
    }

    if(rest.size() != 2) {
        ngout;
        return;
    }
    ans.push_back({rest[0], rest[1]});

    int n = ans.size();
    printf("%d\n", n);
    fore(p, ans) printf("%d %d\n", p.second + 1, p.first + 1);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}