Submission #832400

#	Time	Username	Problem	Language	Result	Execution time	Memory
832400		MadokaMagicaFan	The Big Prize (IOI17_prize)	C++14	20 / 100	51 ms	3616 KiB

prize

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define sz(v) ((int)v.size())
#define pb push_back
#ifdef ONPC
vector<int> p;
vector<int> ask(int x);
#else
#include "prize.h"
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int lv[1000];
int al[200005], ar[200005], a[200005];

void g(int x) {
	if (a[x]) return;
	a[x] = 1;
	auto u = ask(x);
	al[x] = u[0];
	ar[x] = u[1];
	lv[al[x]] = min(lv[al[x]], x);
}


int find_best(int n) {
	for (int i = 0; i < 1000; ++i)
		lv[i] = n+2;
	vector<int> rs(n);
	iota(rs.begin(), rs.end(), 0);
	shuffle(rs.begin(), rs.end(), rng);
	int cn = 0;
	for (int i = 0; i < min(n,400); ++i) {
		g(rs[i]);
		cn = max(cn, al[rs[i]] + ar[rs[i]]);
	}
	

	vector<int> sp;
	for (int i = 1; i <= cn; ++i) {
		int l = (i > 1) ? sp.back()+1 : 0;
		int r = n;
		for (int j = i; j <= cn; ++j)
			r = min(r, lv[j]);

		while (l < r) {
			int m = (l+r)/2;
			g(m);
			if (al[m] + ar[m] < cn || al[m] >= i)
				r = m;
			else
				l = m+1;
		}

		sp.pb(l);
	}

	assert(sz(sp) == cn);

	for (auto x : sp) {
		g(x); if (al[x] == 0 && ar[x] == 0) return x;
	}

	return -1;
}


#ifdef ONPC
vector<int> ask(int x) {
	vector<int> r(2,0);
	for (int i = 0; i < x; ++i) if (p[i] < p[x]) ++r[0];
	for (int i = x+1; i < sz(p); ++i) if (p[i] < p[x]) ++r[1];
	return r;
}

int main() {
	int n;
	cin >>n; p.resize(n);
	for (int i = 0; i < n; ++i)
		cin >> p[i];

	cout << find_best(n) << endl;
}
#endif

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