oj.uz

Submission #1012165

# Submission time Handle Problem Language Result Execution time Memory
1012165 2024-07-01T18:36:29 Z Tob The Big Prize (IOI17_prize) C++14
20 / 100
 31 ms 5456 KB 
#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 < 500; 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 4 ms 4952 KB Output is correct
2 Correct 5 ms 5200 KB Output is correct
3 Correct 7 ms 5148 KB Output is correct
4 Correct 7 ms 5208 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 4952 KB Output is correct
8 Correct 5 ms 4952 KB Output is correct
9 Correct 6 ms 4952 KB Output is correct
10 Correct 7 ms 5144 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 7 ms 4952 KB Output is correct
3 Correct 7 ms 4952 KB Output is correct
4 Correct 5 ms 5136 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 5152 KB Output is correct
8 Correct 6 ms 4952 KB Output is correct
9 Correct 6 ms 5164 KB Output is correct
10 Correct 11 ms 4952 KB Output is correct
11 Correct 5 ms 4952 KB Output is correct
12 Correct 4 ms 4952 KB Output is correct
13 Correct 9 ms 4952 KB Output is correct
14 Correct 7 ms 4952 KB Output is correct
15 Correct 10 ms 5128 KB Output is correct
16 Correct 20 ms 5428 KB Output is correct
17 Correct 4 ms 4952 KB Output is correct
18 Partially correct 24 ms 5196 KB Partially correct - number of queries: 5058
19 Correct 3 ms 4952 KB Output is correct
20 Correct 10 ms 4952 KB Output is correct
21 Correct 13 ms 5420 KB Output is correct
22 Correct 5 ms 4952 KB Output is correct
23 Correct 4 ms 5128 KB Output is correct
24 Correct 4 ms 4952 KB Output is correct
25 Correct 26 ms 5208 KB Output is correct
26 Correct 10 ms 5208 KB Output is correct
27 Correct 5 ms 5208 KB Output is correct
28 Correct 14 ms 5260 KB Output is correct
29 Correct 15 ms 5456 KB Output is correct
30 Partially correct 31 ms 5208 KB Partially correct - number of queries: 5028
31 Correct 4 ms 4952 KB Output is correct
32 Correct 8 ms 5208 KB Output is correct
33 Incorrect 3 ms 4952 KB Integer 100 violates the range [0, 99]
34 Halted 0 ms 0 KB -