oj.uz

Submission #64592

# Submission time Handle Problem Language Result Execution time Memory
64592 2018-08-05T02:35:24 Z nvmdava The Big Prize (IOI17_prize) C++17
20 / 100
 139 ms 5948 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
 
 
vector<int> ans[210000];
int mx = -1, ll, rr;
int find(int l, int r){
	if(ans[l][0] == ans[r][0]){
		return 0;
	}
	if(ll > r || rr < l){
		return 0;
	}
	int m = (l + r) >> 1, L = m, R = m + 1;
	while(l < L){
		if(L < ll){
			break;
		}
		ans[L] =ask(L);
		if(ans[L][0] + ans[L][1] == mx){
			break;
		}
		if(ans[L][0] + ans[L][1] == 0){
			return L;
		}
		if(ans[L][0] == 0){
			ll = L + 1;
			break;
		}
		L--;
	}
	while(r > R){
		if(R > rr){
			break;
		}
		ans[R] =ask(R);
		if(ans[R][0] + ans[R][1] == mx){
			break;
		}
		if(ans[R][0] + ans[R][1] == 0){
			return R;
		}
		if(ans[R][1] == 0){
			rr = R - 1;
			break;	
		}
		R++;
	}
	return max(find(l, L), find(R, r));
}
 
int find_best(int n) {
	ll = 0;
	rr = n - 1;
	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 11 ms 5240 KB Output is correct
2 Correct 10 ms 5300 KB Output is correct
3 Correct 11 ms 5480 KB Output is correct
4 Correct 14 ms 5504 KB Output is correct
5 Correct 13 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 11 ms 5504 KB Output is correct
8 Correct 14 ms 5504 KB Output is correct
9 Correct 12 ms 5560 KB Output is correct
10 Correct 13 ms 5560 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5560 KB Output is correct
2 Correct 12 ms 5560 KB Output is correct
3 Correct 15 ms 5560 KB Output is correct
4 Correct 18 ms 5560 KB Output is correct
5 Correct 11 ms 5560 KB Output is correct
6 Correct 9 ms 5560 KB Output is correct
7 Correct 11 ms 5560 KB Output is correct
8 Correct 14 ms 5560 KB Output is correct
9 Correct 9 ms 5560 KB Output is correct
10 Correct 11 ms 5560 KB Output is correct
11 Correct 24 ms 5560 KB Output is correct
12 Correct 20 ms 5560 KB Output is correct
13 Correct 15 ms 5560 KB Output is correct
14 Correct 24 ms 5560 KB Output is correct
15 Partially correct 57 ms 5888 KB Partially correct - number of queries: 6326
16 Correct 40 ms 5888 KB Output is correct
17 Correct 13 ms 5888 KB Output is correct
18 Correct 40 ms 5888 KB Output is correct
19 Partially correct 86 ms 5888 KB Partially correct - number of queries: 7570
20 Correct 68 ms 5888 KB Output is correct
21 Partially correct 62 ms 5888 KB Partially correct - number of queries: 5213
22 Partially correct 65 ms 5888 KB Partially correct - number of queries: 5698
23 Correct 13 ms 5888 KB Output is correct
24 Correct 16 ms 5888 KB Output is correct
25 Correct 39 ms 5888 KB Output is correct
26 Partially correct 58 ms 5888 KB Partially correct - number of queries: 6261
27 Correct 16 ms 5888 KB Output is correct
28 Correct 35 ms 5888 KB Output is correct
29 Correct 24 ms 5888 KB Output is correct
30 Correct 15 ms 5888 KB Output is correct
31 Correct 18 ms 5888 KB Output is correct
32 Correct 22 ms 5888 KB Output is correct
33 Correct 9 ms 5888 KB Output is correct
34 Partially correct 103 ms 5888 KB Partially correct - number of queries: 7510
35 Correct 12 ms 5888 KB Output is correct
36 Partially correct 84 ms 5888 KB Partially correct - number of queries: 6958
37 Correct 16 ms 5888 KB Output is correct
38 Correct 19 ms 5888 KB Output is correct
39 Partially correct 44 ms 5888 KB Partially correct - number of queries: 5239
40 Correct 62 ms 5888 KB Output is correct
41 Partially correct 100 ms 5888 KB Partially correct - number of queries: 6799
42 Partially correct 109 ms 5888 KB Partially correct - number of queries: 6799
43 Partially correct 60 ms 5888 KB Partially correct - number of queries: 5056
44 Partially correct 68 ms 5888 KB Partially correct - number of queries: 6745
45 Partially correct 61 ms 5888 KB Partially correct - number of queries: 7033
46 Correct 11 ms 5888 KB Output is correct
47 Partially correct 103 ms 5888 KB Partially correct - number of queries: 7126
48 Partially correct 95 ms 5888 KB Partially correct - number of queries: 6894
49 Partially correct 67 ms 5888 KB Partially correct - number of queries: 7874
50 Correct 40 ms 5888 KB Output is correct
51 Partially correct 86 ms 5888 KB Partially correct - number of queries: 7365
52 Partially correct 39 ms 5888 KB Partially correct - number of queries: 7971
53 Correct 13 ms 5888 KB Output is correct
54 Partially correct 80 ms 5888 KB Partially correct - number of queries: 5447
55 Correct 19 ms 5888 KB Output is correct
56 Correct 59 ms 5888 KB Output is correct
57 Correct 36 ms 5888 KB Output is correct
58 Partially correct 97 ms 5888 KB Partially correct - number of queries: 7437
59 Partially correct 99 ms 5888 KB Partially correct - number of queries: 6841
60 Correct 48 ms 5888 KB Output is correct
61 Correct 15 ms 5888 KB Output is correct
62 Correct 11 ms 5888 KB Output is correct
63 Correct 15 ms 5888 KB Output is correct
64 Correct 18 ms 5888 KB Output is correct
65 Correct 15 ms 5888 KB Output is correct
66 Correct 18 ms 5888 KB Output is correct
67 Correct 19 ms 5888 KB Output is correct
68 Correct 10 ms 5888 KB Output is correct
69 Correct 14 ms 5888 KB Output is correct
70 Correct 14 ms 5888 KB Output is correct
71 Partially correct 83 ms 5888 KB Partially correct - number of queries: 8551
72 Correct 12 ms 5888 KB Output is correct
73 Partially correct 58 ms 5888 KB Partially correct - number of queries: 8446
74 Partially correct 72 ms 5888 KB Partially correct - number of queries: 8491
75 Correct 16 ms 5888 KB Output is correct
76 Partially correct 73 ms 5888 KB Partially correct - number of queries: 7471
77 Partially correct 106 ms 5948 KB Partially correct - number of queries: 7678
78 Correct 17 ms 5948 KB Output is correct
79 Correct 45 ms 5948 KB Output is correct
80 Partially correct 83 ms 5948 KB Partially correct - number of queries: 7696
81 Partially correct 44 ms 5948 KB Partially correct - number of queries: 7673
82 Partially correct 61 ms 5948 KB Partially correct - number of queries: 7733
83 Correct 16 ms 5948 KB Output is correct
84 Partially correct 63 ms 5948 KB Partially correct - number of queries: 6506
85 Partially correct 120 ms 5948 KB Partially correct - number of queries: 7732
86 Incorrect 139 ms 5948 KB Incorrect
87 Halted 0 ms 0 KB -