Submission #286369

#	Time	Username	Problem	Language	Result	Execution time	Memory
286369		Atill83	The Big Prize (IOI17_prize)	C++14	20 / 100	3040 ms	13980 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 < 280; 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:7: warning: unused variable 'sz1' [-Wunused-variable]
   29 |   int sz1 = kuc.size();
      |       ^~~

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