Codeforces #700 Div1 : A. Searching Local Minimum

ついに#700に到達。すでに現行より100回分以上ビハインド。
https://codeforces.com/contest/1479/problem/A

問題

整数列A[1...N]を、1～NのPermutationとする。
Aのうち最大100個までの要素を取得できる場合、極小である(A[i-1]＞A[i]かつA[i]＜A[i+1])添え字iを1つ求めよ。
なお、A[0]とA[N+1]は∞とみなす。

解法

区間[L,R]に対し、A[(L+1)...(R-1)]の範囲に、A[L]＞A[i]かつA[i]＜A[R]となるiが最低1個存在する状態をキープしながら、L,Rの範囲を狭めていこう。

区間を4等分し、各区間の境界の添え字をL,M1,M2,M3,Rとする。
それぞれA[L]、A[M1]、A[M2]、A[M3]、A[R]を求めよう。
初期状態では、L=0、R=N+1とすると、A[M1]、A[M2]、A[M3]のうち少なくとも1個はA[L]やA[R]より小さい。

以下のように状態遷移すれば、「A[L]＞A[i]かつA[i]＜A[R]となるiが最低1個存在する状態をキープしながら、L,Rの範囲を狭め」ることができる。

• A[M1]が最小→RをM2に移動する。
• A[M2]が最小→LをM1に、RをM3に移動する。
• A[M3]が最小→LをM2に移動する。

int N;
int A[1010101];

int get(int a) {
	if(A[a]==0) {
		cout<<"? "<<a<<endl;
		cin>>A[a];
	}
	return A[a];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	A[0]=A[N+1]=1<<20;
	
	if(N<=100) {
		for(i=1;i<=N;i++) {
			get(i);
		}
		for(i=1;i<=N;i++) {
			if(A[i]<A[i-1]&&A[i]<A[i+1]) {
				cout<<"! "<<i<<endl;
				return;
			}
		}
	}
	else {
		int L=0,R=N+1;
		int M=(L+R)/2;
		
		while(R-L>=5) {
			int M=(L+R)/2;
			int L1=(L+M)/2;
			int R1=(R+M)/2;
			int LV=get(L);
			int RV=get(R);
			int MV=get(M);
			int L1V=get(L1);
			int R1V=get(R1);
			
			if(LV>L1V&&L1V<MV) {
				R=M;
			}
			else if(L1V>MV&&MV<R1V) {
				L=L1;
				R=R1;
			}
			else {
				L=M;
			}
		}
		for(i=L;i<=R;i++) get(i);
		for(i=L+1;i<R;i++) {
			if(A[i]<A[i-1]&&A[i]<A[i+1]) {
				cout<<"! "<<i<<endl;
				return;
			}
		}
		
	}
	
}

まとめ

Aにしてはちょっと手間取った。