Submission #1177351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177351		emad234	The Big Prize (IOI17_prize)	C++20	20 / 100	23 ms	408 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mod = 1e9 + 7;
const int mxN = 2e3 + 5;
const int mnN = 1e9 * -1;
using namespace std;

int find_best(int n) {
	vector<int> res;
	if (n <= 5000)
	{
		for(int i = 0;i < n;i++){
			res = ask(i);
			if(res[0] + res[1] == 0) return i;
		}
	}
	int mx = 0;
	for(int tmp = 0; tmp < 20;tmp++){
		res = ask(rand() % n);
		mx = max(res[0] + res[1], mx);
	}
	int s = 0,e = n - 1;
	while(1){
		res = ask(s);
		if(res[0] + res[1] != mx){
			if(res[0] + res[1] == 0) return s;
			s++;
			continue;
		}
		int num = res[0];
		int l = s,r = e,md;
		while(l < r){
			md = (l + r + 1) / 2;
			res = ask(md);
			if(res[0] + res[1] != mx || res[0] != num){
				r = md - 1;
			}else l = md;
		}
		if(l == n - 1) break;
		l++;
		res = ask(l);
		if (res[0] + res[1] == 0) return l;
		s = l + 1;
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

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