Submission #286373

#	Time	Username	Problem	Language	Result	Execution time	Memory
286373		Atill83	The Big Prize (IOI17_prize)	C++14	97.93 / 100	68 ms	5496 KiB

prize

	#include "prize.h"
	#include <bits/stdc++.h>
	using namespace std;
	const int MAXN = (int) 2e5 + 5;
	vector<int> asked[MAXN];
	vector<int> kuc;
	bool kc[MAXN];
	vector<int> aski(int i){
		if(!asked[i].empty()) return asked[i];
		return asked[i] = ask(i);
	}




	int find_best(int n) {
		int top = 0;
		mt19937 gen(time(NULL));
		for(int i = 0; i < 470; i++){
			int u = gen() % n;
			vector<int> cev = aski(u);
			if(cev[0] + cev[1] == 0) return u;
			top = max(top, cev[0] + cev[1]);
		}
		//assert(top <= 600);


		while(true){
			int sz1 = kuc.size();
			int l = 0, r = n - 1;
			while(l < r){
				int m = (l + r) / 2;
				while(kc[m] && m > l) m--;
				if(m == l && kc[m]){
					m = (l + r) / 2;
					while(m < r && kc[m]) m++;
				}
				vector<int> cev = aski(m);
				if(cev[0] + cev[1] != top){
					l = m;
					r = m;
				}else{
					cev[0] -= lower_bound(kuc.begin(), kuc.end(), m) - kuc.begin();
					if(cev[0] > 0){
						r = m - 1;
					}else{
						l = m + 1;
					}
				}
			}
			vector<int> cev = aski(l);
			//assert(cev[0] + cev[1] != top);
			if(cev[0] == 0 && cev[1] == 0){
				return l;
			}else {
				//assert(kc[l] != 1);
				kuc.push_back(l);
				int idx = kuc.size() - 1;
				while(idx != 0 && kuc[idx - 1] > kuc[idx]){
					idx--;
					swap(kuc[idx], kuc[idx + 1]);
				}
				kc[l] = 1;
			}
			//assert(kuc.size() != sz1);
		}
		return -1;
	}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:29:8: warning: unused variable 'sz1' [-Wunused-variable]
   29 |    int sz1 = kuc.size();
      |        ^~~

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