oj.uz

Submission #785696

# Submission time Handle Problem Language Result Execution time Memory
785696 2023-07-17T13:13:30 Z QwertyPi The Big Prize (IOI17_prize) C++14
93.13 / 100
 52 ms 1052 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 = max(0, n / 2 - 250); i < min(n, n / 2 + 250); 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 3 ms 336 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 4 ms 292 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 5 ms 328 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 4 ms 328 KB Output is correct
9 Correct 4 ms 336 KB Output is correct
10 Correct 3 ms 336 KB Output is correct

Subtask #2
73.13 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 288 KB Output is correct
2 Correct 2 ms 388 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 328 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 4 ms 328 KB Output is correct
7 Correct 5 ms 316 KB Output is correct
8 Correct 3 ms 336 KB Output is correct
9 Correct 5 ms 292 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 6 ms 308 KB Output is correct
12 Correct 5 ms 296 KB Output is correct
13 Correct 4 ms 364 KB Output is correct
14 Correct 15 ms 396 KB Output is correct
15 Partially correct 50 ms 864 KB Partially correct - number of queries: 5332
16 Partially correct 47 ms 888 KB Partially correct - number of queries: 5530
17 Partially correct 22 ms 916 KB Partially correct - number of queries: 5547
18 Partially correct 42 ms 796 KB Partially correct - number of queries: 5521
19 Partially correct 21 ms 872 KB Partially correct - number of queries: 5241
20 Correct 18 ms 696 KB Output is correct
21 Partially correct 37 ms 908 KB Partially correct - number of queries: 5495
22 Correct 27 ms 712 KB Output is correct
23 Correct 4 ms 344 KB Output is correct
24 Correct 6 ms 280 KB Output is correct
25 Partially correct 20 ms 844 KB Partially correct - number of queries: 5169
26 Partially correct 48 ms 840 KB Partially correct - number of queries: 5144
27 Correct 5 ms 292 KB Output is correct
28 Partially correct 35 ms 1052 KB Partially correct - number of queries: 5126
29 Correct 23 ms 696 KB Output is correct
30 Partially correct 26 ms 800 KB Partially correct - number of queries: 5517
31 Partially correct 27 ms 880 KB Partially correct - number of queries: 5510
32 Correct 9 ms 336 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Partially correct 22 ms 892 KB Partially correct - number of queries: 5520
35 Correct 6 ms 336 KB Output is correct
36 Partially correct 38 ms 884 KB Partially correct - number of queries: 5548
37 Correct 4 ms 360 KB Output is correct
38 Correct 4 ms 292 KB Output is correct
39 Partially correct 28 ms 952 KB Partially correct - number of queries: 5558
40 Correct 45 ms 728 KB Output is correct
41 Partially correct 22 ms 912 KB Partially correct - number of queries: 5578
42 Partially correct 37 ms 844 KB Partially correct - number of queries: 5578
43 Partially correct 46 ms 840 KB Partially correct - number of queries: 5400
44 Partially correct 37 ms 860 KB Partially correct - number of queries: 5541
45 Partially correct 37 ms 776 KB Partially correct - number of queries: 5131
46 Partially correct 22 ms 928 KB Partially correct - number of queries: 5552
47 Partially correct 31 ms 816 KB Partially correct - number of queries: 5165
48 Partially correct 38 ms 864 KB Partially correct - number of queries: 5540
49 Partially correct 34 ms 836 KB Partially correct - number of queries: 5564
50 Partially correct 22 ms 916 KB Partially correct - number of queries: 5546
51 Partially correct 30 ms 912 KB Partially correct - number of queries: 5546
52 Partially correct 45 ms 1008 KB Partially correct - number of queries: 5554
53 Correct 6 ms 296 KB Output is correct
54 Partially correct 48 ms 876 KB Partially correct - number of queries: 5500
55 Partially correct 46 ms 828 KB Partially correct - number of queries: 5553
56 Partially correct 44 ms 896 KB Partially correct - number of queries: 5546
57 Partially correct 52 ms 872 KB Partially correct - number of queries: 5494
58 Partially correct 49 ms 836 KB Partially correct - number of queries: 5553
59 Partially correct 35 ms 800 KB Partially correct - number of queries: 5577
60 Partially correct 47 ms 964 KB Partially correct - number of queries: 5524
61 Correct 4 ms 288 KB Output is correct
62 Correct 3 ms 364 KB Output is correct
63 Correct 6 ms 288 KB Output is correct
64 Correct 3 ms 360 KB Output is correct
65 Correct 5 ms 336 KB Output is correct
66 Correct 6 ms 336 KB Output is correct
67 Correct 7 ms 416 KB Output is correct
68 Correct 4 ms 352 KB Output is correct
69 Correct 9 ms 336 KB Output is correct
70 Correct 5 ms 360 KB Output is correct
71 Partially correct 46 ms 848 KB Partially correct - number of queries: 5258
72 Correct 9 ms 348 KB Output is correct
73 Partially correct 33 ms 836 KB Partially correct - number of queries: 5195
74 Partially correct 27 ms 808 KB Partially correct - number of queries: 5222
75 Correct 6 ms 300 KB Output is correct
76 Correct 41 ms 740 KB Output is correct
77 Partially correct 47 ms 840 KB Partially correct - number of queries: 5678
78 Correct 8 ms 384 KB Output is correct
79 Correct 20 ms 620 KB Output is correct
80 Partially correct 44 ms 896 KB Partially correct - number of queries: 5631
81 Partially correct 33 ms 888 KB Partially correct - number of queries: 5682
82 Partially correct 23 ms 912 KB Partially correct - number of queries: 5687
83 Correct 3 ms 300 KB Output is correct
84 Correct 37 ms 712 KB Output is correct
85 Partially correct 50 ms 892 KB Partially correct - number of queries: 5670
86 Correct 7 ms 348 KB Output is correct
87 Correct 5 ms 348 KB Output is correct
88 Correct 6 ms 372 KB Output is correct
89 Correct 6 ms 332 KB Output is correct
90 Correct 4 ms 336 KB Output is correct
91 Correct 5 ms 336 KB Output is correct
92 Correct 7 ms 336 KB Output is correct
93 Correct 8 ms 336 KB Output is correct
94 Correct 5 ms 336 KB Output is correct
95 Correct 7 ms 364 KB Output is correct
96 Correct 7 ms 324 KB Output is correct
97 Correct 3 ms 336 KB Output is correct