Submission #260488

#	Time	Username	Problem	Language	Result	Execution time	Memory
260488		b00n0rp	The Big Prize (IOI17_prize)	C++17	20 / 100	86 ms	5580 KiB

prize

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

#define vi vector<int>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define all(v) v.begin(),v.end()

mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 

vector<pii> possible;
int mx;

vi done[200005];

vi asky(int ind){
	// cout << ind << endl;
	if(done[ind].size()) return done[ind];
	return done[ind] = ask(ind);
}

void solve(int l,int r,int lcnt,int rcnt){
	// cout << l << " " << r << " " << lcnt << " " << rcnt << endl;
	if(l > r) return;
	if(lcnt+rcnt == mx) return;
	int mid = (l+r)/2;
	int m = mid;
	int bizz = 0;
	while(mid >= l){
		vi gg = asky(mid);
		if(gg[0]+gg[1] == mx){
			solve(l,mid-1,lcnt,gg[1]);
			solve(m+1,r,gg[0]+bizz,rcnt);
			return;
		}
		possible.pb({gg[0]+gg[1],mid});
		bizz++;
		mid--;
	}
	solve(m+1,r,lcnt+bizz,rcnt);
}

int find_best(int n) {
	for(int i = 0; i < 300; i++){
		int ind = RNG()%n;
		// cout << ind << endl;
		vi gg = asky(ind);
		mx = max(mx,gg[0]+gg[1]);
	}
	solve(0,n-1,0,0);
	sort(all(possible));
	return possible[0].S;
}

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