Codeforces #348 Div1. B. Little Artem and Dance

色々グダついたけど割といい順位で赤色復活。
http://codeforces.com/contest/668/problem/B

問題

1～N番の男女がそれぞれ手をつないで順に円周上に並んでいる。
Q個のクエリに対し、それぞれ以下の手順に則り男性側が移動してペアとなる女性を変更する。

• 時計回りにx人分移動する。
• 2k+1番の女性と手をつないでいる男性と2k+2番の女性と手をつないでいる男性の位置を交換する。

最終的に各女性と手をつないでいる男性は何番の男性か答えよ。

解法

初期状態で2つ隣にいる人は、どちらのクエリにおいてもずっと2つ隣という相対的な位置関係は変わらない。
そこで、クエリに対し1,2番の男性の移動だけ愚直にシミュレートすれば、あとはクエリ完了後に２つ隣の人を1,2番を基準に順に配置することができる。
入出力が多いのでcin/coutでTLEしないよう注意。

int N,Q;
int R[1010100];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int p0=0;
	int p1=1;
	scanf("%d%d",&N,&Q);
	while(Q--) {
		scanf("%d",&x);
		if(x==1) {
			scanf("%d",&y);
			p0+=y+N;
			while(p0>=N) p0-=N;
			p1+=y+N;
			while(p1>=N) p1-=N;
		}
		else {
			p0^=1;
			p1^=1;
		}
	}
	
	FOR(i,N/2) {
		R[p0] = 1+i*2;
		R[p1] = 2+i*2;
		p0+=2;
		p1+=2;
		while(p0>=N) p0-=N;
		while(p1>=N) p1-=N;
	}
	
	FOR(i,N) _P("%d%s",R[i],(i==N-1)?"\n":" ");
	
}

まとめ

cin/coutの2TLEが無ければ4位だったのに…。