Submission #260492

#	Time	Username	Problem	Language	Result	Execution time	Memory
260492		b00n0rp	The Big Prize (IOI17_prize)	C++17	20 / 100	135 ms	5524 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) {
	vi bruh = {175038, 164912, 48447, 56204, 130467, 61981, 156795, 71155, 165755, 46492, 14913, 121820, 48037, 14809, 18188, 47090, 44335, 70042, 63699, 112155, 92988, 195226, 83797, 177680, 156562, 91803, 74301, 131570, 93639, 30707, 117677, 164693, 60304, 82393, 50874, 42681, 196535, 114714, 130612, 8175, 1961, 167732, 25952, 126880, 35181, 4129, 195226, 65614, 93274, 93049, 106533, 150951, 10812, 158910, 141820, 34594, 129541, 149736, 13599, 191657, 182831, 191057, 96180, 125258, 19449, 71635, 153028, 182528, 111578, 4250, 165230, 3356, 39309, 332, 175116, 196923, 95308, 104449, 92485, 196292, 161180, 194584, 87349, 91014, 102108, 138598, 183452, 120325, 103919, 145804, 149462, 181941, 13311, 151831, 40995, 24088, 1702, 78417, 20497, 137355, 147324, 70197, 29274, 107710, 56993, 27165, 79201, 48319, 67302, 81015, 61015, 140652, 6451, 144012, 66265, 196066, 44906, 98585, 80597, 194841, 78730, 198086, 160990, 26219, 21458, 31211, 4117, 139031, 93154, 168228, 29535, 153990, 192236, 189054, 132102, 93027, 62180, 150788, 140895, 31431, 26133, 180233, 55568, 121279, 150362, 78361, 171501, 81164, 181689, 143013, 93429, 89467, 182020, 92448, 182745, 115189, 83809, 544, 8572, 175359, 136681, 62664, 48643, 163232, 1486, 90043, 76547, 34492, 121612, 108895, 52498, 159681, 44550, 55494, 174209, 111888, 14058, 151376, 127349, 111296, 71294, 80716, 100, 16638, 159372, 76664, 33592, 35855, 94299, 66743, 38793, 62754, 74804, 28105, 110297, 31273, 65903, 114041, 24099, 142849};
	for(int i = 0; i < 200; i++){
		int ind = bruh[i]%n;
		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