Submission #1048279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048279		Gromp15	The Big Prize (IOI17_prize)	C++17	20 / 100	35 ms	4952 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 = 10;

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);
		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;
	}
	int ANS = -1;
	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;
		/*
		cerr << "CUR ML MR WANT " << ml << " " << mr << " " << want << '\n';
		for (int x : ask) cerr << x << " ";
		cerr << '\n';
		*/
		while (tl <= tr) {
			int mid = (tl + tr) / 2;
			auto res = _ask(ask[mid]);
			//cerr << "ASK " << ask[mid] << " " << res[0] << " " << res[1] << endl;
			if (res[0] + res[1] == 0) {
				ANS = ask[mid]; return;
			}
			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;
			}
		}
		/*
		cerr << "DONE " << ans << endl;
		for (int x : ask) cerr << x << " ";
		cerr << '\n';
		*/
		if (!~ans) return;
		auto res = _ask(ask[ans]);
		if (res[0] + res[1] == 0) {
			ANS = ask[ans]; return;
		}
		if (ans - 2 >= 0 && !~ANS) {
			s(s, vector<int>(ask.begin(), ask.begin() + ans - 1), ml, want - 1);
		}
		if (ans + 1 < sz(ask) && !~ANS) {
			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);
	return ANS;
}

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