Submission #104547

#	Time	Username	Problem	Language	Result	Execution time	Memory
104547		KCSC	The Big Prize (IOI17_prize)	C++14	20 / 100	79 ms	904 KiB

prize

#ifndef HOME
	#include "prize.h"
#endif

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

#ifdef HOME

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;

vector<int> ask(int i) {
	query_count++;
	if(query_count > max_q) {
		cerr << "Query limit exceeded" << endl;
		exit(0);
	}

	if(i < 0 || i >= n) {
		cerr << "Bad index: " << i << endl;
		exit(0);
	}

	vector<int> res(2);
	res[0] = rank_count[g[i] - 1][i + 1];
	res[1] = rank_count[g[i] - 1][n] - res[0];
	return res;
}
#endif

map<int, pair<int, int>> mmp;

pair<int, int> _ask(int p) {
	--p;
	if (mmp.find(p) != mmp.end()) {
		return mmp[p]; }
	vector<int> aux = ask(p);
	pair<int, int> pr(aux[0], aux[1]);
	return mmp[p] = pr; }

void solve(int le, int ri, int nr, int tot, int lef, int rig, bool &ok, int &ps) {
	if (ok or !nr or le > ri) {
		return; }
	int md, nps; pair<int, int> pr;
	if (le == ri) {
		pr = _ask(le);
		if (pr.first + pr.second == 0) {
			ps = le; ok = true; } }
	else {
		md = (le + ri) / 2, nps = md;
		for (; nps >= le; --nps) {
			pr = _ask(nps);
			if (pr.first + pr.second == 0) {
				ps = nps; ok = true; return; }
			if (pr.first + pr.second == tot) {
				solve(le, nps - 1, pr.first - lef, tot, lef, pr.second, ok, ps);
				solve(md + 1, ri, pr.second - (md - nps) - rig, tot, pr.first + (md - nps), rig, ok, ps);
				return; } }
		solve(md + 1, ri, nr - (md - le + 1), tot, lef + (md - le + 1), rig, ok, ps); } }
			
int find_best(int n) {
	int nr = 0, ps;
	for (int i = 1; i <= min(450, n); ++i) {
		pair<int, int> pr = _ask(i); 
		if (pr.first + pr.second == 0) {
			return i - 1; }
		if (nr < pr.first + pr.second) {
			nr = pr.first + pr.second; ps = i; } }
	bool ok = false; 
	solve(ps + 1, n, nr - (ps - 1), nr, ps - 1, 0, ok, ps);
	return ps - 1; } 	

#ifdef HOME
int main() {
	freopen("prize.in", "r", stdin);
	freopen("prize.out", "w", stdout);
	cin >> n;

	g.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> g[i];
		if(g[i] < 1) {
			cerr << "Invalid rank " << g[i] << " at index " << i << endl;
			exit(0);
		}
	}

	int max_rank = *max_element(g.begin(), g.end());

	rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
	for(int r = 0; r <= max_rank; r++) {
		for(int i = 1; i <= n; i++) {
			rank_count[r][i] = rank_count[r][i - 1];
			if(g[i - 1] == r)
			  rank_count[r][i]++;
		}
	}

	for(int i = 0; i <= n; i++)
		for(int r = 1; r <= max_rank; r++)
			rank_count[r][i] += rank_count[r - 1][i];

	int res = find_best(n);
	cout << res << endl << "Query count: " << query_count << endl;

	return 0;
}
#endif

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