Submission #426007

#	Time	Username	Problem	Language	Result	Execution time	Memory
426007		Tangent	The Big Prize (IOI17_prize)	C++17	20 / 100	149 ms	1348 KiB

prize

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

set<int> seen_inds;
map<int, pii> memo;
pii ask2(int i) {
	if (seen_inds.find(i) == seen_inds.end()) {
		seen_inds.emplace(i);
		auto res = ask(i);
		memo[i] = {res[0], res[1]};
	}
	return memo[i];
}

int find_best(int n) {
	if (n <= 5000) {
		rep(i, n) {
			auto res = ask2(i);
			if (!res.first && !res.second) {
				return i;
			}
		}
	}
	int a = n / 2, b = rand() % n, c = rand() % n;
	while (b == a) {
		b = rand() % n;
	}
	while (c == a || c == b) {
		c = rand() % n;
	}
	auto res1 = ask2(a), res2 = ask2(b), res3 = ask2(c);
	if (!res1.first && !res1.second) {
		return a;
	}
	if (!res2.first && !res2.second) {
		return b;
	}
	if (!res3.first && !res3.second) {
		return c;
	}
	int expcount = max(max(res1.first + res1.second, res2.first + res2.second), res3.first + res3.second);
	
	int found = 0;
	while (res1.first + res1.second != expcount) {
		a++;
		found++;
		res1 = ask2(a);
		if (!res1.first && !res1.second) {
			return a;
		}
	}
	deque<tuple<int, int, int, int, int>> segs = {{0, n / 2 - 1, res1.first - found, 0, found + res1.second}, {a + 1, n - 1, res1.second, res1.first, 0}};
	while (!segs.empty()) {
		int lo, hi, cnt, tol, tor, l, r;
		tie(lo, hi, cnt, tol, tor) = segs.front();
		segs.pop_front();
		
		int med = (lo + hi) / 2;
		auto cand = seen_inds.lower_bound(lo);
		if (cand != seen_inds.end() && *cand <= hi) {
			med = *cand;
		}
		int omed = med;
		tie(l, r) = ask2(med);
		if (!l && !r) {
			return med;
		}
		int found2 = 0;
		while (l + r != expcount && med < hi) {
			med++;
			found2++;
			tie(l, r) = ask2(med);
			if (!l && !r) {
				return med;
			}
		}
		if (l + r > expcount) {
			expcount = l + r;
			segs.clear();
			segs = {{0, med - 1, l, 0, r}};
			segs = {{med + 1, n - 1, r, l, 0}};
			continue;
		}
		if (l + r != expcount) {
			if (cnt - found2 - 1 > 0) {
				segs.emplace_back(lo, omed - 1, cnt - found2 - 1, tol, tor + found2);
			}
		} else {
			if (l - found2 - tol > 0) {
				segs.emplace_back(lo, omed - 1, l - found2 - tol, tol, found2 + r);
			}
			if (r - tor > 0) {
				segs.emplace_back(med + 1, hi, r - tor, l, tor);
			}

		}
	}
	
	return 0;
}

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