Submission #137758

#	Time	Username	Problem	Language	Result	Execution time	Memory
137758		Mahdi_Jfri	The Big Prize (IOI17_prize)	C++14	90 / 100	107 ms	5312 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
 
const int maxn = 2e5 + 20;
 
vector<int> res[maxn] , candid;
 
int mx;

bool found;
 
vector<int> reval(int k)
{
	if(!res[k].empty())
		return res[k];
 
	res[k] = ask(k);
	if(res[k][0] + res[k][1] == 0)
		found = 1;
	return res[k];
}
 
void solve(int l , int r)
{
	if(found)
		return;
	while(l < r)
	{
		if(found)
			return;
		auto tmp = reval(l);
		if(tmp[0] + tmp[1] != mx)
			candid.pb(l++);
		else
			break;
	}
	if(found)
		return;
	while(l < r)
	{
		if(found)
			return;
		r--;
		auto tmp = reval(r);
		if(tmp[0] + tmp[1] != mx)
			candid.pb(r);
		else
			break;
	}
	if(found)
		return;
 
	if(l >= r)
		return;
 
	reval(l); reval(r);
	if(res[r][0] - res[l][0] == 0)
		return;
 
	int m = (l + r) / 2;
	solve(m , r + 1);
	solve(l , m);
}
 
int find_best(int n)
{
	if(n <= 5000)
	{
		for(int i = 0; i < n; i++) {
			std::vector<int> res = ask(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}
 
	for(int i = 0; i < 500; i++)
	{
		vector<int> tmp = reval(i);
		mx = max(mx , tmp[0] + tmp[1]);
	}
 
	solve(0 , n);
 
	for(int i = 0; i < n; i++)
	{
		if(res[i].empty())
			continue;
		auto tmp = res[i];
		if(tmp[0] + tmp[1] == 0)
			return i;
	}
	cout << 1/0;
	return -85;
}
 
 

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:97:11: warning: division by zero [-Wdiv-by-zero]
  cout << 1/0;
          ~^~

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