Submission #1199361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199361		didododi	The Big Prize (IOI17_prize)	C++20	90 / 100	61 ms	9884 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;
set<int> possible;
vi askeys;
vi myask(int p) {
	if (cache.count(p)) return cache[p];
	asked++;
	askeys.push_back(p);
	cache[p] = ask(p);
	if (cache[p][0]+cache[p][1]) possible.erase(p);
	return cache[p];
}

int find_best(int n) {
	int mx = 0;
	srand(time(0));
	int select;
	for (int i = 0;i<500 && i<n;i++) {
		vi v = myask(i);
		if (v[0]+v[1] == 0) return i;
		if (v[0]+v[1] > mx) {
			mx = v[0]+v[1];
			select = i;
		}
	}
	int pr = select;
	for (int i = select+1;i<n;i++) possible.insert(i);
	for (auto it : askeys) {
		vi vvv = myask(it);
		if (vvv[0]+vvv[1]) possible.erase(it);
		else return it;
	}
	while (possible.size()+asked > 3000) {
		if (pr >= n-1) break;
		vector<int> q = myask(pr);
		vi prv = myask(pr+1);
		if (prv[0]+prv[1] == 0) return pr+1;
		if ((prv[0]+prv[1]) != (q[0]+q[1])) {
			int ptr = pr+1;
			possible.erase(ptr);
			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 = min(n-1,pr+500);
		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;
	}
	vi v(all(possible));
	shuffle(all(v),mt19937_64(0));
	for (auto it : v) {
		vi vv = myask(it);
		if (vv[0] + vv[1] == 0) return it;
	}
	assert(0);
}

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