本番あと15秒で間に合わなかった…。
http://codeforces.com/contest/420/problem/D
問題
初期状態で1~N番の番号が付いたN個のカップが1列に並んでいるが、その並び順は不明である。
これらのカップをM回シャッフルした。
各シャッフルではY[i]番目にあるカップを先頭に持ってくるという処理を行った。
その際、動かしたカップはX[i]番の番号がついていた。
初期状態であり得るカップの状態のうち、辞書順最小のものを求めよ。
解法
N,M <= 10^6なので、配列を1個ずつずらしたりすると間に合わない。
ここでは平方分割し、1000個のvectorに分けて管理した。
後は各vectorに初期状態の位置を書いた番号を入れて、シャッフル処理を再現すればよい。
その都度シャッフル対象のカップに番号X[i]を割り当て、1つのカップに2つの番号が割当たったり、2つのカップに同じ番号が割当たらないか調べていけばよい。
M回シャッフルして登場しない番号は、先頭から若い順に割り当てれば辞書順最小になる。
平方分割によりO(M√N)で処理可能。
int N,M; int num[1000008]; int used[1000008]; vector<int> V[3000]; void solve() { int f,i,j,k,l,x,y; cin>>N>>M; FOR(i,N) V[i/1000].push_back(i); FOR(i,M) { cin>>x>>y; FOR(j,3000) { if(y<=V[j].size()) break; y-=V[j].size(); } y--; k=V[j][y]; if(num[k]!=0 && num[k]!=x) return _P("-1\n"); if(num[k]==0 && used[x]) return _P("-1\n"); num[k]=x; used[x]=1; V[j].erase(V[j].begin()+y); if(V[0].size()>1000) { for(j=2998;j>=0;j--) swap(V[j+1],V[j]); V[0].clear(); V[0].push_back(k); } else { V[0].resize(V[0].size()+1); for(j=V[0].size()-1;j>=1;j--) V[0][j]=V[0][j-1]; V[0][0]=k; } } x=1; FOR(i,N) { while(used[x]) x++; if(num[i]==0) num[i]=x++; _P("%d ",num[i]); } _P("\n"); }
まとめ
D問題とはいえ1500ptなので自力で解けるレベルだった。