oj.uz

Submission #789190

# Submission time Handle Problem Language Result Execution time Memory
789190 2023-07-21T07:16:22 Z enerelt14 The Big Prize (IOI17_prize) C++14
90 / 100
 93 ms 11412 KB 
#include "prize.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define pb push_back

const int B = 472;
int val;

vector<vector<int>> memo;
vector<int> K(int i) {
	if(memo[i][0] != -1) return memo[i];
	return ask(i);
}

vector<int> find(int l, int r){
	vector<int> ans;
	if (l > r)return ans;
	vector<int> x = K(r);
	if (x[0] + x[1] != val){
		ans = find(l, r - 1);
		ans.pb(r);
		return ans;
	}
	int tl = l, tr = r;
	while (tl != tr){
		int mid = (tl + tr) / 2;
		vector<int> y = K(mid);
		if (y[0] + y[1] != val){
			tl = mid + 1;
			continue;
		}
		if (y[1] != x[1])tl = mid + 1;
		else tr = mid;
	}
	if (l == tr)return ans;
	else{
		ans = find(l, tr - 2);
		ans.pb(tr - 1);
		return ans;
	}
}

int find_best(int n){
	memo.resize(n, {-1, -1});
	vector<int> non_lolipop, x;
	for (int i = 0; i < B && i < n; i++){
		x = K(i);
		val = max(val, x[0] + x[1]);
	}
	for (int i = 0; i < n; i += B){
		x = find(i, min(n - 1, i + B - 1));
		for (int i = 0; i < x.size(); i++)non_lolipop.pb(x[i]);
	}
	for (int i = 0; i < non_lolipop.size(); i++){
		x = K(non_lolipop[i]);
		if (x[0] + x[1] == 0)return non_lolipop[i];
	}
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (int i = 0; i < x.size(); i++)non_lolipop.pb(x[i]);
      |                   ~~^~~~~~~~~~
prize.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < non_lolipop.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
prize.cpp:62:14: warning: control reaches end of non-void function [-Wreturn-type]
   62 |  vector<int> non_lolipop, x;
      |              ^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11244 KB Output is correct
2 Correct 51 ms 11164 KB Output is correct
3 Correct 27 ms 11276 KB Output is correct
4 Correct 52 ms 11156 KB Output is correct
5 Correct 29 ms 11284 KB Output is correct
6 Correct 33 ms 11276 KB Output is correct
7 Correct 52 ms 11216 KB Output is correct
8 Correct 26 ms 11272 KB Output is correct
9 Correct 41 ms 11216 KB Output is correct
10 Correct 46 ms 11216 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11172 KB Output is correct
2 Correct 44 ms 11152 KB Output is correct
3 Correct 38 ms 11192 KB Output is correct
4 Correct 38 ms 11336 KB Output is correct
5 Correct 50 ms 11216 KB Output is correct
6 Correct 47 ms 11220 KB Output is correct
7 Correct 52 ms 11168 KB Output is correct
8 Correct 36 ms 11272 KB Output is correct
9 Correct 46 ms 11196 KB Output is correct
10 Correct 38 ms 11192 KB Output is correct
11 Partially correct 52 ms 11180 KB Partially correct - number of queries: 5024
12 Partially correct 27 ms 11264 KB Partially correct - number of queries: 5009
13 Partially correct 44 ms 11216 KB Partially correct - number of queries: 5043
14 Correct 15 ms 1360 KB Output is correct
15 Partially correct 68 ms 11248 KB Partially correct - number of queries: 8718
16 Partially correct 89 ms 11216 KB Partially correct - number of queries: 9255
17 Partially correct 72 ms 11216 KB Partially correct - number of queries: 8842
18 Partially correct 75 ms 11216 KB Partially correct - number of queries: 9317
19 Partially correct 88 ms 11260 KB Partially correct - number of queries: 8624
20 Partially correct 41 ms 5772 KB Partially correct - number of queries: 5542
21 Partially correct 52 ms 11272 KB Partially correct - number of queries: 9041
22 Partially correct 56 ms 11172 KB Partially correct - number of queries: 7784
23 Correct 31 ms 11216 KB Output is correct
24 Partially correct 54 ms 11172 KB Partially correct - number of queries: 5002
25 Partially correct 90 ms 11172 KB Partially correct - number of queries: 8996
26 Partially correct 51 ms 11248 KB Partially correct - number of queries: 8980
27 Correct 41 ms 11268 KB Output is correct
28 Partially correct 82 ms 11252 KB Partially correct - number of queries: 9197
29 Partially correct 80 ms 11164 KB Partially correct - number of queries: 8352
30 Partially correct 52 ms 11276 KB Partially correct - number of queries: 9296
31 Partially correct 39 ms 11252 KB Partially correct - number of queries: 8838
32 Partially correct 42 ms 11212 KB Partially correct - number of queries: 5029
33 Correct 2 ms 304 KB Output is correct
34 Partially correct 80 ms 11172 KB Partially correct - number of queries: 8996
35 Correct 42 ms 11216 KB Output is correct
36 Partially correct 51 ms 11272 KB Partially correct - number of queries: 8897
37 Partially correct 37 ms 11268 KB Partially correct - number of queries: 5027
38 Correct 50 ms 11168 KB Output is correct
39 Partially correct 83 ms 11268 KB Partially correct - number of queries: 9042
40 Partially correct 38 ms 11268 KB Partially correct - number of queries: 8631
41 Partially correct 77 ms 11248 KB Partially correct - number of queries: 9130
42 Partially correct 68 ms 11216 KB Partially correct - number of queries: 9130
43 Partially correct 61 ms 11268 KB Partially correct - number of queries: 8987
44 Partially correct 39 ms 11276 KB Partially correct - number of queries: 9052
45 Partially correct 73 ms 11164 KB Partially correct - number of queries: 8976
46 Partially correct 57 ms 11260 KB Partially correct - number of queries: 8849
47 Partially correct 67 ms 11168 KB Partially correct - number of queries: 9023
48 Partially correct 40 ms 11272 KB Partially correct - number of queries: 9183
49 Partially correct 50 ms 11272 KB Partially correct - number of queries: 8892
50 Partially correct 72 ms 11172 KB Partially correct - number of queries: 9318
51 Partially correct 89 ms 11252 KB Partially correct - number of queries: 9012
52 Partially correct 79 ms 11284 KB Partially correct - number of queries: 8876
53 Correct 51 ms 11216 KB Output is correct
54 Partially correct 76 ms 11172 KB Partially correct - number of queries: 9039
55 Partially correct 49 ms 11252 KB Partially correct - number of queries: 8848
56 Partially correct 91 ms 11248 KB Partially correct - number of queries: 9331
57 Partially correct 75 ms 11256 KB Partially correct - number of queries: 9160
58 Partially correct 64 ms 11252 KB Partially correct - number of queries: 9161
59 Partially correct 65 ms 11272 KB Partially correct - number of queries: 9131
60 Partially correct 80 ms 11256 KB Partially correct - number of queries: 9102
61 Correct 63 ms 11168 KB Output is correct
62 Correct 49 ms 11176 KB Output is correct
63 Correct 47 ms 11232 KB Output is correct
64 Correct 34 ms 11164 KB Output is correct
65 Correct 52 ms 11168 KB Output is correct
66 Partially correct 55 ms 11252 KB Partially correct - number of queries: 5642
67 Partially correct 33 ms 11260 KB Partially correct - number of queries: 5171
68 Partially correct 57 ms 11312 KB Partially correct - number of queries: 5605
69 Partially correct 45 ms 11312 KB Partially correct - number of queries: 5625
70 Partially correct 44 ms 11252 KB Partially correct - number of queries: 5012
71 Partially correct 69 ms 11256 KB Partially correct - number of queries: 9708
72 Partially correct 46 ms 11164 KB Partially correct - number of queries: 5086
73 Partially correct 79 ms 11264 KB Partially correct - number of queries: 9659
74 Partially correct 43 ms 11272 KB Partially correct - number of queries: 9680
75 Correct 42 ms 11216 KB Output is correct
76 Partially correct 47 ms 11272 KB Partially correct - number of queries: 9112
77 Partially correct 80 ms 11216 KB Partially correct - number of queries: 9728
78 Partially correct 61 ms 11216 KB Partially correct - number of queries: 5086
79 Partially correct 66 ms 11216 KB Partially correct - number of queries: 7021
80 Partially correct 80 ms 11240 KB Partially correct - number of queries: 9749
81 Partially correct 80 ms 11260 KB Partially correct - number of queries: 9727
82 Partially correct 90 ms 11272 KB Partially correct - number of queries: 9709
83 Correct 52 ms 11216 KB Output is correct
84 Partially correct 62 ms 11216 KB Partially correct - number of queries: 8930
85 Partially correct 93 ms 11256 KB Partially correct - number of queries: 9732
86 Partially correct 33 ms 11300 KB Partially correct - number of queries: 5663
87 Correct 34 ms 11156 KB Output is correct
88 Partially correct 38 ms 11412 KB Partially correct - number of queries: 5610
89 Partially correct 58 ms 11336 KB Partially correct - number of queries: 5656
90 Correct 55 ms 11216 KB Output is correct
91 Partially correct 50 ms 11272 KB Partially correct - number of queries: 5264
92 Partially correct 50 ms 11268 KB Partially correct - number of queries: 5614
93 Partially correct 47 ms 11272 KB Partially correct - number of queries: 5854
94 Partially correct 54 ms 11324 KB Partially correct - number of queries: 5861
95 Partially correct 41 ms 11272 KB Partially correct - number of queries: 5841
96 Partially correct 60 ms 11312 KB Partially correct - number of queries: 5819
97 Partially correct 37 ms 11344 KB Partially correct - number of queries: 5613