Codeforces #449 Div1 B. Ithea Plays With Chtholly

本番これは完全に見当違いの回答してダメだった。
http://codeforces.com/contest/896/problem/B

問題

N個のスロットがある。
1～Cの数字がランダムで計M回通知されるので、その都度その数字をどこかのスロットに埋めていこう。

MはN*ceil(C/2)以上である場合、最終的に全スロットが昇順になるように数字を埋められるか。

解法

入力値がC/2以下ならスロットの手前から、そうでなければ後ろから、全体が昇順になるのを保つようにして詰めていく。
場合によっては上書きしてもよい。
各スロットが上書きされる回数はC/2回未満のため、M回数字を入力すれば必ずNスロットが埋まる。

int N,M,C;
int P[1010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>C;
	FOR(i,M+1) {
		if(count(P,P+N,0)==0) return;
		
		cin>>x;
		if(x<=C/2) {
			FOR(j,N) if(P[j]==0 || P[j]>x) break;
		}
		else {
			for(j=N-1;j>=0;j--) if(P[j]==0 || P[j]<x) break;
		}
		P[j]=x;
		cout<<j+1<<endl;
	}
}

まとめ

いやこれは感心。