oj.uz

답안 #785695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785695 2023-07-17T13:12:17 Z QwertyPi 커다란 상품 (IOI17_prize) C++14
92.89 / 100
 51 ms 1164 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 < min(n, 500); 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 336 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 4 ms 328 KB Output is correct
5 Correct 2 ms 360 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 4 ms 320 KB Output is correct
10 Correct 5 ms 332 KB Output is correct

Subtask #2
72.89 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 328 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 5 ms 288 KB Output is correct
4 Correct 2 ms 352 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 4 ms 292 KB Output is correct
8 Correct 5 ms 336 KB Output is correct
9 Correct 2 ms 360 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 6 ms 296 KB Output is correct
12 Correct 4 ms 356 KB Output is correct
13 Correct 4 ms 408 KB Output is correct
14 Correct 11 ms 448 KB Output is correct
15 Partially correct 35 ms 1164 KB Partially correct - number of queries: 5334
16 Partially correct 50 ms 828 KB Partially correct - number of queries: 5532
17 Partially correct 31 ms 912 KB Partially correct - number of queries: 5551
18 Partially correct 22 ms 888 KB Partially correct - number of queries: 5523
19 Partially correct 21 ms 932 KB Partially correct - number of queries: 5243
20 Correct 34 ms 668 KB Output is correct
21 Partially correct 21 ms 888 KB Partially correct - number of queries: 5502
22 Correct 28 ms 752 KB Output is correct
23 Correct 6 ms 336 KB Output is correct
24 Correct 4 ms 368 KB Output is correct
25 Partially correct 37 ms 792 KB Partially correct - number of queries: 5164
26 Partially correct 20 ms 844 KB Partially correct - number of queries: 5146
27 Correct 3 ms 328 KB Output is correct
28 Partially correct 45 ms 828 KB Partially correct - number of queries: 5125
29 Correct 39 ms 712 KB Output is correct
30 Partially correct 50 ms 804 KB Partially correct - number of queries: 5520
31 Partially correct 49 ms 840 KB Partially correct - number of queries: 5513
32 Correct 5 ms 336 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Partially correct 22 ms 888 KB Partially correct - number of queries: 5522
35 Correct 6 ms 304 KB Output is correct
36 Partially correct 49 ms 812 KB Partially correct - number of queries: 5551
37 Correct 8 ms 292 KB Output is correct
38 Correct 5 ms 292 KB Output is correct
39 Partially correct 22 ms 972 KB Partially correct - number of queries: 5561
40 Correct 36 ms 824 KB Output is correct
41 Partially correct 35 ms 820 KB Partially correct - number of queries: 5588
42 Partially correct 22 ms 912 KB Partially correct - number of queries: 5588
43 Partially correct 48 ms 800 KB Partially correct - number of queries: 5402
44 Partially correct 22 ms 912 KB Partially correct - number of queries: 5545
45 Partially correct 39 ms 892 KB Partially correct - number of queries: 5124
46 Partially correct 45 ms 804 KB Partially correct - number of queries: 5554
47 Partially correct 31 ms 780 KB Partially correct - number of queries: 5159
48 Partially correct 37 ms 876 KB Partially correct - number of queries: 5542
49 Partially correct 30 ms 792 KB Partially correct - number of queries: 5568
50 Partially correct 49 ms 836 KB Partially correct - number of queries: 5548
51 Partially correct 22 ms 920 KB Partially correct - number of queries: 5549
52 Partially correct 48 ms 908 KB Partially correct - number of queries: 5559
53 Correct 5 ms 288 KB Output is correct
54 Partially correct 47 ms 800 KB Partially correct - number of queries: 5505
55 Partially correct 37 ms 1012 KB Partially correct - number of queries: 5556
56 Partially correct 29 ms 884 KB Partially correct - number of queries: 5549
57 Partially correct 31 ms 956 KB Partially correct - number of queries: 5497
58 Partially correct 42 ms 928 KB Partially correct - number of queries: 5557
59 Partially correct 45 ms 808 KB Partially correct - number of queries: 5586
60 Partially correct 23 ms 916 KB Partially correct - number of queries: 5526
61 Correct 5 ms 288 KB Output is correct
62 Correct 3 ms 360 KB Output is correct
63 Correct 3 ms 364 KB Output is correct
64 Correct 6 ms 336 KB Output is correct
65 Correct 2 ms 336 KB Output is correct
66 Correct 4 ms 360 KB Output is correct
67 Correct 4 ms 508 KB Output is correct
68 Correct 2 ms 328 KB Output is correct
69 Correct 6 ms 336 KB Output is correct
70 Correct 6 ms 336 KB Output is correct
71 Partially correct 48 ms 812 KB Partially correct - number of queries: 5258
72 Correct 8 ms 364 KB Output is correct
73 Partially correct 35 ms 840 KB Partially correct - number of queries: 5195
74 Partially correct 46 ms 836 KB Partially correct - number of queries: 5222
75 Correct 7 ms 336 KB Output is correct
76 Correct 30 ms 692 KB Output is correct
77 Partially correct 24 ms 936 KB Partially correct - number of queries: 5691
78 Correct 9 ms 392 KB Output is correct
79 Correct 22 ms 712 KB Output is correct
80 Partially correct 29 ms 860 KB Partially correct - number of queries: 5711
81 Partially correct 33 ms 832 KB Partially correct - number of queries: 5708
82 Partially correct 36 ms 816 KB Partially correct - number of queries: 5656
83 Correct 6 ms 336 KB Output is correct
84 Correct 19 ms 796 KB Output is correct
85 Partially correct 51 ms 1020 KB Partially correct - number of queries: 5598
86 Correct 5 ms 336 KB Output is correct
87 Correct 4 ms 288 KB Output is correct
88 Correct 5 ms 336 KB Output is correct
89 Correct 3 ms 336 KB Output is correct
90 Correct 5 ms 336 KB Output is correct
91 Correct 3 ms 300 KB Output is correct
92 Correct 5 ms 332 KB Output is correct
93 Correct 7 ms 468 KB Output is correct
94 Correct 8 ms 336 KB Output is correct
95 Correct 6 ms 344 KB Output is correct
96 Correct 5 ms 392 KB Output is correct
97 Correct 3 ms 336 KB Output is correct