Submission #1272947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272947		hgmhc	The Big Prize (IOI17_prize)	C++20	0 / 100	2 ms	516 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];
}

int L[1'000'000];
int R[1'000'000];

int Left(int x) {
	if(x==-1) return 0;
	return L[x];
}

int Right(int x) {
	if(x==n) return 0;
	return R[x];
}

void search(int a, int b) {
	if(a>b) return;
	
	int m1=(a+b)>>1, m2=m1;
	
	while(a<m1 && ASK(m1)[0] + ASK(m1)[1] < mx) m1--;
	while(m2<b && ASK(m2)[0] + ASK(m2)[1] < mx) m2++;
	
	for(int i=m1; i<=m2; ++i) {
		L[i]=Left(m1-1);
		R[i]=Right(m2+1);
	}
	
	if(a<m1 && Left(a-1)<ASK(m1)[0]) {
		search(a, m1-1);
	}
	if(m2<b && ASK(m2)[1]>Right(b+1)) {
		search(m2+1, b);
	}
}

int find_best(int _n) {
	n = _n;
	
	for(int i=0; i<100; ++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: 0 / 20
• Subtask 2: 0 / 80