これは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