Submission #1195781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195781		nikulid	The Big Prize (IOI17_prize)	C++20	20 / 100	23 ms	412 KiB

prize

#include "prize.h"
#include <vector>
using namespace std;

/*
	Lemma: 
	subtask 1 is binary search (eazy peazy lemon squeezy)
*/

int find_best(int n) {
	vector<int> res;
	res = ask(0);
	if(res[0] + res[1] == 0){
		return 0;
	}
	res = ask(n-1);
	if(res[0] + res[1] == 0){
		return n-1;
	}
	
	int l=0, r=n-1, m; // these are definitely outside the thingy majiggy whatever ykwim
	
	while(true){
		m = (l+r)/2;
		res = ask(m);
		if(res[0]+res[1] == 0)return m;
		if(res[0])r=m;
		else l=m;
	}


	/*
	for(int i = 0; i < n; i++) {
		res = ask(i);
		if(res[0] + res[1] == 0)
			return i;
	}
	*/
	return 0;
}

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