Submission #285172

#	Time	Username	Problem	Language	Result	Execution time	Memory
285172		mohammad	The Big Prize (IOI17_prize)	C++14	98.12 / 100	58 ms	416 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
 
#define endl "\n"
// #define int long long

typedef long long ll ;
const ll ooo = 1e14 ;
const ll oo = 2e9 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7  ;
const int N = 10000010  ;

int binary(int lo , int hi , vector<int> l , vector<int> r){
	if(lo > hi) return -1;
	int md = (lo + hi) / 2;
	vector<int> res = ask(md);
	if(res[0] + res[1] == 0) return md;
	int ans = -1;
	int ra = rand() % 2;
	if(ra){
		if(res[1] > 0 && res != l) ans = binary(md+1 , hi , l , res);
		if(ans == -1 && res[0] > 0 && res != r) ans = binary(lo , md - 1 , res , r);
	}else {
		if( res[0] > 0 && res != r) ans = binary(lo , md - 1 , res , r);
		if(ans == -1 && res[1] > 0 && res != l) ans = binary(md+1 , hi , l , res);
	}
	return ans ;
}

int find_best(int n) {
	srand (time(NULL));
	vector<int> x(2 , -1);
	return binary(0 , n - 1 , x , x);
}

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