Codeforces #569 Div1 A. Valeriy and Deque

これはまぁまぁ調子いい回だったね。
https://codeforces.com/contest/1179/problem/A

問題

　
N要素の整数列であるdequeが与えられる。
以下の処理を行うことを考える。

• 先頭2要素を抜き出し、小さい方を先頭、大きい方を末尾に入れる。

M回目の処理で抜き出される2要素を求めよ。

解法

最小値が一旦先頭に来ると、あとは先頭は固定で残りの要素がdeque内を回転する。
よって最初N回程度は愚直にシミュレートし、あとは同じループを繰り返すと考えよう。

int N,Q;
deque<int> A;
pair<int,int> ret[303030];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>x;
		A.push_back(x);
	}
	
	for(i=1;i<=300000;i++) {
		x=A[0];
		y=A[1];
		A.pop_front();
		A.pop_front();
		ret[i]={x,y};
		A.push_front(max(x,y));
		A.push_back(min(x,y));
	}
	
	FOR(i,Q) {
		ll v;
		cin>>v;
		if(v<=300000) {
			cout<<ret[v].first<<" "<<ret[v].second<<endl;
		}
		else {
			v-=300001;
			v%=(N-1);
			cout<<A[0]<<" "<<A[1+v]<<endl;
		}
	}
	
	
}

まとめ

この回A問題解いた人数多いな。