Submission #38437

#	Time	Username	Problem	Language	Result	Execution time	Memory
38437		mohammad_kilani	The Big Prize (IOI17_prize)	C++14	90 / 100	89 ms	7168 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
bool asked[N];
vector<int> answer[N];
int mx = 0 ;

vector<int> get(int i){
	if(asked[i])
		return answer[i];
	asked[i] = true;
	return answer[i] = ask(i);

}

int solve(int s,int e){
	if(s == e){
		vector<int> cur = get(s);
		if(cur[0] + cur[1] != 0) return -1;
		return s;
	}
	vector<int> v1 = get(s);
	if(v1[0] + v1[1] == 0) return s;
	if(v1[0] + v1[1] != mx) return solve(s+1,e);
	vector<int> v2 = get(e);
	if(v2[0] + v2[1] == 0) return e;
	if(v2[0] + v2[1] != mx) return solve(s,e-1);
	if(v1[0] == v2[0]) return -1;
	if(s == e - 1) return -1;
	int mid = (s + e) / 2;
	if(rand() % 2){
		int idx = solve(s,mid);
		if(idx != -1) return idx;
		return solve(mid+1,e);
	}
	int idx = solve(mid+1,e);
	if(idx != -1) return idx;
	return solve(s,mid);
}

int find_best(int n) {
	srand(time(0));
	int num = min(n,480);
	for(int i=0;i<num;i++){
		vector<int> res = get(i);
		int cur = res[0] + res[1];
		mx = max(mx,cur);
	}
	return solve(0,n-1);
}

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