Submission #136012

#	Time	Username	Problem	Language	Result	Execution time	Memory
136012		JustasZ	The Big Prize (IOI17_prize)	C++14	20 / 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 it = 0; it < 200; it++)
	{
		int p = rd() % n;
		a = ask(p);
		mx = max(mx, a[0] + a[1]);
	}
	int cnt = 200;
	int i = 0;
	while(i < n)
	{
		//assert(++cnt < 10000);
		a = ask(i);
		if(a[0] + a[1] == 0)
			return i;
		vector<int>nex = ask(i + 1);
		if(nex[0] + nex[1] != mx)
		{
			++i;
			continue;
		}
		if(a[0] + a[1] == mx)
		{
			int fi = a[0], se = a[1];
			int l = i + 1, r = n - se;
			while(l < r)
			{
				int mid = (l + r) / 2;
				//assert(++cnt < 10000);
				a = ask(mid);
				if(a[0] + a[1] != mx)
					r = mid;
				else
				{
					if(a[0] > fi)
						r = mid - 1;
					else
						l = mid + 1;
				}
			}
			//assert(++cnt < 10000);
			a = ask(l);
			//assert(a[0] + a[1] != mx);
			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:43:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 200;
      ^~~
prize.cpp:86:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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