Submission #574539

# Submission time Handle Problem Language Result Execution time Memory
574539 2022-06-08T18:52:28 Z valerikk The Big Prize (IOI17_prize) C++17
90 / 100
90 ms 344 KB
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

int mx_cnt;

}

int solve(int l, int r, vector<int> h, int f) {
	if (l > r) 
		return -1;

	if (l == r) {
		auto a = f == 0 ? h : ask(l);
		if (a[0] + a[1] == 0)
			return l;
		return -1;
	}

	auto al = f == 0 ? h : ask(l);
	auto ar = f == 1 ? h : ask(r);

	if (al[0] + al[1] == 0)
		return l;
	if (ar[0] + ar[1] == 0)
		return r;

	if (al[0] + al[1] == mx_cnt && ar[0] + ar[1] == mx_cnt && al[0] == ar[0]) 
		return -1;

	int m = (l + r) / 2;

	return max(solve(l, m, al, 0), solve(m + 1, r, ar, 1));
}	

int find_best(int n) {
	mx_cnt = 0;

	for (int i = 0; i < min(n, 500); ++i) {
		auto a = ask(i);

		if (a[0] + a[1] == 0)
			return i;

		mx_cnt = max(mx_cnt, a[0] + a[1]);
	}

	return solve(0, n - 1, {}, -1);
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 3 ms 292 KB Output is correct
4 Correct 3 ms 292 KB Output is correct
5 Correct 6 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 3 ms 292 KB Output is correct
8 Correct 3 ms 296 KB Output is correct
9 Correct 3 ms 208 KB Output is correct
10 Correct 5 ms 208 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 288 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 5 ms 296 KB Output is correct
5 Correct 5 ms 292 KB Output is correct
6 Correct 0 ms 284 KB Output is correct
7 Correct 4 ms 292 KB Output is correct
8 Correct 3 ms 208 KB Output is correct
9 Correct 3 ms 284 KB Output is correct
10 Correct 4 ms 208 KB Output is correct
11 Correct 14 ms 208 KB Output is correct
12 Correct 9 ms 208 KB Output is correct
13 Correct 10 ms 296 KB Output is correct
14 Correct 20 ms 208 KB Output is correct
15 Partially correct 66 ms 288 KB Partially correct - number of queries: 8957
16 Partially correct 76 ms 280 KB Partially correct - number of queries: 9402
17 Correct 4 ms 208 KB Output is correct
18 Partially correct 83 ms 280 KB Partially correct - number of queries: 9402
19 Correct 2 ms 272 KB Output is correct
20 Partially correct 33 ms 300 KB Partially correct - number of queries: 6286
21 Partially correct 90 ms 284 KB Partially correct - number of queries: 9332
22 Partially correct 62 ms 292 KB Partially correct - number of queries: 7305
23 Correct 8 ms 288 KB Output is correct
24 Correct 11 ms 288 KB Output is correct
25 Partially correct 59 ms 276 KB Partially correct - number of queries: 8623
26 Partially correct 88 ms 208 KB Partially correct - number of queries: 8643
27 Correct 7 ms 284 KB Output is correct
28 Partially correct 60 ms 288 KB Partially correct - number of queries: 8549
29 Partially correct 74 ms 292 KB Partially correct - number of queries: 7311
30 Partially correct 37 ms 344 KB Partially correct - number of queries: 9332
31 Correct 4 ms 208 KB Output is correct
32 Correct 11 ms 272 KB Output is correct
33 Correct 0 ms 208 KB Output is correct
34 Partially correct 81 ms 288 KB Partially correct - number of queries: 9406
35 Correct 11 ms 284 KB Output is correct
36 Partially correct 63 ms 208 KB Partially correct - number of queries: 9342
37 Correct 13 ms 208 KB Output is correct
38 Correct 7 ms 280 KB Output is correct
39 Partially correct 55 ms 288 KB Partially correct - number of queries: 9331
40 Partially correct 70 ms 292 KB Partially correct - number of queries: 8193
41 Partially correct 77 ms 208 KB Partially correct - number of queries: 9410
42 Partially correct 71 ms 292 KB Partially correct - number of queries: 9410
43 Partially correct 33 ms 336 KB Partially correct - number of queries: 9145
44 Partially correct 71 ms 208 KB Partially correct - number of queries: 9391
45 Partially correct 73 ms 280 KB Partially correct - number of queries: 8590
46 Correct 3 ms 268 KB Output is correct
47 Partially correct 81 ms 276 KB Partially correct - number of queries: 8704
48 Partially correct 79 ms 208 KB Partially correct - number of queries: 9406
49 Partially correct 35 ms 280 KB Partially correct - number of queries: 9395
50 Partially correct 64 ms 208 KB Partially correct - number of queries: 9395
51 Partially correct 79 ms 288 KB Partially correct - number of queries: 9395
52 Partially correct 77 ms 280 KB Partially correct - number of queries: 9387
53 Correct 8 ms 208 KB Output is correct
54 Partially correct 75 ms 208 KB Partially correct - number of queries: 9325
55 Correct 4 ms 208 KB Output is correct
56 Partially correct 76 ms 296 KB Partially correct - number of queries: 9387
57 Partially correct 77 ms 268 KB Partially correct - number of queries: 9333
58 Partially correct 70 ms 292 KB Partially correct - number of queries: 9418
59 Partially correct 68 ms 208 KB Partially correct - number of queries: 9414
60 Partially correct 64 ms 208 KB Partially correct - number of queries: 9339
61 Correct 5 ms 268 KB Output is correct
62 Correct 7 ms 208 KB Output is correct
63 Correct 6 ms 280 KB Output is correct
64 Correct 5 ms 280 KB Output is correct
65 Correct 3 ms 300 KB Output is correct
66 Correct 13 ms 292 KB Output is correct
67 Correct 9 ms 272 KB Output is correct
68 Correct 5 ms 208 KB Output is correct
69 Correct 6 ms 296 KB Output is correct
70 Correct 7 ms 208 KB Output is correct
71 Partially correct 77 ms 292 KB Partially correct - number of queries: 9547
72 Correct 12 ms 208 KB Output is correct
73 Partially correct 85 ms 208 KB Partially correct - number of queries: 9428
74 Partially correct 87 ms 300 KB Partially correct - number of queries: 9479
75 Correct 6 ms 208 KB Output is correct
76 Partially correct 66 ms 300 KB Partially correct - number of queries: 8323
77 Partially correct 50 ms 300 KB Partially correct - number of queries: 9390
78 Correct 9 ms 292 KB Output is correct
79 Correct 48 ms 296 KB Output is correct
80 Partially correct 81 ms 208 KB Partially correct - number of queries: 9430
81 Partially correct 90 ms 300 KB Partially correct - number of queries: 9436
82 Partially correct 70 ms 208 KB Partially correct - number of queries: 9342
83 Correct 8 ms 208 KB Output is correct
84 Partially correct 31 ms 300 KB Partially correct - number of queries: 7937
85 Partially correct 68 ms 296 KB Partially correct - number of queries: 9404
86 Correct 7 ms 208 KB Output is correct
87 Correct 6 ms 208 KB Output is correct
88 Correct 12 ms 208 KB Output is correct
89 Correct 9 ms 208 KB Output is correct
90 Correct 6 ms 288 KB Output is correct
91 Correct 7 ms 296 KB Output is correct
92 Correct 10 ms 208 KB Output is correct
93 Correct 20 ms 208 KB Output is correct
94 Correct 21 ms 208 KB Output is correct
95 Correct 18 ms 300 KB Output is correct
96 Correct 18 ms 300 KB Output is correct
97 Correct 13 ms 300 KB Output is correct