제출 #410064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410064		dreezy	커다란 상품 (IOI17_prize)	C++17	0 / 100	95 ms	280 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