oj.uz

Submission #785689

# Submission time Handle Problem Language Result Execution time Memory
785689 2023-07-17T13:00:36 Z QwertyPi The Big Prize (IOI17_prize) C++14
20 / 100
 51 ms 1404 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

map<int, vector<int>> M, Li;
vector<int> self_ask(int i){
	if(!M.count(i)) M[i] = ask(i); vector<int> r = M[i];
	Li[r[0] + r[1]].push_back(i);
	return r;
}

vector<int> b;

void solve(int l, int r, int cc, int lc, int rc){
	if(l > r || lc == rc) return;
	int L = (l + r) / 2, R = (l + r) / 2 + 1, F = 0;
	int c; vector<int> a;
	while(true){
		c = F ? R++ : L--; F ^= 1;
		a = self_ask(c);
		if(a[0] + a[1] == cc || R - L - 1 == rc - lc){
			break;
		}
	}
	if(c == L + 1){
		solve(l, L, cc, lc, a[0]);
		solve(R, r, cc, a[0] + (R - L - 2), rc);
	}else{
		solve(l, L, cc, lc, a[0] - (R - L - 2));
		solve(R, r, cc, a[0], rc);
	}
}

int find_best(int n) {
	
	for(int i = 0; i < (int) sqrt(n); i++) self_ask(i);
	int cc = (--Li.end())->first;
	solve(0, n - 1, cc, 0, cc);
	for(auto [i, p] : M){
		if(p[0] + p[1] == 0){
			return i;
		}
	}
	return -1; 
}

Compilation message

prize.cpp: In function 'std::vector<int> self_ask(int)':
prize.cpp:8:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    8 |  if(!M.count(i)) M[i] = ask(i); vector<int> r = M[i];
      |  ^~
prize.cpp:8:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    8 |  if(!M.count(i)) M[i] = ask(i); vector<int> r = M[i];
      |                                 ^~~~~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:40:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |  for(auto [i, p] : M){
      |           ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 3 ms 292 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 4 ms 292 KB Output is correct
7 Correct 5 ms 336 KB Output is correct
8 Correct 4 ms 288 KB Output is correct
9 Correct 3 ms 292 KB Output is correct
10 Correct 5 ms 300 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 308 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 4 ms 288 KB Output is correct
4 Correct 3 ms 324 KB Output is correct
5 Correct 4 ms 296 KB Output is correct
6 Correct 6 ms 336 KB Output is correct
7 Correct 4 ms 292 KB Output is correct
8 Correct 5 ms 296 KB Output is correct
9 Correct 4 ms 296 KB Output is correct
10 Correct 6 ms 320 KB Output is correct
11 Correct 8 ms 292 KB Output is correct
12 Correct 8 ms 364 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 11 ms 380 KB Output is correct
15 Partially correct 48 ms 840 KB Partially correct - number of queries: 5284
16 Partially correct 24 ms 872 KB Partially correct - number of queries: 5480
17 Partially correct 28 ms 880 KB Partially correct - number of queries: 5499
18 Partially correct 21 ms 880 KB Partially correct - number of queries: 5471
19 Partially correct 42 ms 760 KB Partially correct - number of queries: 5197
20 Correct 34 ms 660 KB Output is correct
21 Partially correct 48 ms 808 KB Partially correct - number of queries: 5450
22 Correct 33 ms 676 KB Output is correct
23 Correct 6 ms 336 KB Output is correct
24 Correct 8 ms 296 KB Output is correct
25 Partially correct 34 ms 968 KB Partially correct - number of queries: 5118
26 Partially correct 38 ms 816 KB Partially correct - number of queries: 5093
27 Correct 5 ms 296 KB Output is correct
28 Partially correct 46 ms 784 KB Partially correct - number of queries: 5073
29 Correct 29 ms 672 KB Output is correct
30 Partially correct 36 ms 780 KB Partially correct - number of queries: 5468
31 Partially correct 50 ms 892 KB Partially correct - number of queries: 5461
32 Correct 7 ms 332 KB Output is correct
33 Correct 1 ms 304 KB Output is correct
34 Partially correct 43 ms 824 KB Partially correct - number of queries: 5470
35 Correct 5 ms 328 KB Output is correct
36 Partially correct 49 ms 832 KB Partially correct - number of queries: 5499
37 Correct 7 ms 460 KB Output is correct
38 Correct 3 ms 288 KB Output is correct
39 Partially correct 21 ms 880 KB Partially correct - number of queries: 5509
40 Correct 20 ms 816 KB Output is correct
41 Partially correct 35 ms 840 KB Partially correct - number of queries: 5536
42 Partially correct 30 ms 908 KB Partially correct - number of queries: 5536
43 Partially correct 33 ms 840 KB Partially correct - number of queries: 5350
44 Partially correct 28 ms 896 KB Partially correct - number of queries: 5493
45 Partially correct 44 ms 832 KB Partially correct - number of queries: 5071
46 Partially correct 51 ms 840 KB Partially correct - number of queries: 5502
47 Partially correct 44 ms 840 KB Partially correct - number of queries: 5107
48 Partially correct 22 ms 888 KB Partially correct - number of queries: 5490
49 Partially correct 37 ms 908 KB Partially correct - number of queries: 5516
50 Partially correct 48 ms 840 KB Partially correct - number of queries: 5496
51 Partially correct 21 ms 892 KB Partially correct - number of queries: 5497
52 Partially correct 36 ms 892 KB Partially correct - number of queries: 5507
53 Correct 2 ms 360 KB Output is correct
54 Partially correct 48 ms 868 KB Partially correct - number of queries: 5453
55 Partially correct 21 ms 880 KB Partially correct - number of queries: 5504
56 Partially correct 23 ms 876 KB Partially correct - number of queries: 5497
57 Partially correct 41 ms 832 KB Partially correct - number of queries: 5445
58 Partially correct 41 ms 780 KB Partially correct - number of queries: 5505
59 Partially correct 21 ms 924 KB Partially correct - number of queries: 5534
60 Partially correct 50 ms 812 KB Partially correct - number of queries: 5474
61 Correct 3 ms 360 KB Output is correct
62 Correct 2 ms 356 KB Output is correct
63 Correct 3 ms 288 KB Output is correct
64 Correct 2 ms 360 KB Output is correct
65 Correct 2 ms 332 KB Output is correct
66 Correct 4 ms 360 KB Output is correct
67 Correct 8 ms 328 KB Output is correct
68 Incorrect 47 ms 1404 KB Incorrect
69 Halted 0 ms 0 KB -