Submission #1012167

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1012167	2024-07-01T18:37:52 Z	Tob	The Big Prize (IOI17_prize)	C++14	20 / 100	26 ms	5708 KB

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 < 550; 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);
		while (x[0] + x[1] < d && r >= l) {
			if (x[0]+x[1] == 0) return r;
			r--;
			if (l <= r) x = Ask(r);
		}
		if (l > r) continue;
		int 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;
		}
	}
	
	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

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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4952 KB	Output is correct
2	Correct	7 ms	5156 KB	Output is correct
3	Correct	6 ms	5208 KB	Output is correct
4	Correct	8 ms	4952 KB	Output is correct
5	Correct	5 ms	4952 KB	Output is correct
6	Correct	4 ms	4948 KB	Output is correct
7	Correct	6 ms	5208 KB	Output is correct
8	Correct	7 ms	5400 KB	Output is correct
9	Correct	6 ms	4952 KB	Output is correct
10	Correct	7 ms	5152 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4952 KB	Output is correct
2	Correct	6 ms	4952 KB	Output is correct
3	Correct	6 ms	4952 KB	Output is correct
4	Correct	8 ms	4952 KB	Output is correct
5	Correct	6 ms	4952 KB	Output is correct
6	Correct	4 ms	4952 KB	Output is correct
7	Correct	5 ms	4956 KB	Output is correct
8	Correct	6 ms	5204 KB	Output is correct
9	Correct	6 ms	4952 KB	Output is correct
10	Correct	8 ms	4952 KB	Output is correct
11	Correct	8 ms	4952 KB	Output is correct
12	Correct	5 ms	4952 KB	Output is correct
13	Correct	9 ms	5160 KB	Output is correct
14	Correct	6 ms	4952 KB	Output is correct
15	Correct	8 ms	4952 KB	Output is correct
16	Correct	19 ms	5440 KB	Output is correct
17	Correct	4 ms	4952 KB	Output is correct
18	Partially correct	25 ms	5164 KB	Partially correct - number of queries: 5108
19	Correct	4 ms	4952 KB	Output is correct
20	Correct	9 ms	4952 KB	Output is correct
21	Correct	10 ms	4952 KB	Output is correct
22	Correct	5 ms	4952 KB	Output is correct
23	Correct	4 ms	4952 KB	Output is correct
24	Correct	5 ms	4952 KB	Output is correct
25	Correct	19 ms	5396 KB	Output is correct
26	Correct	17 ms	5208 KB	Output is correct
27	Correct	6 ms	4952 KB	Output is correct
28	Correct	26 ms	5708 KB	Output is correct
29	Correct	15 ms	5480 KB	Output is correct
30	Partially correct	20 ms	5208 KB	Partially correct - number of queries: 5078
31	Correct	4 ms	4952 KB	Output is correct
32	Correct	13 ms	5208 KB	Output is correct
33	Incorrect	2 ms	4952 KB	Integer 100 violates the range [0, 99]
34	Halted	0 ms	0 KB	-