Submission #1272951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272951		hgmhc	The Big Prize (IOI17_prize)	C++20	100 / 100	24 ms	1380 KiB

prize

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

mt19937_64 rng(random_device{}());
#define my_random(l,r) uniform_int_distribution<int>(l,r)(rng)
#define my_shuffle(...) shuffle(__VA_ARGS__,rng)

map<int, vector<int>> cache;
map<int, set<int>> S;

int n;
int mx;

vector<int> ASK(int x) {
	if(x==-1) return {0, n};
	if(x==n) return {n, 0};
	if(not cache.contains(x)) cache[x] = ask(x);
	S[cache[x][0] + cache[x][1]].insert(x);
	return cache[x];
}

void search(int a, int b) {
	if(a>b) return;
	
	int m1=(a+b)>>1, m2=m1;
	auto v=ASK(m1);
	
	while(a<=m1 && ASK(m1)[0] + ASK(m1)[1] < mx) {
		m1--;
	}
	while(m2<=b && ASK(m2)[0] + ASK(m2)[1] < mx) {
		m2++;
	}
	
	if(a<m1 && ASK(a-1)[0]<ASK(m1)[0]) {
		search(a, m1-1);
	}
	if(m2<b && ASK(m2)[1]>ASK(b+1)[1]) {
		search(m2+1, b);
	}
}

int find_best(int _n) {
	n = _n;
	
	for(int i=0; i<200; ++i) {
		auto v=ASK(my_random(0, n-1));
		mx = max(mx, v[0]+v[1]);
	}
	
	search(0, n-1);
	
	for(auto [x, y] : S) {
		cerr << x << ": ";
		for(auto e : y) cerr << e << ' ';
		cerr << endl;
	}
	
	assert(S.begin()->first == 0);
	
	return *(S.begin()->second.begin());
}

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