Submission #73128

#	Time	Username	Problem	Language	Result	Execution time	Memory
73128		aleksam	The Big Prize (IOI17_prize)	C++14	90 / 100	135 ms	5728 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){//printf("weight(%d)\n", x);
	return left(x)+right(x);
}

int find(int l, int r){
	//printf("find(%d, %d)\n", l, r);
	if(l+1>=r && l>=0 && l<N){
		if(left(l)+right(l)==0){
			return l;
		}
		return -1;
	}
	if(weight(l)==0)return l;
	if(weight(r-1)==0)return r-1;
	if(weight(l)!=weight(r-1)){
		if(weight(l)>weight(r-1))return find(l, r-1);
		else return find(l+1, r);
	}
	if(left(r-1)==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: 20 / 20
• Subtask 2: 70 / 80