Submission #1198948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198948		dosts	The Big Prize (IOI17_prize)	C++20	90 / 100	70 ms	9980 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;

const int inf = 2e9;
map<int,vi> cache;
int asked = 0;
vi myask(int p) {
	if (cache.count(p)) return cache[p];
	asked++;
	return cache[p] = ask(p);
}

int find_best(int n) {
	set<int> possible;
	int mx = 0;
	srand(time(0));
	int select;
	for (int i = 0;i<1000 && i<n;i++) {
		vi v = myask(i);
		if (v[0]+v[1] > mx) {
			mx = v[0]+v[1];
			select = i;
		}
	}
	for (int i=0;i<n;i++) possible.insert(i);
	int pl = select,pr = select;
	while (possible.size() >= 10000-asked) {
		if (pl <= 0) break;
		vector<int> q = myask(pl);
		vi prv = myask(pl-1);
		if ((prv[0]+prv[1]) != (q[0]+q[1])) {
			int ptr = pl-1;
			while (ptr > 0) {
				prv = myask(ptr-1);
				if (prv[0]+prv[1] == 0) return ptr-1;
				if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr--;
				else break;
			}
			pl = ptr-1;
			continue;
		}
		int l = 0;
		int r = pl-1;
		while (l<=r) {
			int m = (l+r) >> 1;
			vi vv = myask(m);
			if (vv[0]+vv[1] == 0) return m;
			if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[1] > q[1])) l = m+1;
			else r = m-1;
		}
		for (int j = pl;j >= l;j--) possible.erase(j);
		pl = l;
	}
	while (possible.size() >= 10000-asked) {
		if (pr >= n-1) break;
		vector<int> q = myask(pr);
		vi prv = myask(pr+1);
		if ((prv[0]+prv[1]) != (q[0]+q[1])) {
			int ptr = pr+1;
			while (ptr < n-1) {
				prv = myask(ptr+1);
				if (prv[0]+prv[1] == 0) return ptr-1;
				if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr++;
				else break;
			}
			pr = ptr+1;
			continue;
		}
		int l = pr+1;
		int r = n-1;
		while (l<=r) {
			int m = (l+r) >> 1;
			vi vv = myask(m);
			if (vv[0]+vv[1] == 0) return m;
			if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[0] > q[0])) r = m-1;
			else l = m+1;
		}
		for (int j = pr;j <= r;j++) possible.erase(j);
		pr = r;
	}
	if (possible.size()+asked > 10000) assert(0);
	for (auto it : possible) {
		vi vv = myask(it);
		if (vv[0] + vv[1] == 0) return it;
	}
	assert(0);
}

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