Submission #70805

#	Time	Username	Problem	Language	Result	Execution time	Memory
70805		bnahmad15	The Big Prize (IOI17_prize)	C++17	90 / 100	140 ms	5740 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200000,buk = 480;

vector<int> res[N];
int n,mx = -1;

vector<int> ASK(int p){
	if(res[p].size())
		return res[p];
	return res[p] = ask(p);
}

int FIND(int l,int r){
	if(l == r){
		vector<int> tmp = ASK(l);
		if(tmp[0] == 0 && tmp[1] == 0)
			return l;
		return -1;
	}
	vector<int> tmp1,tmp2;
	tmp1 = ASK(l);
	tmp2 = ASK(r);
	if(tmp1[0] == tmp1[1] && tmp1[0] == 0)
		return l;
	if(tmp2[0] == tmp2[1] && tmp2[0] == 0)
		return r;
	int md = (l+r)/2;
	if(tmp1 == tmp2)
		return -1;
	int t = FIND(l,md);
	int t2 = FIND(md+1,r);
	if(t != -1)
		return t;
	return t2;
}


int find_best(int _N) {
	n = _N;
	return FIND(0,n-1);
}

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