Submission #1082925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082925		happypotato	The Big Prize (IOI17_prize)	C++17	97.68 / 100	70 ms	4364 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
vector<pii> sto;
pii Ask(int x) {
	if (sto[x].ff != -1) return sto[x];
	// cerr << "ASK " << x << endl;
	vector<int> res = ask(x);
	return (sto[x] = make_pair(res[0], res[1]));
}
int brainless(int n) {
	for (int i = 0; i < n; i++) {
		pii ret = Ask(i);
		if (ret.ff + ret.ss == 0) return i;
	}
	throw runtime_error("no answer?");
}
vector<int> bit;
void update(int pos) {
	pos++;
	int n = (int)(bit.size()) - 1;
	while (pos <= n) {
		bit[pos]++;
		pos += (pos & -pos);
	}
}
int pquery(int pos) {
	int n = (int)(bit.size()) - 1;
	int res = 0;
	while (pos >= 1) {
		res += bit[pos];
		pos -= (pos & -pos);
	}
	return res;
}
int query(int l, int r) {
	if (l > r) return 0;
	l++; r++;
	return pquery(r) - pquery(l - 1);
}
int find_best(int n) {
	sto.clear(); sto.resize(n, make_pair(-1, -1));
	bit.clear(); bit.resize(n + 1, 0);
	if (n <= 5000) return brainless(n);
	// only 472 max: 1 4 21 446 []
	set<int> asked;
	int times = 0;
	for (int i = 1; i <= 473; i++) {
		pii ret = Ask(i);
		times = max(times, ret.ff + ret.ss);
	}
	vector<int> v(n);
	for (int i = 0; i < n; i++) v[i] = i;
	for (int res = 1; res <= 473; res++) {
		pii ret = Ask(res);
		if (ret.ff + ret.ss == times) {
			asked.insert(res);
			continue;
		}
		if (ret.ff + ret.ss == 0) return res;
		update(res);
		for (int i = 0; i < (int)(v.size()); i++) {
			if (v[i] == res) {
				v.erase(v.begin() + i);
				break;
			}
		}
	}

	auto pickmid = [&](int lb, int rb) -> int {
		set<int>::iterator it;
		int mid = v[(lb + rb) >> 1];
		it = asked.lower_bound(mid);
		if (it != asked.end() && *it < v[rb]) return *it;
		it = asked.upper_bound(mid);
		if (it != asked.begin() && *(--it) >= v[lb]) return *it;
		return mid;
	};

	auto findpos = [&](int tar) -> int {
		int lb = 0, rb = (int)(v.size()) - 1;
		while (lb < rb) {
			int mid = (lb + rb) >> 1;
			if (v[mid] == tar) return mid;
			if (v[mid] < tar) lb = mid + 1;
			else rb = mid;
		}
		return lb;
	};

	auto findone = [&]() -> int {
		int lb = 0, rb = (int)(v.size()) - 1;
		while (lb < rb) {
			int mid = pickmid(lb, rb);
			int pos = findpos(mid);
			pii ret = Ask(mid);
			if (ret.ff + ret.ss < times) return mid;
			asked.insert(mid);
			if (query(0, mid - 1) < ret.ff) rb = pos - 1;
			else lb = pos + 1;
		}
		return v[lb];
	};

	for (int t = 1; t <= times; t++) {
		int res = findone();
		pii ret = Ask(res);
		if (ret.ff + ret.ss == 0) return res;
		update(res);
		for (int i = 0; i < (int)(v.size()); i++) {
			if (v[i] == res) {
				v.erase(v.begin() + i);
				break;
			}
		}
	}
	// throw runtime_error("oh no");
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int pquery(int)':
prize.cpp:32:6: warning: unused variable 'n' [-Wunused-variable]
   32 |  int n = (int)(bit.size()) - 1;
      |      ^

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