Submission #410063

#	Time	Username	Problem	Language	Result	Execution time	Memory
410063		dreezy	The Big Prize (IOI17_prize)	C++17	0 / 100	1 ms	284 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

/*********************************************************************************************************************/

int find_best(int n) {
	int left =0,middle = n/2,  right = n-1;
	
	int numleft = 0, numright = 0;//left and right from range
	int curtotal = INT_MAX;
	int cnt = 0;
	while(true){
		int numl, numr; //left and right from query
		

		
		vector<int> res = ask(middle);
		numl = res[0], numr = res[1];
		
		if(numl  == 0 && numr ==  0)
			return middle;
			
		if(numl + numr < curtotal){
			numleft = 0, numright = 0;
			curtotal = numl + numr;
			left = 0, middle = n/2, right = n-1;
		//	cout << "NEW TOTAL: "<<curtotal<<endl;
		}
		
		numl -= numleft;
		numr -= numright;
		
		//cout <<"("<< left <<", "<<middle<<", "<<right<<")";
		//cout << ":\t"<<numleft <<", "<<numright<<", "<<numl<<", "<<numr;
		
		
		int lhole = (middle - left) - numl +1;
		int rhole = (right - middle) - numr +1;
		
		//cout << ";\t"<<lhole<<", "<<rhole<<endl;
		if( (lhole< rhole && numl  > 0) || numr == 0){
			right = middle -1;
			middle = middle - lhole;
			numright += numr;
		}
		else{
			left = middle + 1;
			middle = middle + rhole;
			numleft +=numl;
		}
		cnt++;
		if(cnt == 7) break;
		
	}
	return 0;
}


/*********************************************************************************************************************/

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