Submission #1082921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082921		happypotato	The Big Prize (IOI17_prize)	C++17	20 / 100	54 ms	3928 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];
	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> queried;
	int times = 0;
	for (int i = 1; i <= 473; i++) {
		pii ret = Ask(i); queried.insert(i);
		times = max(times, ret.ff + ret.ss);
	}
	vector<int> v(n);
	for (int i = 0; i < n; i++) v[i] = i;

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

	auto findone = [&]() -> int {
		int lb = 0, rb = (int)(v.size()) - 1;
		while (lb < rb) {
			int mid = pickmid(lb, rb);

			pii ret = Ask(v[mid]); queried.insert(v[mid]);
			if (ret.ff + ret.ss < times) return v[mid];
			if (query(0, v[mid] - 1) < ret.ff) rb = mid;
			else lb = mid + 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);
		int pos = 0;
		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:31:6: warning: unused variable 'n' [-Wunused-variable]
   31 |  int n = (int)(bit.size()) - 1;
      |      ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:86:7: warning: unused variable 'pos' [-Wunused-variable]
   86 |   int pos = 0;
      |       ^~~

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