AIM Tech Round 4 : B. Interactive LowerBound

アプローチはあっていたがしょうもないミスで落とした。
http://codeforces.com/contest/843/problem/B

問題

異なる数値で構成されたN要素の数列Aがある。
Aのうち最小値となる要素A[s]が与えられる。

さて、この数列に対し、以下のクエリを最大2000回実行できる。

• 要素番号iを指定すると、その値A[i]と、A中で次に大きな値を持つ要素jを返す。

このクエリを用いて、A中でX以上の値を持つ最小の要素を求めよ。

解法

最小要素A[s]がX以上であればA[s]が解。

以後そうでないケースを考える。
解法としては乱拓となる。
まず適当に1000個の要素の値を求めよう。
うち、A[i]がX以下となる最大のiを求めよう。
後はそこから1000個次に大きい要素を順にたどっていき、X以上の数値が出てきたらその要素を答える。

int N,S,X;
int V[50505],nex[50505];
int did=0;
int mi=1<<30;


void answer(int v) {
	cout<<"! "<<v<<endl;
	exit(0);
}

void ask(int id) {
	cout<<"? "<<id<<endl;
	fflush(stdout);
	cin>>V[id]>>nex[id];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>X;
	MINUS(V);
	
	srand(time(NULL));
	
	vector<int> A;
	FOR(i,N) if(i+1!=S) A.push_back(i+1);
	random_shuffle(ALL(A));
	A.resize(min((int)A.size(),999));
	A.push_back(S);
	
	vector<pair<int,int>> cand;
	FORR(r,A) {
		ask(r);
		cand.push_back({V[r],r});
	}
	sort(ALL(cand));
	for(j=cand.size()-1;j>=0;j--) {
		if(cand[j].first==X) answer(cand[j].first);
		if(cand[j].first<X) break;
	}
	if(j==-1) answer(V[S]);
	x=cand[j].second;
	
	while(x!=-1) {
		ask(x);
		if(V[x]>=X) answer(V[x]);
		x=nex[x];
	}
	answer(-1);
}

まとめ

おかげでレートを大幅に失った。