oj.uz

Submission #936650

# Submission time Handle Problem Language Result Execution time Memory
936650 2024-03-02T12:41:49 Z Ghetto The Big Prize (IOI17_prize) C++17
92.42 / 100
 31 ms 756 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n;

int v_sum;
int find_v_sum() {
	unordered_map<int, int> sum_freq;
	for (int i = 0; i < min(n, 1000); i++) {
		vector<int> res = ask(i);
		sum_freq[res[0] + res[1]]++;
	}

	for (pii sf : sum_freq)
		if (sf.second >= min(n / 2, 500)) return sf.first;
	assert(true == false); 
}

bool is_v(int res_sum) {
	return res_sum == v_sum;
}

vector<int> append(vector<int> v1, vector<int> v2) {
	v1.insert(v1.end(), v2.begin(), v2.end());
	return v1;
}

int find_one(int lo, int hi, int l, int r) { // -1 if none
	// cout << "CALL " << lo << " " << hi << " " << l << " " << r << endl;
	if (lo > hi) return -1; 

	vector<int> res;
	int l_mid = (lo + hi) / 2, r_mid = (lo + hi) / 2;
	while (r_mid <= hi) {
		res = ask(r_mid);

		if (is_v(res[0] + res[1])) break;
		if (res[0] + res[1] == 0) return r_mid;
		r_mid++;
	}
	if (r_mid == hi + 1) return find_one(lo, l_mid - 1, l, r + r_mid - l_mid);

	int l_size = res[0] - l - (r_mid - l_mid);
	int r_size = res[1] - r;
	// cout << "DETAILS " << l_mid << " " << r_mid << " " << l_size << " " << r_size << endl;
	assert(min(l_size, r_size) >= 0);	

	if (l_size == 0 && r_size == 0) return -1;
	else if (l_size == 0) return find_one(r_mid + 1, hi, l + r_mid - l_mid, r);
	else if (r_size == 0) return find_one(lo, l_mid - 1, l, r + r_mid - l_mid);
	return max(find_one(lo, l_mid - 1, l, r + r_size + r_mid - l_mid), find_one(r_mid + 1, hi, l + l_size + r_mid - l_mid, r)); 
}

int find_best(int tmp_n) {
	n = tmp_n;

	v_sum = find_v_sum();

	int ans = find_one(0, n - 1, 0, 0);
	assert(ans != -1);
	return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 344 KB Output is correct

Subtask #2
72.42 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 6 ms 344 KB Output is correct
13 Correct 8 ms 596 KB Output is correct
14 Correct 10 ms 344 KB Output is correct
15 Partially correct 22 ms 344 KB Partially correct - number of queries: 5240
16 Partially correct 24 ms 344 KB Partially correct - number of queries: 5489
17 Partially correct 24 ms 600 KB Partially correct - number of queries: 5455
18 Partially correct 20 ms 344 KB Partially correct - number of queries: 5469
19 Partially correct 23 ms 344 KB Partially correct - number of queries: 5200
20 Correct 16 ms 344 KB Output is correct
21 Partially correct 23 ms 600 KB Partially correct - number of queries: 5451
22 Correct 26 ms 344 KB Output is correct
23 Correct 4 ms 344 KB Output is correct
24 Correct 7 ms 344 KB Output is correct
25 Partially correct 21 ms 344 KB Partially correct - number of queries: 5054
26 Partially correct 21 ms 344 KB Partially correct - number of queries: 5054
27 Correct 5 ms 344 KB Output is correct
28 Correct 21 ms 344 KB Output is correct
29 Correct 18 ms 344 KB Output is correct
30 Partially correct 23 ms 756 KB Partially correct - number of queries: 5430
31 Partially correct 22 ms 344 KB Partially correct - number of queries: 5435
32 Correct 5 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Partially correct 24 ms 428 KB Partially correct - number of queries: 5487
35 Correct 4 ms 344 KB Output is correct
36 Partially correct 25 ms 344 KB Partially correct - number of queries: 5401
37 Correct 5 ms 344 KB Output is correct
38 Correct 7 ms 344 KB Output is correct
39 Partially correct 24 ms 344 KB Partially correct - number of queries: 5389
40 Correct 21 ms 344 KB Output is correct
41 Partially correct 29 ms 344 KB Partially correct - number of queries: 5435
42 Partially correct 27 ms 344 KB Partially correct - number of queries: 5435
43 Partially correct 25 ms 344 KB Partially correct - number of queries: 5354
44 Partially correct 26 ms 344 KB Partially correct - number of queries: 5478
45 Partially correct 24 ms 344 KB Partially correct - number of queries: 5036
46 Partially correct 28 ms 344 KB Partially correct - number of queries: 5466
47 Partially correct 23 ms 344 KB Partially correct - number of queries: 5136
48 Partially correct 23 ms 344 KB Partially correct - number of queries: 5449
49 Partially correct 25 ms 344 KB Partially correct - number of queries: 5438
50 Partially correct 21 ms 344 KB Partially correct - number of queries: 5463
51 Partially correct 29 ms 600 KB Partially correct - number of queries: 5454
52 Partially correct 23 ms 344 KB Partially correct - number of queries: 5468
53 Correct 5 ms 540 KB Output is correct
54 Partially correct 25 ms 344 KB Partially correct - number of queries: 5453
55 Partially correct 24 ms 344 KB Partially correct - number of queries: 5465
56 Partially correct 21 ms 344 KB Partially correct - number of queries: 5475
57 Partially correct 28 ms 344 KB Partially correct - number of queries: 5439
58 Partially correct 19 ms 596 KB Partially correct - number of queries: 5444
59 Partially correct 23 ms 344 KB Partially correct - number of queries: 5439
60 Partially correct 31 ms 344 KB Partially correct - number of queries: 5425
61 Correct 4 ms 344 KB Output is correct
62 Correct 5 ms 344 KB Output is correct
63 Correct 4 ms 344 KB Output is correct
64 Correct 4 ms 344 KB Output is correct
65 Correct 4 ms 344 KB Output is correct
66 Correct 6 ms 344 KB Output is correct
67 Correct 6 ms 344 KB Output is correct
68 Correct 4 ms 344 KB Output is correct
69 Correct 6 ms 344 KB Output is correct
70 Correct 6 ms 344 KB Output is correct
71 Partially correct 28 ms 596 KB Partially correct - number of queries: 5758
72 Correct 6 ms 344 KB Output is correct
73 Partially correct 26 ms 344 KB Partially correct - number of queries: 5695
74 Partially correct 31 ms 344 KB Partially correct - number of queries: 5722
75 Correct 4 ms 344 KB Output is correct
76 Partially correct 22 ms 344 KB Partially correct - number of queries: 5110
77 Partially correct 29 ms 344 KB Partially correct - number of queries: 5449
78 Correct 7 ms 344 KB Output is correct
79 Correct 18 ms 344 KB Output is correct
80 Partially correct 24 ms 344 KB Partially correct - number of queries: 5511
81 Partially correct 28 ms 344 KB Partially correct - number of queries: 5452
82 Partially correct 27 ms 344 KB Partially correct - number of queries: 5440
83 Correct 4 ms 344 KB Output is correct
84 Correct 25 ms 344 KB Output is correct
85 Partially correct 26 ms 344 KB Partially correct - number of queries: 5479
86 Correct 6 ms 344 KB Output is correct
87 Correct 5 ms 344 KB Output is correct
88 Correct 6 ms 344 KB Output is correct
89 Correct 6 ms 344 KB Output is correct
90 Correct 6 ms 596 KB Output is correct
91 Correct 5 ms 344 KB Output is correct
92 Correct 8 ms 344 KB Output is correct
93 Correct 10 ms 344 KB Output is correct
94 Correct 7 ms 344 KB Output is correct
95 Correct 8 ms 344 KB Output is correct
96 Correct 6 ms 344 KB Output is correct
97 Correct 7 ms 344 KB Output is correct