Submission #1012199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012199		Tob	The Big Prize (IOI17_prize)	C++14	100 / 100	26 ms	5560 KiB

prize

#include <bits/stdc++.h>

#include "prize.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int val(int x) {
	uniform_int_distribution <int> rnd(0, x-1);
	return rnd(rng);
}
/*
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;
}
*/
const int B = 250, N = 2e5 + 7;
vector <int> ans[N];

vector <int> Ask(int x) {
	if (ans[x].empty()) ans[x] = ask(x);
	return ans[x];
}

int find_best(int n) {
	vector <int> x, v;
	int d = 0, la = -1, cnt = 0;
	for (int i = 0; i < n; i += B) {
		x = Ask(min(i+B, n)-1);
		d = max(d, x[0]+x[1]);
	}
	for (int i = 0; i < min(n, max(0, 510-n/B)); i++) {
		x = Ask(i);
		d = max(d, x[0]+x[1]);
	}
	for (int i = 0; i < n; i += B) {
		int l = i, r = min(i+B, n)-1;
		x = Ask(r);
		int cnt2 = 0;
		while (x[0] + x[1] < d && r >= l) {
			if (x[0]+x[1] == 0) return r;
			r--;
			cnt2++;
			if (l <= r) x = Ask(r);
		}
		int z = 0;
		if (l <= r) z = x[0]-cnt;
		while (z--) {
			int lo = l, hi = r;
			while (lo < hi) {
				int mid = (lo + hi) / 2;
				x = Ask(mid);
				if (x[0] + x[1] < d || x[0] > cnt) hi = mid;
				else lo = mid+1;
			}
			x = Ask(lo);
			if (x[0]+x[1] == 0) return lo;
			cnt++;
			l = lo+1;
		}
		cnt += cnt2;
	}
	
	return 0;
}
/*
int main() {
	n = 2e5;
//	cin >> n;
	vector <int> v, u;
	v.pb(1);
	ll sum = 1;
	for (int i = 0; sum <= n; i++) {
		ll x = v.back();
		ll kol = (ll)x*x+1+val(3);
		if (sum+kol > n) {
			v[v.size()-1] += n-sum;
			break;
		}
		else {
			v.pb(kol);
			sum += kol;
		}		
	}
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v[i]; j++) u.pb(i+1);
	}
	shuffle(all(u), rng);

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

	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;
}
*/

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:56:13: warning: unused variable 'la' [-Wunused-variable]
   56 |  int d = 0, la = -1, cnt = 0;
      |             ^~

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