Submission #429105

#	Time	Username	Problem	Language	Result	Execution time	Memory
429105		vanic	The Big Prize (IOI17_prize)	C++14	20 / 100	81 ms	512 KiB

prize

#include "prize.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <set>
#include <unistd.h>
#include <cassert>

using namespace std;

const int maxn=2e5+5;
const int cap=1000;

int sum;
bool asked[maxn];
int uk;

int nadji(int L, int D, int vall, int vald){
	int mid=(L+D)/2;
	vector < int > v={-1, -1};
	while(mid<D && v[0]+v[1]!=sum){
		if(!asked[mid]){
			uk++;
			v=ask(mid);
			asked[mid]=1;
			if(!v[0] && !v[1]){
				return mid;
			}
		}
		mid++;
	}
	if(v[0]+v[1]!=sum){
		mid=(L+D)/2;
		while(mid>=L && v[0]+v[1]!=sum){
			if(!asked[mid]){
				uk++;
				v=ask(mid);
				asked[mid]=1;
				if(!v[0] && !v[1]){
					return mid;
				}
			}
			mid--;
		}
		if(v[0]+v[1]!=sum){
			return -1;
		}
		uk--;
		mid++;
	}
	else{
		uk--;
		mid--;
	}
	assert(uk<cap);
	int br=-1;
	if(v[0]-vall){
		br=nadji(L, mid, vall, v[1]);
		if(br!=-1){
			return br;
		}
	}
	if(v[1]-vald){
		br=nadji(mid+1, D, v[0], vald);
	}
	return br;
}

set < int > svi;
set < int > jaki;

int find_best(int n){
	srand(time(NULL));
	vector < int > v;
	int pos;
	if(n>5000){
		for(int i=0; i<440; i++){
			do{
				pos=rand()%n;
			}while(svi.find(pos)!=svi.end());
			v=ask(pos);
			svi.insert(pos);
			if(!v[0] && !v[1]){
				return pos;
			}
			if(v[0]+v[1]==sum){
				jaki.insert(pos);
			}
			else if(v[0]+v[1]>sum){
				jaki.clear();
				jaki.insert(pos);
				sum=v[0]+v[1];
			}
		}
		while(!jaki.empty()){
			svi.erase(*jaki.begin());
			jaki.erase(jaki.begin());
		}
		while(!svi.empty()){
			asked[*svi.begin()]=1;
			svi.erase(svi.begin());
		}
		int a=nadji(0, n, 0, 0);
		assert(a!=-1);
		return a;
	}
	else{
		for(int i=0; i<n; i++){
			v=ask(i);
			if(!v[0] && !v[1]){
				return i;
			}
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:77:17: warning: control reaches end of non-void function [-Wreturn-type]
   77 |  vector < int > v;
      |                 ^

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