Submission #441818

#	Time	Username	Problem	Language	Result	Execution time	Memory
441818		prvocislo	The Big Prize (IOI17_prize)	C++17	20 / 100	69 ms	1368 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

const int maxk = 1;
map<int, vector<int> > me; // tam si pamatame nase doterajsie queries
bool di = false;
int notl;
vector<int> ask2(int x)
{
	if (!me.count(x)) return me[x] = ask(x);
	else return me[x];
}
bool lolipop(int x)
{
	vector<int> v = ask2(x);
	return v[0] + v[1] == notl;
}
void rek(int l, int r, int cntl, int cntr)
{
	if (r < l || cntl + cntr == notl) return;
	int mr = (l + r) / 2, ml = mr;
	while (ml >= l && !lolipop(ml)) ml--;
	while (mr <= r && !lolipop(mr)) mr++;
	if (ml > l)
	{
		vector<int> vl = ask2(ml);
		rek(l, ml-1, cntl, vl[1]);
	}
	if (mr < r)
	{
		vector<int> vr = ask2(mr);
		rek(mr+1, r, vr[0], cntr);
	}
}
int find_best(int n) 
{
	for (int i = 0; i < min(n, maxk); i++) ask2(i);
	for (const pair<int, vector<int> > &i : me)
		notl = max(notl, i.second[0] + i.second[1]);
	rek(0, n-1, 0, 0);
	for (const pair<int, vector<int> > &i : me) if (i.second[0] + i.second[1] == 0) return i.first;
	assert(false);
}

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