oj.uz

Submission #64591

# Submission time Handle Problem Language Result Execution time Memory
64591 2018-08-05T02:09:39 Z nvmdava The Big Prize (IOI17_prize) C++17
20 / 100
 143 ms 5940 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
 
 
vector<int> ans[210000];
int mx = -1;
int find(int l, int r){
	if(ans[l][0] == ans[r][0]){
		return 0;
	}
	int m = (l + r) >> 1, L = m, R = m + 1;
	while(l < L){
		ans[L] =ask(L);
		if(ans[L][0] + ans[L][1] == mx){
			break;
		}
		if(ans[L][0] + ans[L][1] == 0){
			return L;
		}
		L--;
	}
	while(r > R){
		ans[R] =ask(R);
		if(ans[R][0] + ans[R][1] == mx){
			break;
		}
		if(ans[R][0] + ans[R][1] == 0){
			return R;
		}
		R++;
	}
	return max(find(l, L), find(R, r));
}
 
int find_best(int n) {
	for(int i = 0; i < 448; i++){
		ans[i] = ask(i);
		if(ans[i][0] + ans[i][1] == 0){
			return i;
		}
		mx = max(mx, ans[i][0] + ans[i][1]);
	}
	int l = 0, r = n - 1;
	while(true){
		if(ans[l][0] + ans[l][1] == mx){
			break;
		}
		l++;
	}
	while(true){
		
		ans[r] = ask(r);
		
		if(ans[r][0] + ans[r][1] == mx){
			break;
		}
		if(ans[r][0] + ans[r][1] == 0){
			return r;
		}
		r--;
	}
	return find(l, r);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5384 KB Output is correct
2 Correct 11 ms 5432 KB Output is correct
3 Correct 10 ms 5432 KB Output is correct
4 Correct 10 ms 5456 KB Output is correct
5 Correct 10 ms 5456 KB Output is correct
6 Correct 7 ms 5456 KB Output is correct
7 Correct 14 ms 5488 KB Output is correct
8 Correct 10 ms 5568 KB Output is correct
9 Correct 10 ms 5568 KB Output is correct
10 Correct 10 ms 5568 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5568 KB Output is correct
2 Correct 8 ms 5568 KB Output is correct
3 Correct 15 ms 5568 KB Output is correct
4 Correct 23 ms 5572 KB Output is correct
5 Correct 18 ms 5572 KB Output is correct
6 Correct 9 ms 5572 KB Output is correct
7 Correct 15 ms 5572 KB Output is correct
8 Correct 10 ms 5572 KB Output is correct
9 Correct 15 ms 5572 KB Output is correct
10 Correct 17 ms 5572 KB Output is correct
11 Correct 21 ms 5624 KB Output is correct
12 Correct 18 ms 5624 KB Output is correct
13 Correct 24 ms 5624 KB Output is correct
14 Correct 41 ms 5624 KB Output is correct
15 Partially correct 128 ms 5632 KB Partially correct - number of queries: 7504
16 Partially correct 111 ms 5768 KB Partially correct - number of queries: 7918
17 Correct 13 ms 5768 KB Output is correct
18 Partially correct 85 ms 5880 KB Partially correct - number of queries: 7966
19 Partially correct 104 ms 5880 KB Partially correct - number of queries: 7573
20 Partially correct 68 ms 5880 KB Partially correct - number of queries: 5263
21 Partially correct 85 ms 5880 KB Partially correct - number of queries: 7894
22 Partially correct 57 ms 5880 KB Partially correct - number of queries: 6231
23 Correct 15 ms 5880 KB Output is correct
24 Correct 14 ms 5880 KB Output is correct
25 Partially correct 46 ms 5880 KB Partially correct - number of queries: 7229
26 Partially correct 106 ms 5880 KB Partially correct - number of queries: 7126
27 Correct 19 ms 5880 KB Output is correct
28 Partially correct 91 ms 5880 KB Partially correct - number of queries: 7191
29 Partially correct 105 ms 5880 KB Partially correct - number of queries: 6135
30 Partially correct 45 ms 5880 KB Partially correct - number of queries: 7922
31 Correct 17 ms 5880 KB Output is correct
32 Correct 26 ms 5880 KB Output is correct
33 Correct 8 ms 5880 KB Output is correct
34 Partially correct 124 ms 5880 KB Partially correct - number of queries: 7954
35 Correct 21 ms 5880 KB Output is correct
36 Partially correct 69 ms 5880 KB Partially correct - number of queries: 7999
37 Correct 25 ms 5880 KB Output is correct
38 Correct 16 ms 5880 KB Output is correct
39 Partially correct 59 ms 5880 KB Partially correct - number of queries: 7923
40 Partially correct 64 ms 5880 KB Partially correct - number of queries: 6958
41 Partially correct 52 ms 5880 KB Partially correct - number of queries: 7939
42 Partially correct 127 ms 5880 KB Partially correct - number of queries: 7939
43 Partially correct 136 ms 5880 KB Partially correct - number of queries: 7745
44 Partially correct 53 ms 5880 KB Partially correct - number of queries: 7918
45 Partially correct 73 ms 5880 KB Partially correct - number of queries: 7134
46 Correct 14 ms 5880 KB Output is correct
47 Partially correct 116 ms 5880 KB Partially correct - number of queries: 7254
48 Partially correct 114 ms 5880 KB Partially correct - number of queries: 7921
49 Partially correct 117 ms 5880 KB Partially correct - number of queries: 7994
50 Partially correct 77 ms 5880 KB Partially correct - number of queries: 7925
51 Partially correct 109 ms 5880 KB Partially correct - number of queries: 7935
52 Partially correct 101 ms 5880 KB Partially correct - number of queries: 7991
53 Correct 14 ms 5880 KB Output is correct
54 Partially correct 137 ms 5880 KB Partially correct - number of queries: 7909
55 Correct 15 ms 5880 KB Output is correct
56 Partially correct 59 ms 5880 KB Partially correct - number of queries: 8011
57 Partially correct 93 ms 5880 KB Partially correct - number of queries: 7950
58 Partially correct 143 ms 5880 KB Partially correct - number of queries: 7953
59 Partially correct 72 ms 5880 KB Partially correct - number of queries: 7981
60 Partially correct 105 ms 5880 KB Partially correct - number of queries: 7930
61 Correct 13 ms 5880 KB Output is correct
62 Correct 19 ms 5880 KB Output is correct
63 Correct 13 ms 5880 KB Output is correct
64 Correct 14 ms 5880 KB Output is correct
65 Correct 15 ms 5880 KB Output is correct
66 Correct 20 ms 5880 KB Output is correct
67 Correct 22 ms 5880 KB Output is correct
68 Correct 15 ms 5880 KB Output is correct
69 Correct 10 ms 5880 KB Output is correct
70 Correct 22 ms 5880 KB Output is correct
71 Partially correct 90 ms 5940 KB Partially correct - number of queries: 8551
72 Correct 34 ms 5940 KB Output is correct
73 Partially correct 117 ms 5940 KB Partially correct - number of queries: 8446
74 Partially correct 137 ms 5940 KB Partially correct - number of queries: 8491
75 Correct 16 ms 5940 KB Output is correct
76 Partially correct 60 ms 5940 KB Partially correct - number of queries: 7471
77 Partially correct 128 ms 5940 KB Partially correct - number of queries: 7707
78 Correct 27 ms 5940 KB Output is correct
79 Correct 31 ms 5940 KB Output is correct
80 Partially correct 140 ms 5940 KB Partially correct - number of queries: 7805
81 Partially correct 141 ms 5940 KB Partially correct - number of queries: 7787
82 Partially correct 136 ms 5940 KB Partially correct - number of queries: 7621
83 Correct 23 ms 5940 KB Output is correct
84 Partially correct 79 ms 5940 KB Partially correct - number of queries: 6551
85 Partially correct 139 ms 5940 KB Partially correct - number of queries: 7813
86 Incorrect 111 ms 5940 KB Incorrect
87 Halted 0 ms 0 KB -