oj.uz

Submission #70109

# Submission time Handle Problem Language Result Execution time Memory
70109 2018-08-22T11:11:51 Z E869120 The Big Prize (IOI17_prize) C++14
20 / 100
 135 ms 2480 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

vector<int>vec;

int find_best(int n) {
	// -------------- 前処理 -----------------
	for(int i=0;i<n;i++) vec.push_back(i);
	
	while(vec.size() >= 2){
		int maxn=0;
		for(int i=0;i<30;i++){
			vector<int>P = ask(vec[rand()%vec.size()]);
			maxn = max(maxn, P[0] + P[1]);
		}
		assert(maxn<(int)vec.size());
		vector<int>vec2; int ret = -1;
		for(int h=0;h<maxn;h++){
			int cx = 0;
			for(int i=17;i>=0;i--){
				int pos = cx + (1 << i) - 1; if(pos >= (int)vec.size()) pos = vec.size() - 1;
				vector<int>L = ask(vec[pos]);
				if((L[0] + L[1] == maxn && L[0] == h) || pos <= ret) cx += (1 << i);
			}
			if(cx == 262143) cx = vec.size() - 1;
			assert(cx < (int)vec.size());
			vec2.push_back(vec[cx]); ret = cx;
		}
		vec = vec2;
	}
	return vec[0];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1436 KB Output is correct
2 Correct 4 ms 1448 KB Output is correct
3 Correct 4 ms 1528 KB Output is correct
4 Correct 5 ms 1556 KB Output is correct
5 Correct 6 ms 1600 KB Output is correct
6 Correct 5 ms 1728 KB Output is correct
7 Correct 4 ms 1728 KB Output is correct
8 Correct 4 ms 1728 KB Output is correct
9 Correct 4 ms 1728 KB Output is correct
10 Correct 5 ms 1728 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1728 KB Output is correct
2 Correct 5 ms 1728 KB Output is correct
3 Correct 4 ms 1728 KB Output is correct
4 Correct 4 ms 1728 KB Output is correct
5 Correct 5 ms 1728 KB Output is correct
6 Correct 5 ms 1728 KB Output is correct
7 Correct 5 ms 1728 KB Output is correct
8 Correct 5 ms 1728 KB Output is correct
9 Correct 6 ms 1728 KB Output is correct
10 Correct 4 ms 1728 KB Output is correct
11 Correct 17 ms 1728 KB Output is correct
12 Correct 12 ms 1728 KB Output is correct
13 Correct 14 ms 1728 KB Output is correct
14 Correct 25 ms 1728 KB Output is correct
15 Partially correct 62 ms 1728 KB Partially correct - number of queries: 8124
16 Partially correct 43 ms 1728 KB Partially correct - number of queries: 9192
17 Partially correct 81 ms 1728 KB Partially correct - number of queries: 9192
18 Partially correct 75 ms 1728 KB Partially correct - number of queries: 9192
19 Partially correct 73 ms 1728 KB Partially correct - number of queries: 8526
20 Partially correct 72 ms 1728 KB Partially correct - number of queries: 6456
21 Partially correct 54 ms 1728 KB Partially correct - number of queries: 8928
22 Partially correct 64 ms 1728 KB Partially correct - number of queries: 6498
23 Correct 7 ms 1728 KB Output is correct
24 Correct 18 ms 1728 KB Output is correct
25 Partially correct 77 ms 1728 KB Partially correct - number of queries: 9192
26 Partially correct 84 ms 1728 KB Partially correct - number of queries: 9192
27 Correct 7 ms 1728 KB Output is correct
28 Partially correct 129 ms 1728 KB Partially correct - number of queries: 8928
29 Partially correct 88 ms 1728 KB Partially correct - number of queries: 7482
30 Partially correct 51 ms 1728 KB Partially correct - number of queries: 8928
31 Partially correct 110 ms 1728 KB Partially correct - number of queries: 8928
32 Correct 21 ms 1728 KB Output is correct
33 Correct 7 ms 1728 KB Output is correct
34 Partially correct 124 ms 1728 KB Partially correct - number of queries: 9192
35 Correct 10 ms 1728 KB Output is correct
36 Partially correct 85 ms 1728 KB Partially correct - number of queries: 9066
37 Correct 8 ms 1728 KB Output is correct
38 Correct 12 ms 1728 KB Output is correct
39 Partially correct 89 ms 1728 KB Partially correct - number of queries: 8928
40 Partially correct 46 ms 1728 KB Partially correct - number of queries: 7554
41 Partially correct 42 ms 1728 KB Partially correct - number of queries: 9192
42 Partially correct 103 ms 1728 KB Partially correct - number of queries: 9192
43 Partially correct 92 ms 1728 KB Partially correct - number of queries: 8886
44 Partially correct 91 ms 1728 KB Partially correct - number of queries: 9192
45 Partially correct 102 ms 1728 KB Partially correct - number of queries: 9192
46 Partially correct 98 ms 1728 KB Partially correct - number of queries: 9192
47 Partially correct 116 ms 1728 KB Partially correct - number of queries: 9192
48 Partially correct 113 ms 1728 KB Partially correct - number of queries: 9192
49 Partially correct 106 ms 1728 KB Partially correct - number of queries: 9192
50 Partially correct 124 ms 1728 KB Partially correct - number of queries: 9192
51 Partially correct 135 ms 1728 KB Partially correct - number of queries: 9192
52 Partially correct 85 ms 1728 KB Partially correct - number of queries: 9192
53 Correct 6 ms 1728 KB Output is correct
54 Partially correct 55 ms 1728 KB Partially correct - number of queries: 8928
55 Partially correct 84 ms 1728 KB Partially correct - number of queries: 9192
56 Partially correct 38 ms 1728 KB Partially correct - number of queries: 9192
57 Partially correct 81 ms 1728 KB Partially correct - number of queries: 8928
58 Partially correct 116 ms 1728 KB Partially correct - number of queries: 9192
59 Partially correct 92 ms 1728 KB Partially correct - number of queries: 9192
60 Partially correct 77 ms 1728 KB Partially correct - number of queries: 8928
61 Correct 8 ms 1728 KB Output is correct
62 Correct 7 ms 1728 KB Output is correct
63 Correct 7 ms 1728 KB Output is correct
64 Correct 8 ms 1728 KB Output is correct
65 Correct 11 ms 1728 KB Output is correct
66 Partially correct 87 ms 1728 KB Partially correct - number of queries: 9192
67 Partially correct 86 ms 1728 KB Partially correct - number of queries: 8928
68 Partially correct 104 ms 1728 KB Partially correct - number of queries: 8124
69 Partially correct 107 ms 1728 KB Partially correct - number of queries: 9192
70 Partially correct 51 ms 1728 KB Partially correct - number of queries: 5682
71 Partially correct 47 ms 1728 KB Partially correct - number of queries: 9192
72 Correct 17 ms 1728 KB Output is correct
73 Partially correct 112 ms 1728 KB Partially correct - number of queries: 8976
74 Partially correct 66 ms 1728 KB Partially correct - number of queries: 8928
75 Correct 8 ms 1728 KB Output is correct
76 Partially correct 73 ms 1728 KB Partially correct - number of queries: 7650
77 Partially correct 61 ms 1728 KB Partially correct - number of queries: 9192
78 Correct 15 ms 1728 KB Output is correct
79 Correct 41 ms 1728 KB Output is correct
80 Partially correct 56 ms 1728 KB Partially correct - number of queries: 9192
81 Partially correct 38 ms 1728 KB Partially correct - number of queries: 9192
82 Partially correct 93 ms 1728 KB Partially correct - number of queries: 8928
83 Correct 9 ms 1728 KB Output is correct
84 Partially correct 84 ms 1728 KB Partially correct - number of queries: 7380
85 Partially correct 56 ms 1728 KB Partially correct - number of queries: 9192
86 Runtime error 9 ms 2480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Halted 0 ms 0 KB -