Submission #1208709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208709		m5588ohammed	The Big Prize (IOI17_prize)	C++20	91.40 / 100	17 ms	5284 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 cntask;
vector<int> getVal(int i){
	if(res[i].empty()){
		res[i] = ask(i);
		cntask++;
	}
	if(cntask == 9000) assert(0);
	return res[i];
}
int find_best(int n)
{
	res.resize(n);
	// assert(0);
	if (n <= 5000)
	{
		for (int i = 0; i < n; i++)
		{
			res[i] = getVal(i);
			if (res[i][0] + res[i][1] == 0)
				return i;
		}
	}
	int mx = 0;
	for (int tmp = 0; tmp < 500; tmp++)
	{
		int md = rand() % n;
		if (res[md].empty())
			res[md] = getVal(md);
		mx = max(res[md][0] + res[md][1], mx);
	}
	int sq = sqrt(n);
	int s = 0, e = sq;
	while (s < e)
	{
		// cout<<s<<' '<<e<<'\n';
		while (s <= e)
		{
			if (res[s].empty())
				res[s] = getVal(s);
			if (res[s][0] + res[s][1] != mx)
			{
				if (res[s][0] + res[s][1] == 0)
					return s;
				s++;
				continue;
			}
			if (res[e].empty())
				res[e] = getVal(e);
			if (res[s] == res[e])
				break;
			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] = getVal(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] = getVal(l);
			if (res[l][0] + res[l][1] == 0)
				return l;
			s = l + 1;
		}
		s = e + 1;
		e += sq + 1;
		e = min(e, n - 1);
	}
}

Compilation message (stderr)

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

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