Submission #416197

#	Time	Username	Problem	Language	Result	Execution time	Memory
416197		InternetPerson10	The Big Prize (IOI17_prize)	C++17	97.62 / 100	56 ms	1864 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

int le[200001], ri[200001];
map<int, int> ge;
vector<int> vec;

int bad, unfound = 0;

vector<int> asksk(int n) {
	if(le[n] >= 0) {
		vector<int> v;
		v.push_back(le[n]);
		v.push_back(ri[n]);
		return v;
	}
	else return ask(n);
}

int rec(int l, int r, int u) {
	// cout << l << ' ' << r << ' ' << u << "\n";
	int k = u;
	if(u == 0) return 0;
	int mid = (l+r)/2;
	int l_r, r_l; l_r = r_l = mid;
	while(l_r > l && u >= 0) {
		auto v = asksk(l_r);
		le[l_r] = v[0]; ri[l_r] = v[1];
		if(le[l_r] + ri[l_r] != bad) u--;
		else {
			u -= rec(l, l_r, le[l_r] - le[l]);
			break;
		}
		l_r--;
	}
	while(r_l < r && u >= 0) {
		auto v = asksk(r_l);
		le[r_l] = v[0]; ri[r_l] = v[1];
		if(le[r_l] + ri[r_l] != bad && r_l != mid) u--;
		else if(le[r_l] + ri[r_l] == bad) {
			u -= rec(r_l, r, k - le[r_l] + le[l]);
			break;
		}
		r_l++;
	}
	return k;
}

int find_best(int n) {
	for(int i = 0; i < n; i++) le[i] = ri[i] = -1;
	int k = 0;
	while(7 * k * k / 8 < n) {
		k++;
		if(k == n) break;
	}
	if(n <= 5000) k = n;
	for(int i = 0; i < k; i++) {
		auto v = asksk(i);
		le[i] = v[0]; ri[i] = v[1];
		if(ge.find(le[i] + ri[i]) == ge.end()) ge[le[i] + ri[i]] = 1;
		else ge[le[i] + ri[i]]++;
	}
	for(auto p : ge) {
		vec.push_back(p.first);
	}
	bad = vec[vec.size() - 1]; // sum of lowest prize
	unfound = bad;
	int st = 0;
	int buffer = 0;
	for(int i = 0; i < k; i++) {
		if(le[i] + ri[i] != bad) {
			buffer++;
		}
		else {
			unfound -= buffer; buffer = 0;
			st = i;
		}
	}
	rec(st, n, unfound);
	for(int i = 0; i < n; i++) {
		if(le[i] + ri[i] == 0) return i;
	}
	rec(0, n, bad);
	for(int i = 0; i < n; i++) {
		if(le[i] + ri[i] == 0) return i;
	}
	return bad+200000;
}
 

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