Submission #136002

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

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