Submission #283935

#	Time	Username	Problem	Language	Result	Execution time	Memory
283935		emanIaicepsa	The Big Prize (IOI17_prize)	C++14	98.86 / 100	69 ms	6008 KiB

prize

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

vi ans[200005];
int asked[200005];
set<int> s;
vector<int> Ask(int x){
	if(!asked[x]) ans[x] = ask(x), asked[x] = 1, s.insert(x);
	return ans[x];
}

int find_best(int n) {
	srand(time(0));
	if(n <= 5000){
		for(int i=0;i<n;i++){
			vi tmp = Ask(i);
			if(tmp[0] + tmp[1] == 0) return i;
		}
	}
	int mx = 0;

	for(int i=0;i<10;i++){
		int x = rand() % n;
		vi tmp = Ask(x);
		mx = max(mx, tmp[0] + tmp[1]);
	}

	int l = 0;
	vi cur;
	while(1){
		cur = Ask(l);
		if(cur[0] == 0 && cur[1] == 0) return l;
		if(cur[0] + cur[1] < mx) l++;
		else break;
	}
	while(l < n){
		auto iter = s.begin();
		while(!s.empty() && (*iter < l || Ask(*iter) == Ask(l))) iter = s.erase(iter);
		int L = l, R = s.empty() ? n-1 : *s.begin();
		while(L < R){
			int m = (L+R+1)/2;
			vi tmp = Ask(m);
			if(tmp[0] + tmp[1] == 0) return m;
			if(tmp[0] != cur[0] || tmp[1] != cur[1]) R = m - 1;
			else L = m;
		}
		if(L == n-1) break;
		l = L+1;
		while(1){
			if(l == n) break;
			cur = Ask(l);
			if(cur[0] == 0 && cur[1] == 0) return l;
			if(cur[0] + cur[1] < mx) l++;
			else break;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:31:5: warning: control reaches end of non-void function [-Wreturn-type]
   31 |  vi cur;
      |     ^~~

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