oj.uz

Submission #1060626

# Submission time Handle Problem Language Result Execution time Memory
1060626 2024-08-15T19:48:04 Z TAhmed33 The Big Prize (IOI17_prize) C++
90 / 100
 53 ms 1984 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
pair <int, int> memo[200001];
int ans;
pair <int, int> get (int x) {
	if (memo[x].first != -1) {
		return memo[x];
	}
	auto h = ask(x);
	pair <int, int> g = {h[0], h[1]};
	if (g.first + g.second == 0) {
		ans = x;
	}
	return memo[x] = g;
}
void solve (int l, int r) {
	if (l == r) {
		get(l);
		return;
	}
	auto less = [&] (int x, int y) -> bool {
		return get(x).first + get(x).second < get(y).first + get(y).second;
	};
	while (less(l, r) || less(r, l)) {
		while (less(l, r)) l++;
		while (less(r, l)) r--;
	}
	if (get(l).second == get(r).second) {
		return;
	}
	int mid = (l + r) / 2;
	solve(l, mid); solve(mid + 1, r);
}
int find_best (int n) {
	ans = -1;
	for (int i = 0; i < n; i++) {
		memo[i] = {-1, -1};
	}
	solve(0, n - 1);
	return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1880 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 1 ms 1876 KB Output is correct
10 Correct 1 ms 1880 KB Output is correct
11 Correct 4 ms 1876 KB Output is correct
12 Correct 4 ms 1880 KB Output is correct
13 Correct 4 ms 1880 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Partially correct 37 ms 1972 KB Partially correct - number of queries: 7059
16 Partially correct 45 ms 1880 KB Partially correct - number of queries: 7472
17 Partially correct 49 ms 1880 KB Partially correct - number of queries: 7467
18 Partially correct 44 ms 1880 KB Partially correct - number of queries: 7519
19 Partially correct 36 ms 1880 KB Partially correct - number of queries: 7127
20 Correct 18 ms 1112 KB Output is correct
21 Partially correct 35 ms 1880 KB Partially correct - number of queries: 7449
22 Partially correct 21 ms 1880 KB Partially correct - number of queries: 5786
23 Correct 2 ms 1880 KB Output is correct
24 Correct 4 ms 1880 KB Output is correct
25 Partially correct 32 ms 1880 KB Partially correct - number of queries: 6783
26 Partially correct 39 ms 1880 KB Partially correct - number of queries: 6679
27 Correct 2 ms 1880 KB Output is correct
28 Partially correct 29 ms 1880 KB Partially correct - number of queries: 6744
29 Partially correct 31 ms 1880 KB Partially correct - number of queries: 5688
30 Partially correct 44 ms 1880 KB Partially correct - number of queries: 7475
31 Partially correct 38 ms 1880 KB Partially correct - number of queries: 7398
32 Correct 4 ms 1880 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Partially correct 47 ms 1980 KB Partially correct - number of queries: 7509
35 Correct 2 ms 1880 KB Output is correct
36 Partially correct 34 ms 1880 KB Partially correct - number of queries: 7554
37 Correct 4 ms 1880 KB Output is correct
38 Correct 2 ms 1880 KB Output is correct
39 Partially correct 46 ms 1880 KB Partially correct - number of queries: 7478
40 Partially correct 33 ms 1880 KB Partially correct - number of queries: 6513
41 Partially correct 44 ms 1880 KB Partially correct - number of queries: 7494
42 Partially correct 53 ms 1880 KB Partially correct - number of queries: 7494
43 Partially correct 28 ms 1880 KB Partially correct - number of queries: 7300
44 Partially correct 32 ms 1880 KB Partially correct - number of queries: 7472
45 Partially correct 30 ms 1880 KB Partially correct - number of queries: 6687
46 Partially correct 38 ms 1880 KB Partially correct - number of queries: 7512
47 Partially correct 34 ms 1880 KB Partially correct - number of queries: 6807
48 Partially correct 40 ms 1880 KB Partially correct - number of queries: 7476
49 Partially correct 39 ms 1880 KB Partially correct - number of queries: 7549
50 Partially correct 42 ms 1880 KB Partially correct - number of queries: 7480
51 Partially correct 41 ms 1880 KB Partially correct - number of queries: 7488
52 Partially correct 38 ms 1976 KB Partially correct - number of queries: 7544
53 Correct 2 ms 1880 KB Output is correct
54 Partially correct 30 ms 1880 KB Partially correct - number of queries: 7463
55 Partially correct 44 ms 1880 KB Partially correct - number of queries: 7522
56 Partially correct 34 ms 1880 KB Partially correct - number of queries: 7565
57 Partially correct 25 ms 1880 KB Partially correct - number of queries: 7503
58 Partially correct 33 ms 1880 KB Partially correct - number of queries: 7507
59 Partially correct 41 ms 1880 KB Partially correct - number of queries: 7536
60 Partially correct 46 ms 1880 KB Partially correct - number of queries: 7483
61 Correct 2 ms 1880 KB Output is correct
62 Correct 2 ms 1880 KB Output is correct
63 Correct 2 ms 1880 KB Output is correct
64 Correct 2 ms 1880 KB Output is correct
65 Correct 1 ms 1880 KB Output is correct
66 Correct 3 ms 1880 KB Output is correct
67 Correct 3 ms 1880 KB Output is correct
68 Correct 3 ms 1880 KB Output is correct
69 Correct 3 ms 1968 KB Output is correct
70 Correct 2 ms 1880 KB Output is correct
71 Partially correct 36 ms 1880 KB Partially correct - number of queries: 8104
72 Correct 4 ms 1880 KB Output is correct
73 Partially correct 34 ms 1880 KB Partially correct - number of queries: 7999
74 Partially correct 38 ms 1876 KB Partially correct - number of queries: 8044
75 Correct 2 ms 1880 KB Output is correct
76 Partially correct 35 ms 1880 KB Partially correct - number of queries: 7024
77 Partially correct 41 ms 1880 KB Partially correct - number of queries: 7264
78 Correct 4 ms 1880 KB Output is correct
79 Correct 14 ms 1880 KB Output is correct
80 Partially correct 36 ms 1880 KB Partially correct - number of queries: 7326
81 Partially correct 42 ms 1880 KB Partially correct - number of queries: 7196
82 Partially correct 42 ms 1880 KB Partially correct - number of queries: 7258
83 Correct 2 ms 1880 KB Output is correct
84 Partially correct 22 ms 1880 KB Partially correct - number of queries: 6078
85 Partially correct 48 ms 1880 KB Partially correct - number of queries: 7270
86 Correct 2 ms 1880 KB Output is correct
87 Correct 1 ms 1880 KB Output is correct
88 Correct 3 ms 1880 KB Output is correct
89 Correct 3 ms 1876 KB Output is correct
90 Correct 1 ms 1880 KB Output is correct
91 Correct 2 ms 1880 KB Output is correct
92 Correct 1 ms 1880 KB Output is correct
93 Correct 3 ms 1880 KB Output is correct
94 Correct 4 ms 1880 KB Output is correct
95 Correct 5 ms 1880 KB Output is correct
96 Correct 3 ms 1880 KB Output is correct
97 Correct 1 ms 1880 KB Output is correct