Codeforces Round #298 (Div. 2) D. Handshakes

Codeforces Round #298 (Div. 2)に参加しました。結果はABCDが通ってくれて,div2とはいえ20位という好順位をとれ結構満足でした。

問題:Problem - 534D - Codeforces

解法:戦略としては,たくさんの人と握手したと主張する人がなるべく矛盾しないようにするため,多く握手した人を優先していきます。
それがわかれば後は実装の問題で,それは以下のようにやりました。
・main関数のcurが今握手できる人の人数を管理する。もしcurの人数だけ握手したと主張する人がいなければ実現不可能なのでImpossibleを返す
・上のcurの人数と握手した人がいたかどうかは,GとNOWで管理する。Gはcurだけ握手したと主張する人のリストで,NOWは今それの何人目まで進んだかを表す
・たくさんの人と握手した人を優先するため,毎回「今現在でのまだ処理していなくて,『握手した人の人数が一番多い人』が何人と握手するつもりなのか」を計算する(getっていう関数)
・このgetっていう関数はbinary indexed treeでの二分探索でmax値を返す
BITは普段使ってるのが1-basedだったので0-basedにするのにやや困惑しましたが調べたら出てきてくれたので助かりました->http://hos.ac/slides/20140319_bit.pdf

以下ソースコード

const int MAXN = 222222;
vector<int> G[MAXN];
int NOW[MAXN];
int a[MAXN];

int bit[MAXN];
int n;

int sum(int i) {
    int ret = 0;
    for (int x = i; x >= 0; x = (x & (x+1))-1) {
        ret += bit[x];
    }
    return ret;
}

void add(int i, int x) {
    for (int a = i; a < n; a |= a+1) {
        bit[a] += x;
    }
}

int get(int num) {
    int low = -1, high = n+1;
    while (high - low > 1) {
        int med = (high+low)/2;
        if (sum(med) >= n-num) high = med;
        else low = med;
    }
    return high;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        G[a[i]].push_back(i);
        add(a[i], 1);
    }
    vector<int> ans;
    int cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur < 0 || (int)G[cur].size() <= NOW[cur]) {
            cout << "Impossible" << endl;
            return 0;
        }
        ans.push_back(G[cur][NOW[cur]++]);
        add(cur, -1);
        cur++;
        int ma = get(i+1);
        if (cur > ma) {
            cur = cur - (cur-ma)/3*3;
            if (cur > ma) cur -= 3;
        }
    }
    if (ans.size() == n) {
        cout << "Possible" << endl;
        for (int i = 0; i < n; i++) {
            cout << ans[i] ;
            if (i != n-1) cout << " ";
        }
        cout << endl;
    } else cout << "Impossible" << endl;
    return 0;
}