oj.uz

Submission #721451

# Submission time Handle Problem Language Result Execution time Memory
721451 2023-04-11T01:46:27 Z minhcool The Big Prize (IOI17_prize) C++17
90 / 100
 89 ms 348 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
vector<int> askk(int pos){
	return ask(pos - 1);
}
 
int find_best(int N){
	n = N;
	if(n <= 5000){
		for(int i = 1; i <= n; i++){
			vector<int> res = askk(i);
			if(res[0] == 0 && res[1] == 0) return i - 1;
		}
	}
	//cout << "OK\n";
	int mx = -1;
	for(int i = 1; i <= 500; i++){
		vector<int> v = askk(rnd(1, n));
		mx = max(mx, v[0] + v[1]);
	}
	int itr = 0, tot = 0;
	while(1){
      if(itr >= n) return n - 1;
		int l = itr + 1, r = n;
		while(l < r){
			int mid = (l + r) >> 1;
			vector<int> a = askk(mid);
			if(a[0] + a[1] != mx) r = mid;
			else if(a[0] > tot) r = mid;
			else l = mid + 1;
		}
		vector<int> v = askk(l);
		if(!(v[0] + v[1])) return l - 1;
		itr = l;
        tot++;
		/*
		assert(l != n);
		vector<int> v = ask(l + 1);
		assert(v[0] + v[1] != mx);
		if(!(v[0] + v[1])) return l + 1;
		int temp = l + 1;
		set<int> se;
		se.insert(mx);
		se.insert(v[0] + v[1]);*/
	}
}
 
 
/*
void process(){
 
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
*/

Compilation message

prize.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 4 ms 296 KB Output is correct
4 Correct 4 ms 296 KB Output is correct
5 Correct 7 ms 296 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 5 ms 208 KB Output is correct
8 Correct 4 ms 208 KB Output is correct
9 Correct 3 ms 300 KB Output is correct
10 Correct 5 ms 208 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 292 KB Output is correct
2 Correct 6 ms 292 KB Output is correct
3 Correct 4 ms 296 KB Output is correct
4 Correct 3 ms 292 KB Output is correct
5 Correct 5 ms 272 KB Output is correct
6 Correct 5 ms 208 KB Output is correct
7 Correct 5 ms 292 KB Output is correct
8 Correct 3 ms 296 KB Output is correct
9 Correct 5 ms 208 KB Output is correct
10 Correct 5 ms 208 KB Output is correct
11 Correct 8 ms 300 KB Output is correct
12 Correct 4 ms 208 KB Output is correct
13 Correct 5 ms 336 KB Output is correct
14 Correct 8 ms 208 KB Output is correct
15 Correct 13 ms 300 KB Output is correct
16 Partially correct 46 ms 300 KB Partially correct - number of queries: 7454
17 Correct 6 ms 292 KB Output is correct
18 Partially correct 80 ms 296 KB Partially correct - number of queries: 8659
19 Correct 4 ms 208 KB Output is correct
20 Correct 17 ms 208 KB Output is correct
21 Correct 27 ms 292 KB Output is correct
22 Correct 6 ms 296 KB Output is correct
23 Correct 3 ms 272 KB Output is correct
24 Correct 4 ms 296 KB Output is correct
25 Partially correct 22 ms 336 KB Partially correct - number of queries: 5138
26 Partially correct 47 ms 208 KB Partially correct - number of queries: 5098
27 Correct 5 ms 292 KB Output is correct
28 Partially correct 77 ms 208 KB Partially correct - number of queries: 8275
29 Partially correct 65 ms 208 KB Partially correct - number of queries: 6377
30 Partially correct 34 ms 292 KB Partially correct - number of queries: 8571
31 Correct 5 ms 300 KB Output is correct
32 Correct 8 ms 208 KB Output is correct
33 Correct 0 ms 208 KB Output is correct
34 Correct 34 ms 300 KB Output is correct
35 Correct 5 ms 208 KB Output is correct
36 Correct 25 ms 208 KB Output is correct
37 Correct 7 ms 208 KB Output is correct
38 Correct 3 ms 296 KB Output is correct
39 Correct 17 ms 300 KB Output is correct
40 Partially correct 31 ms 336 KB Partially correct - number of queries: 7400
41 Partially correct 51 ms 300 KB Partially correct - number of queries: 5376
42 Partially correct 30 ms 288 KB Partially correct - number of queries: 5376
43 Correct 23 ms 296 KB Output is correct
44 Correct 25 ms 208 KB Output is correct
45 Correct 33 ms 208 KB Output is correct
46 Correct 7 ms 208 KB Output is correct
47 Correct 43 ms 300 KB Output is correct
48 Partially correct 46 ms 208 KB Partially correct - number of queries: 6529
49 Correct 13 ms 272 KB Output is correct
50 Partially correct 70 ms 208 KB Partially correct - number of queries: 8654
51 Correct 29 ms 208 KB Output is correct
52 Correct 6 ms 208 KB Output is correct
53 Correct 7 ms 208 KB Output is correct
54 Correct 31 ms 292 KB Output is correct
55 Correct 4 ms 208 KB Output is correct
56 Partially correct 54 ms 208 KB Partially correct - number of queries: 8641
57 Partially correct 51 ms 348 KB Partially correct - number of queries: 6440
58 Partially correct 38 ms 296 KB Partially correct - number of queries: 6554
59 Partially correct 42 ms 300 KB Partially correct - number of queries: 5376
60 Partially correct 40 ms 208 KB Partially correct - number of queries: 5030
61 Correct 7 ms 208 KB Output is correct
62 Correct 3 ms 300 KB Output is correct
63 Correct 7 ms 292 KB Output is correct
64 Correct 8 ms 280 KB Output is correct
65 Correct 7 ms 208 KB Output is correct
66 Correct 46 ms 208 KB Output is correct
67 Correct 6 ms 300 KB Output is correct
68 Partially correct 68 ms 208 KB Partially correct - number of queries: 8993
69 Correct 37 ms 208 KB Output is correct
70 Correct 5 ms 296 KB Output is correct
71 Partially correct 88 ms 208 KB Partially correct - number of queries: 8852
72 Correct 8 ms 208 KB Output is correct
73 Partially correct 68 ms 208 KB Partially correct - number of queries: 8733
74 Partially correct 79 ms 208 KB Partially correct - number of queries: 8786
75 Correct 4 ms 208 KB Output is correct
76 Partially correct 31 ms 208 KB Partially correct - number of queries: 7578
77 Partially correct 82 ms 208 KB Partially correct - number of queries: 8740
78 Correct 12 ms 208 KB Output is correct
79 Correct 43 ms 208 KB Output is correct
80 Partially correct 68 ms 208 KB Partially correct - number of queries: 8712
81 Partially correct 79 ms 208 KB Partially correct - number of queries: 8699
82 Partially correct 89 ms 208 KB Partially correct - number of queries: 8654
83 Correct 4 ms 208 KB Output is correct
84 Partially correct 70 ms 208 KB Partially correct - number of queries: 7192
85 Partially correct 83 ms 208 KB Partially correct - number of queries: 8729
86 Partially correct 76 ms 208 KB Partially correct - number of queries: 7671
87 Correct 8 ms 208 KB Output is correct
88 Partially correct 44 ms 208 KB Partially correct - number of queries: 6733
89 Correct 42 ms 208 KB Output is correct
90 Correct 6 ms 208 KB Output is correct
91 Correct 31 ms 208 KB Output is correct
92 Partially correct 51 ms 208 KB Partially correct - number of queries: 6047
93 Partially correct 72 ms 208 KB Partially correct - number of queries: 8336
94 Partially correct 74 ms 208 KB Partially correct - number of queries: 8629
95 Partially correct 78 ms 208 KB Partially correct - number of queries: 8534
96 Partially correct 69 ms 208 KB Partially correct - number of queries: 8630
97 Partially correct 64 ms 208 KB Partially correct - number of queries: 7982