oj.uz

Submission #931424

# Submission time Handle Problem Language Result Execution time Memory
931424 2024-02-21T18:54:03 Z Lobo The Big Prize (IOI17_prize) C++17
90 / 100
 44 ms 2164 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
map<int,pair<int,pair<int,int>>> qr;
 
int cnt = 0;
int cntnonlol;
int n;
pair<int,pair<int,int>> query(int i) {
	if(i == n) return mp(cntnonlol,mp(cntnonlol,0));
	if(qr.count(i)) return qr[i];
	++cnt;
	// assert(cnt <= 8500);
	vector<int> perg = ask(i);
	return qr[i] = mp(perg[0]+perg[1],mp(perg[0],perg[1]));
}
 
const int B = 477;
const int S = 950;
int find_best(int N) {
 	n = N;
 	queue<pair<int,int>> q;
 	q.push(mp(0,n-1));

 	while(q.size()) {
 		int l = q.front().fr;
 		int r = q.front().sc;
 		q.pop();
 		if(l > r) continue;

 		if(query(l).fr == 0) return l;
 		if(query(r).fr == 0) return r;

 		if(query(l) == query(r)) continue;

 		int mid = (l+r)/2;
 		q.push(mp(l,mid));
 		q.push(mp(mid+1,r));
 	}

 	assert(false);
 	return -1;


}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 436 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 428 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 692 KB Output is correct
11 Correct 3 ms 976 KB Output is correct
12 Correct 2 ms 624 KB Output is correct
13 Correct 3 ms 976 KB Output is correct
14 Correct 6 ms 864 KB Output is correct
15 Partially correct 32 ms 1708 KB Partially correct - number of queries: 6519
16 Partially correct 39 ms 1112 KB Partially correct - number of queries: 6526
17 Partially correct 26 ms 1208 KB Partially correct - number of queries: 5745
18 Partially correct 44 ms 1392 KB Partially correct - number of queries: 8135
19 Partially correct 35 ms 2096 KB Partially correct - number of queries: 6330
20 Correct 17 ms 1392 KB Output is correct
21 Partially correct 29 ms 1432 KB Partially correct - number of queries: 6983
22 Partially correct 25 ms 1344 KB Partially correct - number of queries: 5253
23 Correct 1 ms 956 KB Output is correct
24 Correct 4 ms 868 KB Output is correct
25 Partially correct 27 ms 1920 KB Partially correct - number of queries: 6452
26 Partially correct 33 ms 1776 KB Partially correct - number of queries: 7149
27 Correct 1 ms 440 KB Output is correct
28 Partially correct 34 ms 1516 KB Partially correct - number of queries: 7257
29 Partially correct 29 ms 1360 KB Partially correct - number of queries: 6151
30 Partially correct 42 ms 1240 KB Partially correct - number of queries: 8075
31 Partially correct 28 ms 2164 KB Partially correct - number of queries: 6642
32 Correct 4 ms 968 KB Output is correct
33 Correct 0 ms 436 KB Output is correct
34 Partially correct 30 ms 1688 KB Partially correct - number of queries: 6975
35 Correct 2 ms 452 KB Output is correct
36 Partially correct 29 ms 884 KB Partially correct - number of queries: 5911
37 Correct 2 ms 452 KB Output is correct
38 Correct 1 ms 440 KB Output is correct
39 Partially correct 35 ms 1592 KB Partially correct - number of queries: 7053
40 Partially correct 30 ms 1160 KB Partially correct - number of queries: 5823
41 Partially correct 32 ms 2112 KB Partially correct - number of queries: 7225
42 Partially correct 43 ms 1356 KB Partially correct - number of queries: 7225
43 Partially correct 39 ms 1032 KB Partially correct - number of queries: 6991
44 Partially correct 33 ms 1400 KB Partially correct - number of queries: 7054
45 Partially correct 40 ms 1900 KB Partially correct - number of queries: 6990
46 Partially correct 30 ms 1444 KB Partially correct - number of queries: 5745
47 Partially correct 37 ms 1780 KB Partially correct - number of queries: 7164
48 Partially correct 31 ms 1444 KB Partially correct - number of queries: 7359
49 Partially correct 34 ms 1872 KB Partially correct - number of queries: 6755
50 Partially correct 40 ms 1560 KB Partially correct - number of queries: 7631
51 Partially correct 35 ms 1568 KB Partially correct - number of queries: 7827
52 Partially correct 35 ms 1788 KB Partially correct - number of queries: 7636
53 Correct 1 ms 696 KB Output is correct
54 Correct 18 ms 984 KB Output is correct
55 Partially correct 26 ms 1624 KB Partially correct - number of queries: 5745
56 Partially correct 44 ms 1700 KB Partially correct - number of queries: 7632
57 Partially correct 37 ms 1428 KB Partially correct - number of queries: 7927
58 Partially correct 41 ms 1736 KB Partially correct - number of queries: 7991
59 Partially correct 32 ms 1032 KB Partially correct - number of queries: 7225
60 Partially correct 42 ms 1644 KB Partially correct - number of queries: 7842
61 Correct 1 ms 448 KB Output is correct
62 Correct 1 ms 436 KB Output is correct
63 Correct 1 ms 440 KB Output is correct
64 Correct 1 ms 440 KB Output is correct
65 Correct 1 ms 432 KB Output is correct
66 Correct 1 ms 440 KB Output is correct
67 Correct 0 ms 436 KB Output is correct
68 Correct 0 ms 432 KB Output is correct
69 Correct 1 ms 608 KB Output is correct
70 Correct 1 ms 436 KB Output is correct
71 Partially correct 43 ms 872 KB Partially correct - number of queries: 8104
72 Correct 4 ms 740 KB Output is correct
73 Partially correct 34 ms 1384 KB Partially correct - number of queries: 7999
74 Partially correct 40 ms 1628 KB Partially correct - number of queries: 8044
75 Correct 1 ms 448 KB Output is correct
76 Partially correct 32 ms 1520 KB Partially correct - number of queries: 7024
77 Partially correct 34 ms 1560 KB Partially correct - number of queries: 8009
78 Correct 4 ms 436 KB Output is correct
79 Correct 24 ms 952 KB Output is correct
80 Partially correct 42 ms 1568 KB Partially correct - number of queries: 7862
81 Partially correct 35 ms 1836 KB Partially correct - number of queries: 8078
82 Partially correct 34 ms 1988 KB Partially correct - number of queries: 7750
83 Correct 1 ms 688 KB Output is correct
84 Partially correct 29 ms 1056 KB Partially correct - number of queries: 6586
85 Partially correct 39 ms 1548 KB Partially correct - number of queries: 7999
86 Correct 7 ms 968 KB Output is correct
87 Correct 2 ms 456 KB Output is correct
88 Correct 5 ms 944 KB Output is correct
89 Correct 6 ms 688 KB Output is correct
90 Correct 1 ms 440 KB Output is correct
91 Correct 3 ms 948 KB Output is correct
92 Correct 1 ms 432 KB Output is correct
93 Correct 3 ms 724 KB Output is correct
94 Correct 4 ms 708 KB Output is correct
95 Correct 4 ms 468 KB Output is correct
96 Correct 4 ms 708 KB Output is correct
97 Correct 0 ms 436 KB Output is correct