Codeforces #238 Div1 B. Toy Sum

これはAよりも簡単で本番10分かかってない…。Aより先にこちらやればよかった。
http://codeforces.com/contest/406/problem/B

問題

1～10^6までの数字が1個ずつあり、そのうちN個を含む部分集合Xが与えられる。
1～10^6までの数字のうちXに含まれない要素をいくつか含む部分集合Yのうち、

となるYを答えよ。

解法

あるpがXに含まれる場合、(1000001-p)をYに含まれば、p-1=(1000000-(1000001-p))なので両辺の値が一致する。
ただし、pも(1000001-p)もXに含まれている場合、別のq・(1000001-q)のペアのうちどちらもXに含まれていないようなものをYに含めればよい。
この時(p-1)+*1なので両辺の値が一致する。

N<=500000のため、そのようなqは必ず見つかる。

int N;
int M[1000002];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	ll tot=0;
	FOR(i,N) {
		cin>>x;
		M[x]=1;
	}
	j=0;
	for(i=1;i<=500000;i++) {
		if(M[i]==1 && M[1000001-i]==0) M[1000001-i]=2;
		else if(M[i]==0 && M[1000001-i]==1) M[i]=2;
		else if(M[i]==1 && M[1000001-i]==1) j++;
	}
	for(i=1;i<=500000;i++) if(j&&M[i]==0&&M[1000001-i]==0) j--,M[i]=M[1000001-i]=2;
	_P("%d\n",count(M,M+1000002,2));
	for(i=1;i<=1000000;i++) if(M[i]==2) _P("%d ",i);
	_P("\n");
	
}

まとめ

これは本番すんなり思いつけて良かった。

*1:1000001-p)-1)=999999=(1000000-q)+(1000000-(1000001-q