Submission #136021

#	Time	Username	Problem	Language	Result	Execution time	Memory
136021		JustasZ	The Big Prize (IOI17_prize)	C++14	90 / 100	102 ms	504 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
/*vector<int> ask(int i)
{
	cout << "? " << i << endl;
	vector<int>a(2);
	cin >> a[0] >> a[1];
	return a;
}*/
int find_best(int n)
{
	vector<int>a;
	if(n < 5000)
	{
		for(int i = 0; i < n; i++)
		{
			a = ask(i);
			if(a[0] == 0 && a[1] == 0)
				return i;
		}
	}
	int mx = 0;
	for(int i = 0; i < 500; i++)
	{
		a = ask(i);
		mx = max(mx, a[0] + a[1]);
	}
	int i = 0;
	while(i < n)
	{
		a = ask(i);
		if(a[0] + a[1] == 0)
			return i;
		if(a[0] + a[1] == mx)
		{
			vector<int>b = a;
			int l = i + 1, r = n - 1;
			while(l < r)
			{
				int mid = (l + r + 1) / 2;
				a = ask(mid);
				if(b == a)
					l = mid;
				else
					r = mid - 1;
			}
			a = ask(l);
			if(a[0] + a[1] == 0)
				return l;
			i = l + 1;
		}
		else 
			i++;
	}
}

Compilation message (stderr)

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

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