Submission #1204683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204683		Captain_Georgia	The Big Prize (IOI17_prize)	C++20	20 / 100	22 ms	5352 KiB

prize

#include "prize.h"

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

const int MX = 2e5 + 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 < 100;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";
	// node = 5;
	// query(node);
	
	int low = 0, high = node - 1;
	for (int i = memo[node][0] - 1;i >= 0;i --) {
		while (low < high) {
			int mid = (low + high) / 2;
			// cerr << low << " " << high << "\n";
			if (low + 1 == high) {
				query(high);
				if (memo[high][0] + memo[high][1] == memo[node][0] + memo[node][1]) {
					high = low;
				} else {
					low = high;
				}
				break;
			}
			
			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 {
				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;
		high --;
	} // cerr << "\n";
	low = node + 1;
	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;
			if (low + 1 == high) {
				query(low);
				if (memo[low][0] + memo[low][1] == memo[node][0] + memo[node][1]) {
					low = high;
				} else {
					high = low;
				}
				break;
			}

			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;
		low ++;
		high = N - 1;
	}
	// assert(0);
	return 0;
}

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