Codeforces #399 C. Jon Snow and his Favourite Number

Fでしょうもないミスしたけど、A～Eをさっくり解けたこともありレートは増えた。何気にhighest近いのね。
http://codeforces.com/contest/768/problem/C

問題

N要素の数列Aと、整数K,Xが与えられる。
以下の処理をK回行った後、A中の最大値と最小値を求めよ。
Aを昇順にソートし、1,3,5,7,9...番目の要素をXとxorを取った値と差し替える。

解法

愚直に行うとO(NK)かかりTLEする。
ただこの問題は取りうる値の範囲が0～1023とNより小さい。
よってN個の数列を愚直に処理するのではなく、同じ値を複数まとめて処理することでO(K*max(A,X))程度に抑えられる。

int N,K,X;
int from[1050],to[1050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>X;
	FOR(i,N) {
		cin>>x;
		from[x]++;
	}
	
	FOR(j,K) {
		ZERO(to);
		int cnt=0;
		FOR(i,1024) {
			int dodo,donot;
			
			if(from[i]%2==0) {
				dodo=donot=from[i]/2;
			}
			else {
				if(cnt%2==0) {
					dodo=from[i]/2+1;
					donot=from[i]/2;
				}
				else {
					dodo=from[i]/2;
					donot=from[i]/2+1;
				}
			}
			to[i^X] += dodo;
			to[i] += donot;
			cnt+=from[i];
		}
		swap(from,to);
		FOR(i,1024) if(from[i]) _P("%d ",i);
		_P("\n");
	}
	vector<int> V;
	FOR(i,1024) FOR(j,from[i]) V.push_back(i);
	cout<<V.back()<<" "<<V[0]<<endl;
	
	
}

まとめ

これあんまりHackできなかったな。