Submission #613971

#	Time	Username	Problem	Language	Result	Execution time	Memory
613971		AriaH	The Big Prize (IOI17_prize)	C++17	20 / 100	1299 ms	1048576 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, Ans[2][N];

vector < int > vec[N];

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

int FindRight(int p);

int FindLeft(int p)
{
	if(Ans[0][p] != -1) return Ans[0][p];
	vector < int > V = Ask(p);
	int Me = V[0] + V[1];
	if(V[0] == 0) return -1;
	int l = 0, r = p;
	while(r - l > 1)
	{
		int mid = (l + r) >> 1;
		vector < int > now = Ask(mid);
		int you = now[0] + now[1];
		if(Me > you)
		{
			l = mid;
			continue;
		}
		if(Me == you)
		{
			if(V[0] == now[0])
			{
				r = mid;
			}
			else
			{
				l = mid;
			}
			continue;
		}
		int id = mid;
		while(id < p && Ask(id)[0] + Ask(id)[1] >= Me)
		{
			id = FindRight(id);
		}
		if(id == p)
		{
			r = mid;
		}
		else
		{
			l = mid;
		}
	}
	return Ans[0][p] = l;
}

int FindRight(int p)
{
	if(Ans[1][p] != -1) return Ans[1][p];
	vector < int > V = Ask(p);
	int Me = V[0] + V[1];
	if(V[1] == 0) return -1;
	int l = p, r = n - 1;
	while(r - l > 1)
	{
		int mid = (l + r) >> 1;
		vector < int > now = Ask(mid);
		int you = now[0] + now[1];
		if(Me > you)
		{
			r = mid;
			continue;
		}
		if(Me == you)
		{
			if(V[1] == now[1])
			{
				l = mid;
			}
			else
			{
				r = mid;
			}
			continue;
		}
		int id = mid;
		while(id > p && Ask(id)[0] + Ask(id)[1] >= Me)
		{
			id = FindLeft(id);
		}
		if(id == p)
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	return Ans[1][p] = r;
}

int find_best(int _n)
{
	memset(Ans, -1, sizeof Ans);
	n = _n;
	int p = 0;
	while(Ask(p)[0] + Ask(p)[1])
	{
		p = FindRight(p);
	}
	return p;
}

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