Submission #425879

#	Time	Username	Problem	Language	Result	Execution time	Memory
425879		Tangent	The Big Prize (IOI17_prize)	C++17	20 / 100	102 ms	972 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()

map<int, pii> memo;
pii ask2(int i) {
	if (memo.find(i) == memo.end()) {
		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;
	while (b == a) {
		b = rand() % n;
	}
	auto res1 = ask2(a), res2 = ask2(b);
	if (!res1.first && !res1.second) {
		return a;
	}
	if (!res2.first && !res2.second) {
		return b;
	}
	int expcount = max(res1.first + res1.second, res2.first + res2.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;
		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) {
			if (cnt - found2 > 0) {
				segs.emplace_back(lo, (lo + hi) / 2 - 1, cnt - found2, tol, tor + found2);
			}
		} else {
			if (l - found2 - tol > 0) {
				segs.emplace_back(lo, (lo + hi) / 2 - 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