Submission #73416

#	Time	Username	Problem	Language	Result	Execution time	Memory
73416		SmsS	The Big Prize (IOI17_prize)	C++17	97.45 / 100	74 ms	572 KiB

prize

#include<bits/stdc++.h>
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "prize.h"

const bool test = 0;

int mn;
int cnt = 0;
set<int> st;

int solve(int l,int r,vector<int> L,vector<int> R){
	if(l == r-1){
		if(L[0]+L[1] == 0) return l;
		return -1;
	}
	if(rand()%20000 == 0) return -1;
	if(L[1]-R[1] == 0 && R[0]-L[0] == 0) return -1;
	int mid = (l+r)/2;
	vector<int> MID = ask(mid);
	if(MID[0]+MID[1] == 0) return mid;
	int res = -1;

	if(res == -1) res = solve(mid,r,MID,R);
	if(res == -1) res = solve(l,mid,L,MID);
	return res;
}

int find_best(int n) {

	if(!test && n <= 5000){
		for2(i,0,n){
			vector<int> res = ask(i);
			if(res[0]+res[1] == 0) return i;
		}
	}
	srand(time(NULL));
	for2(rep,0,20){
		vector<int> res = ask(rand()%n);
		mn = max(mn,res[0]+res[1]);
	}
	int l,r;
	vector<int> L = ask(0);
	vector<int> R = ask(n-1);
	if(R[0]+R[1] == 0) return n-1;
	return solve(0,n-1,L,R);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:42:6: warning: unused variable 'l' [-Wunused-variable]
  int l,r;
      ^
prize.cpp:42:8: warning: unused variable 'r' [-Wunused-variable]
  int l,r;
        ^

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