Submission #1273421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273421		Lithanium	The Big Prize (IOI17_prize)	C++20	0 / 100	7 ms	1944 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rd(time(0));

int K = 1000; // block size
int N;

pair<int, int> cache[200005];

pair<int, int> query(int i) {
	if (cache[i].first != -1) return cache[i];
	vector<int> v = ask(i-1);
	return cache[i] = make_pair(v[0], v[1]);
}

int sum(int i) {
	auto [x, y] = query(i);
	return x+y;
}

int find_best(int n) {
	N = n;
	for (int i = 1; i <= N; i ++) cache[i] = {-1, -1};
	// rng 50 times to find the max
	int total = 0;
	for (int t = 0; t < 50; t ++) total = max(total, sum(rd()%N+1));
	// consider each block
	set<int> special;
	for (int i = 1; i <= N; i += K) {
		// i -> min(N, i+K-1)
		int l = i, r = min(N, i+K-1);
		while (l <= r and sum(l) != total) {
			special.insert(l);
			l ++;
		}
		while (l <= r and sum(r) != total) {
			special.insert(r);
			r --;
		}
		if (l > r) continue;
		// cout << l << " " << r << " range\n";
		auto [a1, b1] = query(l);
		// keep binary searching
		while (true) {
			int low = l, high = r;
			bool found = 0;
			while (high > low) {
				int mid = (low + high)/2;
				int old = mid;
				while (special.count(mid)) mid ++;
				if (mid > high) {
					high = old-1;
					continue;
				}
				auto [x, y] = query(mid);
				if (x+y == total) {
					// subtract the special things between [l, mid]
					int sum = x - a1;
					for (int j:special) if (l <= j and j <= mid) sum --;
					if (sum > 0) high = old-1;
					else low = mid+1;
				} else {
					special.insert(mid);
					found = 1;
					break;
				}
			}
			if (!found) break;
		}
	}
	for (int i:special) if (sum(i) == 0) return i-1;
	return 0;
	// assert(0);
}

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