Submission #1072450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072450		Joshua_Andersson	The Big Prize (IOI17_prize)	C++14	20 / 100	67 ms	1636 KiB

prize

#include "prize.h"

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

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

map<int, vi> cache;
vi q(int i)
{
	if (cache.find(i) != cache.end()) return cache[i];
	return cache[i] = ask(i);
}

int find_best(int n)
{
	int lollipop_cnt = 0;
	int i = 0;
	rep(i, 500)
	{
		vi res = q(i);
		ll s = res[0] + res[1];
		if (s==0)
		{
			return i;
		}
		// assume that i is second most common
		// then there are s^2 of type t[i], and s^4 of most common type
		assert(s <= 500);
		if (s*s*s*s>n)
		{
			lollipop_cnt = s;
			break;
		}
		lollipop_cnt = max(lollipop_cnt, (int)s);
		i++;
	}
	
	int jump = 220;
	while (true)
	{
		vi base = q(i);
		if (base[0]+base[1]==0)
		{
			return i;
		}
		
		if (base[0]+base[1]==lollipop_cnt)
		{
			if (i+ jump <n)
			{
				vi b2 = q(i + jump);
				if (b2 == base)
				{
					i += jump;
					continue;
				}
			}
			
			int lo = i;
			int hi = min(n, i+ jump);
			while (lo+1<hi)
			{
				int mid = (lo + hi) / 2;
				vi m = q(mid);
				if (m == base)
				{
					lo = mid;
				}
				else hi = mid;
			}
			i = hi;
		}
		else
		{
			i++;
		}
	}

	return 0;
}

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