Codeforces #223 Div1. A. Sereja and Prefixes

年明け１発目のCodeforcesは、Aしか解けないわそれもWA繰り返すわで散々でした。
今回はAの割に実装が重く、みんな速度が遅め。
http://codeforces.com/contest/380/problem/A

問題

初期状態として空の数列がある。
そこに以下の２通りのコマンド群をM個用いて数列を作る。

1. 数列の末尾にxを追加する。
2. 数列の先頭l個をc回繰り返したものを数列の末尾に追加する。

その後N個indexが渡されるので、数列中の対応する要素を答えよ。

解法

２つ目のコマンドではlの上限は10^5である。
そこで、数列要素が10^5に到達するまでは律儀に数列を作る。
以降、１つ目のコマンドが実行された場所とその値はmapで覚えておく。
２つ目のコマンドに対しては、そのコマンドにより追加された列の先頭位置と周期(l)、長さ(l*c)を覚えておく。

以後N個のindexに対し：

• 10^5以下なら作成した数列の値を返す
• mapに要素があれば、そのindexは１つ目のコマンドで作られたものなのでそれを返す
• mapに要素がなければ、そのindexは２つ目のコマンドで作られたものなので、対応する先頭位置を検索し、周期から追加元のindexを求めてそれを返す

ll M,L,N;
int MM[200000];
map<ll,int> H;
map<ll,ll> R;

void solve() {
	int f,i,j,k,x,y;
	
	cin>>M;
	
	vector<ll> V;
	ll l=0,xx;
	
	FOR(i,M) {
		cin>>x;
		if(x==1) {
			cin>>H[l];
			V.push_back(l);
			R[l]=1;
			if(l<200000) MM[l]=H[l];
			l++;
		}
		else {
			cin>>x>>y;
			while(y) {
				if(l+x<200000) {
					FOR(f,x) {
						H[l]=MM[l]=MM[f];
						R[l]=1;
						V.push_back(l);
						l++;
					}
					y--;
				}
				else {
					V.push_back(l);
					R[l]=x;
					l+=x*(ll)y;
					y=0;
				}
			}
		}
	}
	
	cin>>N;
	FOR(i,N) {
		cin>>xx;
		xx--;
		if(H.find(xx)==H.end()) {
			int y=lower_bound(V.begin(),V.end(),xx)-V.begin()-1;
			xx=(xx-V[y])%R[V[y]];
			_P("%d ",MM[xx]);
		}
		else {
			_P("%d ",H[xx]);
		}
	}
	_P("\n");
}

まとめ

今回の惨敗っぷりはひどかった。