Submission #73127

#	Time	Username	Problem	Language	Result	Execution time	Memory
73127		aleksam	The Big Prize (IOI17_prize)	C++14	0 / 100	13 ms	9848 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>
#define MAX_N 200000
using namespace std;

int N;
bool mark[MAX_N];
vector<int> resp[MAX_N];
int worst=MAX_N;

vector<int> aksp(int x){
	if(!mark[x]){
		resp[x]=ask(x);
		mark[x]=1;
	}
	return resp[x];
}

int left(int x){
	if(!mark[x]){
		resp[x]=ask(x);
		mark[x]=1;
	}
	return resp[x][0];
}

int right(int x){
	if(!mark[x]){
		resp[x]=ask(x);
		mark[x]=1;
	}
	return resp[x][1];
}

int weight(int x){
	return left(x)+right(x);
}

int find(int l, int r){
	if(l+1>=r){
		if(left(l)+right(l)==0){
			return l;
		}
		return -1;
	}
	if(weight(l)!=weight(r)){
		if(weight(l)>weight(r))return find(l, r-1);
		else return find(l+1, r);
	}
	if(left(r)==left(l))return -1;
	int mid=(l+r)/2;
	int rl=-1, rr=-1;
	if(weight(mid)==0)return mid;
	rl=find(l, mid);
	rr=find(mid, r);
	if(rl==-1 && rr==-1)return -1;
	else return rl>rr?rl:rr;
}

int easy_solve(int n) {
	for(int i = 0; i < n; i++) {
		std::vector<int> res = ask(i);
		if(res[0] + res[1] == 0)
			return i;
	}
	return 0;
}

void find_worst(){
	for(int i=0; i<450; ++i){//Ad hoc
		if(left(i)+right(i)<worst){
			worst=left(i)+right(i);
			if(2*worst>N){
				return;
			}
		}
	}
}

int find_best(int n) {
	
	N=n;
	if(N<5005)return easy_solve(N);
	//find_worst();
	
	return find(0, N);
}

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