Submission #73130

#	Time	Username	Problem	Language	Result	Execution time	Memory
73130		aleksam	The Big Prize (IOI17_prize)	C++14	90 / 100	98 ms	5772 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>=r && l>=0 && l<N){
		if(weight(l)==0){
			return l;
		}
		return -1;
	}
	if(weight(l)==0)return l;
	if(weight(r)==0)return r;
	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);
	if(rl>-1)return rl;
	else return find(mid+1, r);
}

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-1);
}

Compilation message (stderr)

prize.cpp: In function 'int find(int, int)':
prize.cpp:56:13: warning: unused variable 'rr' [-Wunused-variable]
  int rl=-1, rr=-1;
             ^~

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