Submission #593350

#	Time	Username	Problem	Language	Result	Execution time	Memory
593350		blue	The Big Prize (IOI17_prize)	C++17	20 / 100	183 ms	5300 KiB

prize

#include "prize.h"
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())


const int mx = 200'000;
int lim = 200'000;


int n;

int prizes = 0; //lollipops are not prizes

vvi qr(mx, vi(0));

int askcount = 0;

vi query(int i)
{
	// cerr << "query " << i << '\n';
	cerr << sz(qr[i]) << '\n';
	if(qr[i].empty())
	{
		// cerr << "trigger\n";
		askcount++;
		if(!(askcount <= 50'000))
			while(1);
		qr[i] = ask(i);
	}
	
	return qr[i];
}

bool isprize(int i)
{
	query(i);
	if(qr[i][0] + qr[i][1] != prizes)
		return 1;
	else 
		return 0;
}

bool isdiamond(int i)
{
	query(i);
	return qr[i][0] + qr[i][1] == 0;
}

void solve(int l, int r)
{
	if(r < l)
		return;

	// cerr << "solve " << l << ' ' << r << '\n';

	query(l);
	query(r);

	if(l == r)
		return;

	// cerr << "hello\n";

	if(isprize(l))
	{
		l++;
		solve(l, r);
		return;
	}

	if(isprize(r))
	{
		r--;
		solve(l, r);
		return;
	}

	int m = (l+r)/2;
	query(m);

	// cerr << "check\n";

	int ml = m, mr = m;

	while(isprize(ml))
		ml--;
	query(ml);

	// cerr << "check\n";

	// cerr << l << " : " << ml << '\n';
	// cerr << sz(qr[l]) << ' ' << sz(qr[ml]) << '\n';
	if(ml != l && qr[ml][0] - qr[l][0] >= 1)
	{
		// cerr << "call " << l+1 << ' ' << ml-1 << '\n';
		solve(l+1, ml-1);
	}

	while(isprize(mr))
		mr++;
	query(mr);

	// cerr << "check 5\n";

	// cerr << r << " : " << mr << '\n';

	if(mr != r && qr[r][0] - qr[mr][0] >= 1)
		solve(mr+1, r-1);
}

int find_best(int n_)
{
	n = n_;

	lim = 1;
	while(lim*lim <= n)
		lim++;
	// cerr << n << " : " << lim << '\n';

	for(int i = 0; i < min(n,lim); i++)
	{
		vi q = query(i);
		if(q[0] + q[1] == 0)
			return i;
	}

	// lim = 1; //the first thing must be a lollipop


	for(int i = 0; i < lim; i++)
	{
		vi qi = query(i);

		prizes = max(prizes, qi[0] + qi[1]);
	}

	// cerr << "prizes = " << prizes << '\n';

	solve(lim, n-1);

	for(int i = 0; i < n; i++)
		if(!qr[i].empty())
			if(qr[i][0] + qr[i][1] == 0)
				return i;

	// cerr << "critical error\n";
	assert(0);
	return -1;
}

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