Submission #169927

#	Time	Username	Problem	Language	Result	Execution time	Memory
169927		dennisstar	The Big Prize (IOI17_prize)	C++11	100 / 100	53 ms	2204 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;


int N;
set<pair<int, pii> > S[10]; int val[10], tp;

int ans, fl, chk[200010], ar[200010];

int f(int v) {
	for (int i=0; i<tp; i++) if (val[i]==v) return i;
	val[tp]=v; return tp++;
}

void myfind(int s, int e) {
	if (s>e) return ;
	int md=(s+e)/2;
	if (chk[md]) return ;
	chk[md]=1;
	vim res=ask(md);
	ar[md]=res[0]+res[1];
	if (res[0]==0&&res[1]==0) {
		ans=md;
		fl=1;
		return ;
	}
	int ind=f(ar[md]);
	S[ind].insert({md, make_pair(res[0], res[1])});

	auto it=S[ind].find({md, make_pair(res[0], res[1])});
	pair<int, pii> p=(*it), pr, ne;
	if (it==S[ind].begin()) pr={-1, make_pair(0, ar[md])};
	else pr=*prev(it);
	if (next(it)==S[ind].end()) ne={N, make_pair(ar[md], 0)};
	else ne=*next(it);
	if (pr.se.fi!=p.se.fi) myfind(max(s, pr.fi+1), p.fi-1);
	if (fl) return ;
	if (p.se.fi!=ne.se.fi) myfind(p.fi+1, min(e, ne.fi-1));
}

int find_best(int n) {
	N=n;
	myfind(0, n-1);
	return ans;
}

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