Good Bye 2013 : C. New Year Ratings Change

CF222が調子よかったので、Good Bye 2013にも参加。
ABCはさっさと解答、Cで8Hackも成功したものの、Dのツメが甘かった。
アプローチはよかったもののコーナーケース検討が不十分でDが通せず。
結果レートは微減。何とか年越し2000はキープしたけどね。
http://codeforces.com/contest/379/problem/C

問題

N人の現在のレートB[i]が与えられる。
各人のレートを少しずつ増やし、全員のレートがユニークになるようにしたい。
増分を最小にする場合、増加後のレートを示せ。

解法

初期状態のレートでN人を昇順ソートし、各人のレートをmax(初期レート, 1つ手前の人のレート+1)にすればよい。

int N;
ll A[300001];
pair<ll,int> P[3000001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		P[i].first=A[i];
		P[i].second=i;
	}
	
	ll a=0;
	sort(P,P+N);
	for(i=1;i<N;i++) A[P[i].second] = max(A[P[i].second], A[P[i-1].second]+1);
	FOR(i,N) _P("%lld ",A[i]);
	_P("\n");
	
}

まとめ

「今まで利用したレートと重複するならインクリメントする」というコードを書いた人が多数いたが、これは重複判定にmapやsetを使うとO(log N)かかるうえ、インクリメント回数が１人当たりO(N)かかるので全体でO(N^2 logN)かかるため、Hackし放題だった。