Submission #613979

#	Time	Username	Problem	Language	Result	Execution time	Memory
613979		AriaH	The Big Prize (IOI17_prize)	C++17	100 / 100	65 ms	14760 KiB

prize

#include "prize.h"
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 2e5 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;

int n;

vector < int > vec[N];

set < int > st[N];

inline vector < int > Ask(int pos)
{
	if(!vec[pos].empty())
	{
		return vec[pos];
	}
	return vec[pos] = ask(pos);
}

int solve(int l, int r)
{
	if(l > r) return -1;
	int mid = (l + r) >> 1;
	int s = Ask(mid)[0] + Ask(mid)[1];
	if(!s) return mid;
	auto it = st[s].lower_bound(mid);
	int L = 0, R = 0;
	if(it == st[s].begin() || Ask(mid)[0] != Ask(*prev(it))[0])
	{
		L = 1;
	}
	if(it == st[s].end() || Ask(mid)[1] != Ask(*it)[1])
	{
		R = 1;
	}
	if(Ask(mid)[0] == 0) L = 0;
	if(Ask(mid)[1] == 0) R = 0;
	st[s].insert(mid);
	if(L)
	{
		int ret = solve(l, mid - 1);
		if(ret != -1) return ret;
	}
	if(R)
	{
		int ret = solve(mid + 1, r);
		if(ret != -1) return ret;
	}
	return -1;
}

int find_best(int _n)
{
	n = _n;
	return solve(0, n - 1);
}

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