Submission #1048253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048253		Gromp15	The Big Prize (IOI17_prize)	C++17	0 / 100	5 ms	2904 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;

const int N = 500;

int find_best(int n) {
	map<int, vector<int>> mp;
	auto _ask = [&](int x) {
		if (mp.count(x)) return mp[x];
		auto res = ask(x);
		if (res[0] + res[1] == 0) return res;
		return mp[x] = res;
	};
	int mx = 0;
	for (int i = 0; i < min(n, N); i++) {
		auto res = _ask(i);
		mx = max(mx, res[0] + res[1]);
		if (res[0] + res[1] == 0) return i;
	}
	auto solve = [&](auto&& s, vector<int> ask, int ml, int mr) -> void {
		if (ml > mr || ask.empty()) return;
		int want = (ml + mr) / 2;
		int tl = 0, tr = sz(ask) - 1, ans = -1;
		while (tl <= tr) {
			int mid = (tl + tr) / 2;
			auto res = _ask(mid);
			if (res[0] + res[1] < mx) {
				ask.erase(ask.begin() + mid);
				tr--; continue;
			}
			else {
				if (res[0] >= want) ans = mid, tr = mid - 1;
				else tl = mid + 1;
			}
		}
		if (!~ans) return;
		if (ans - 2 >= 0) {
			s(s, vector<int>(ask.begin(), ask.begin() + ans - 1), ml, want - 1);
		}
		if (ans + 1 < sz(ask)) {
			s(s, vector<int>(ask.begin() + ans + 1, ask.end()), want + 1, mr);
		}
	};
	vector<int> idx(n);
	iota(all(idx), 0);
	solve(solve, idx, 1, mx);
	assert(0);
	return -1;
}

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