oj.uz

Submission #789185

# Submission time Handle Problem Language Result Execution time Memory
789185 2023-07-21T07:13:50 Z enerelt14 The Big Prize (IOI17_prize) C++14
90 / 100
 92 ms 344 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<int> find(int l, int r){
	vector<int> ans;
	if (l > r)return ans;
	vector<int> x = ask(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 = ask(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){
	vector<int> non_lolipop, x;
	for (int i = 0; i < B && i < n; i++){
		x = ask(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 = ask(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:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int i = 0; i < x.size(); i++)non_lolipop.pb(x[i]);
      |                   ~~^~~~~~~~~~
prize.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < non_lolipop.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
prize.cpp:55:14: warning: control reaches end of non-void function [-Wreturn-type]
   55 |  vector<int> non_lolipop, x;
      |              ^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 208 KB Output is correct
2 Correct 41 ms 208 KB Output is correct
3 Correct 39 ms 292 KB Output is correct
4 Correct 16 ms 288 KB Output is correct
5 Correct 34 ms 288 KB Output is correct
6 Correct 43 ms 208 KB Output is correct
7 Correct 39 ms 208 KB Output is correct
8 Correct 26 ms 288 KB Output is correct
9 Correct 35 ms 288 KB Output is correct
10 Correct 38 ms 208 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 288 KB Output is correct
2 Correct 16 ms 288 KB Output is correct
3 Correct 16 ms 292 KB Output is correct
4 Correct 16 ms 292 KB Output is correct
5 Correct 37 ms 292 KB Output is correct
6 Correct 39 ms 208 KB Output is correct
7 Correct 39 ms 300 KB Output is correct
8 Correct 17 ms 288 KB Output is correct
9 Correct 32 ms 208 KB Output is correct
10 Correct 37 ms 208 KB Output is correct
11 Partially correct 32 ms 208 KB Partially correct - number of queries: 5024
12 Partially correct 28 ms 208 KB Partially correct - number of queries: 5009
13 Partially correct 21 ms 268 KB Partially correct - number of queries: 5043
14 Correct 18 ms 208 KB Output is correct
15 Partially correct 50 ms 276 KB Partially correct - number of queries: 8718
16 Partially correct 32 ms 288 KB Partially correct - number of queries: 9255
17 Partially correct 63 ms 288 KB Partially correct - number of queries: 8842
18 Partially correct 76 ms 280 KB Partially correct - number of queries: 9317
19 Partially correct 59 ms 208 KB Partially correct - number of queries: 8624
20 Partially correct 39 ms 208 KB Partially correct - number of queries: 5542
21 Partially correct 51 ms 208 KB Partially correct - number of queries: 9041
22 Partially correct 63 ms 292 KB Partially correct - number of queries: 7784
23 Correct 37 ms 292 KB Output is correct
24 Partially correct 34 ms 292 KB Partially correct - number of queries: 5002
25 Partially correct 30 ms 304 KB Partially correct - number of queries: 8996
26 Partially correct 75 ms 280 KB Partially correct - number of queries: 8980
27 Correct 35 ms 208 KB Output is correct
28 Partially correct 64 ms 316 KB Partially correct - number of queries: 9197
29 Partially correct 39 ms 276 KB Partially correct - number of queries: 8352
30 Partially correct 58 ms 292 KB Partially correct - number of queries: 9296
31 Partially correct 60 ms 292 KB Partially correct - number of queries: 8838
32 Partially correct 38 ms 288 KB Partially correct - number of queries: 5029
33 Correct 2 ms 208 KB Output is correct
34 Partially correct 30 ms 292 KB Partially correct - number of queries: 8996
35 Correct 42 ms 208 KB Output is correct
36 Partially correct 52 ms 208 KB Partially correct - number of queries: 8897
37 Partially correct 42 ms 292 KB Partially correct - number of queries: 5027
38 Correct 33 ms 292 KB Output is correct
39 Partially correct 49 ms 276 KB Partially correct - number of queries: 9042
40 Partially correct 52 ms 276 KB Partially correct - number of queries: 8631
41 Partially correct 30 ms 336 KB Partially correct - number of queries: 9130
42 Partially correct 78 ms 208 KB Partially correct - number of queries: 9130
43 Partially correct 46 ms 336 KB Partially correct - number of queries: 8987
44 Partially correct 75 ms 284 KB Partially correct - number of queries: 9052
45 Partially correct 56 ms 296 KB Partially correct - number of queries: 8976
46 Partially correct 59 ms 280 KB Partially correct - number of queries: 8849
47 Partially correct 70 ms 296 KB Partially correct - number of queries: 9023
48 Partially correct 31 ms 296 KB Partially correct - number of queries: 9183
49 Partially correct 76 ms 292 KB Partially correct - number of queries: 8892
50 Partially correct 64 ms 208 KB Partially correct - number of queries: 9318
51 Partially correct 52 ms 288 KB Partially correct - number of queries: 9012
52 Partially correct 72 ms 208 KB Partially correct - number of queries: 8876
53 Correct 36 ms 292 KB Output is correct
54 Partially correct 81 ms 288 KB Partially correct - number of queries: 9039
55 Partially correct 60 ms 276 KB Partially correct - number of queries: 8848
56 Partially correct 74 ms 208 KB Partially correct - number of queries: 9331
57 Partially correct 34 ms 292 KB Partially correct - number of queries: 9160
58 Partially correct 92 ms 292 KB Partially correct - number of queries: 9161
59 Partially correct 73 ms 276 KB Partially correct - number of queries: 9131
60 Partially correct 64 ms 208 KB Partially correct - number of queries: 9102
61 Correct 19 ms 288 KB Output is correct
62 Correct 40 ms 208 KB Output is correct
63 Correct 33 ms 208 KB Output is correct
64 Correct 36 ms 296 KB Output is correct
65 Correct 39 ms 296 KB Output is correct
66 Partially correct 32 ms 328 KB Partially correct - number of queries: 5642
67 Partially correct 36 ms 292 KB Partially correct - number of queries: 5171
68 Partially correct 48 ms 288 KB Partially correct - number of queries: 5605
69 Partially correct 19 ms 316 KB Partially correct - number of queries: 5625
70 Partially correct 30 ms 296 KB Partially correct - number of queries: 5012
71 Partially correct 64 ms 276 KB Partially correct - number of queries: 9708
72 Partially correct 41 ms 208 KB Partially correct - number of queries: 5086
73 Partially correct 54 ms 208 KB Partially correct - number of queries: 9659
74 Partially correct 52 ms 280 KB Partially correct - number of queries: 9680
75 Correct 32 ms 208 KB Output is correct
76 Partially correct 58 ms 208 KB Partially correct - number of queries: 9112
77 Partially correct 39 ms 300 KB Partially correct - number of queries: 9728
78 Partially correct 39 ms 208 KB Partially correct - number of queries: 5086
79 Partially correct 24 ms 344 KB Partially correct - number of queries: 7021
80 Partially correct 58 ms 336 KB Partially correct - number of queries: 9749
81 Partially correct 32 ms 292 KB Partially correct - number of queries: 9727
82 Partially correct 52 ms 208 KB Partially correct - number of queries: 9709
83 Correct 40 ms 208 KB Output is correct
84 Partially correct 72 ms 208 KB Partially correct - number of queries: 8930
85 Partially correct 77 ms 276 KB Partially correct - number of queries: 9732
86 Partially correct 32 ms 336 KB Partially correct - number of queries: 5663
87 Correct 18 ms 300 KB Output is correct
88 Partially correct 29 ms 344 KB Partially correct - number of queries: 5610
89 Partially correct 34 ms 324 KB Partially correct - number of queries: 5656
90 Correct 41 ms 208 KB Output is correct
91 Partially correct 45 ms 292 KB Partially correct - number of queries: 5264
92 Partially correct 20 ms 320 KB Partially correct - number of queries: 5614
93 Partially correct 50 ms 336 KB Partially correct - number of queries: 5854
94 Partially correct 34 ms 312 KB Partially correct - number of queries: 5861
95 Partially correct 38 ms 336 KB Partially correct - number of queries: 5841
96 Partially correct 32 ms 336 KB Partially correct - number of queries: 5819
97 Partially correct 38 ms 336 KB Partially correct - number of queries: 5613