Submission #1204647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204647		Captain_Georgia	The Big Prize (IOI17_prize)	C++20	0 / 100	9 ms	23904 KiB

prize

#include "prize.h"

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

const int MX = 1e6 + 66;
vector<int> memo[MX];
vector<int> query (int x) {
	if (memo[x].size() == 0) {
		memo[x] = ask(x);
	}
	return memo[x];
}

mt19937 rng(time(NULL));
int find_best (int N) {
	int node = rng() % N;
	query(node);
	for (int i = 0;i < 20;i ++) {
		int node2 = rng() % N;
		query(node2);
		if (memo[node][0] + memo[node][1] < memo[node2][0] + memo[node2][1]) node = node2;
	}
	// cerr << node << "\n";
	
	int low = 0, high = node;
	for (int i = memo[node][0] - 1;i >= 0;i --) {
		while (low < high) {
			int mid = (low + high + 1) / 2;
			query(mid);
			if (memo[mid][0] + memo[mid][1] == memo[node][0] + memo[node][1]) {
				if (memo[mid][0] >= i) high = mid - 1;
				else low = mid + 1;
			} else {
				low = mid;
			}
		}
		// cerr << high << "\n";
		query(high);
		assert(memo[high][0] + memo[high][1] < memo[node][0] + memo[node][1]);
		if (memo[high][0] + memo[high][1] == 0) return high;
		low = 0;
	}
	low = node;
	high = N - 1;
	for (int i = memo[node][0];i < memo[node][0] + memo[node][1];i ++) {
		while (low < high) {
			int mid = (low + high) / 2;
			query(mid);
			if (memo[mid][0] + memo[mid][1] == memo[node][0] + memo[node][1]) {
				if (memo[mid][0] <= i) low = mid + 1;
				else high = mid - 1;
			} else {
				high = mid;
			}
		}
		// cerr << high << "\n";
		query(high);
		assert(memo[high][0] + memo[high][1] < memo[node][0] + memo[node][1]);
		if (memo[high][0] + memo[high][1] == 0) return high;
		high = N - 1;
	}
	while(true);
	return -2;
}

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