Submission #1177361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177361		emad234	The Big Prize (IOI17_prize)	C++20	20 / 100	26 ms	5352 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;
vector<vector<int>> res;
int find_best(int n) {
	res.resize(n);
	if (n <= 5000)
	{
		for(int i = 0;i < n;i++){
			res[i] = ask(i);
			if(res[i][0] + res[i][1] == 0) return i;
		}
	}
	int mx = 0;
	for(int tmp = 0; tmp < 20;tmp++){
		int md = rand() % n;
		if(res[md].empty()) res[md] = ask(md);
		mx = max(res[md][0] + res[md][1], mx);
	}
	int s = 0,e = n - 1;
	while(1){
		if(res[s].empty()) res[s] = ask(s);
		if(res[s][0] + res[s][1] != mx){
			if(res[s][0] + res[s][1] == 0) return s;
			s++;
			continue;
		}
		int num = res[s][0];
		int l = s - 1,r = e,md;
		while(l < r){
			md = (l + r + 1) / 2;
			if(res[md].empty())res[md] = ask(md);
			if(res[md][0] + res[md][1] == 0) return md;
			if(res[md][0] + res[md][1] != mx || res[md][0] != num){

				r = md - 1;
			}else l = md;
		}
		l++;
		if(res[l].empty()) res[l] = ask(l);
		if (res[l][0] + res[l][1] == 0) return l;
		s = l + 1;
	}
}

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