Looksery Cup 2015 G. Happy Line

これほんと簡単だしなんで本番解かなかったんだ…

問題

Problem - 549G - Codeforces

解法

人の移動を入れ替えで考えるとかなりめんどくさいので問題を単純なものに置き換えます。

よく考えると誰と交換したかにかかわらず,前にa人分抜かせば所持金a円減るしa人に抜かされれば所持金はa円増えます。よって,これは単純なソートの問題に置き換えられると思われます。

実際,仮に最初は皆0番目にいるとすると,i番目の人の最初の所持金はa[i]+i円であると考えることが出来ます。これについてソートしたとき,
仮にa[i] = a[i+1]のようなことが成り立ってしまったとすると,どちらかが列の前に並んだ時もう一方の人がupsetするので:( です。
そのようなことがなければ,所持金が少ない人から順に列の後ろに並んでおけば皆Happyになります。

ll a[200010];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] += i;
    }
    sort(a, a+n);
    for (int i = 0; i < n-1; i++) {
        if (a[i] == a[i+1]) {
            cout << ":(" << endl;
            return 0;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i]-i << " ";
    }
    cout << endl;
    return 0;
}