Submission #103078

#	Time	Username	Problem	Language	Result	Execution time	Memory
103078		minson123	The Big Prize (IOI17_prize)	C++11	20 / 100	82 ms	512 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int find_best(int n) {
	int cur=n-1;
	vector<int> q,nq;
	q=ask(cur);
	while(q[0]!=0 || q[1]!=0){
		int sp=-1;
		for(int k=0;cur-(1<<k)>=0;k++){
			nq=ask(cur-(1<<k));
			if(nq[0]!=q[0] || nq[1]!=q[1]) break;
			sp=k;
		}
		if(sp==-1) cur--,q=nq;
		else{
			int l=max(0,cur-(1<<(sp+1))),r=cur-(1<<sp);
			while(r-l>1){
				int mid=(l+r)>>1;
				nq=ask(mid);
				if(nq[0]!=q[0] || nq[1]!=q[1]) l=mid;
				else r=mid;
			}
			cur=l;
			q=ask(cur);
		}
	}
	return cur;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80