#include "prize.h"
#include <bits/stdc++.h>
#define endl "\n"
#define yeap cout<<"YES"<<endl
#define nope cout<<"NO"<<endl
#define ll long long
using namespace std;
const ll max_gems = 480;
bool gems[200005];
std::vector<pair<ll,ll>> response;
vector<int> askk(int i) {
if(response[i] == make_pair(-1ll, -1ll)) {
vector<int> res = ask(i);
response[i] = make_pair(res[0], res[1]);
return res;
}
vector<int> res;
res.push_back(response[i].first);
res.push_back(response[i].second);
return res;
}
int find_best(int n) {
ll mx = 0;
ll mxind = 0;
response.resize(n+5, {-1,-1});
for(int i=1; i<=max_gems; i++){
std::vector<int> v = askk(i-1);
ll a = v[0];
ll b = v[1];
ll c = a+b;
if(c==0){
return i-1;
}
if(c >= mx){
mx = c;
mxind = i-1;
}
}
for(int i=1; i<=max_gems; i++){
std::vector<int> v = askk(i-1);
ll a = v[0];
ll b = v[1];
ll c = a+b;
if(c==0){
return (i-1);
}
if(c != mx){
gems[i-1] = true;
}
}
////////////////////////////////// Thik ache /////////////////////////////////
int cur_lolipop = max_gems, left, right;
while(true) {
// cout << cur_lolipop << " " << 79 << endl;
vector<int> v = askk(cur_lolipop);
ll a = v[0];
ll b = v[1];
ll c = a+b;
if(c==0){
return cur_lolipop;
}
if(c != mx){
gems[cur_lolipop] = true;
cur_lolipop++;
} else {
left = a, right = b;
break;
}
}
while(right != 0) {
// cout << l << " " << r << endl;
int l = cur_lolipop+1, r = n-1;
// cout << l << " " << r << endl;
while(l < r) {
int mid = (l+r)/2;
// cout << mid << " " << 105 << endl;
vector<int> v = askk(mid);
ll a = v[0];
ll b = v[1];
ll c = a+b;
// cout << c << endl;
if(c==0){
return mid;
}
if(c < left + right) {
gems[mid] == true;
r = mid;
} else if(a == left) {
l = mid+1;
for(int i = l; i <= mid; i++) {
response[i] = {left, right};
}
} else {
r = mid - 1;
}
}
gems[l] = true;
cur_lolipop = l+1;
if(cur_lolipop==n){
return cur_lolipop;
}
while(true) {
// cout << cur_lolipop << " " << 134 << endl;
vector<int> v = askk(cur_lolipop);
ll a = v[0];
ll b = v[1];
ll c = a+b;
if(c==0){
return cur_lolipop;
}
if(c != mx){
gems[cur_lolipop] = true;
cur_lolipop++;
} else {
left = a, right = b;
break;
}
}
}
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:124:27: warning: statement has no effect [-Wunused-value]
124 | gems[mid] == true;
| ~~~~~~~~~~^~~~~~~
prize.cpp:37:5: warning: variable 'mxind' set but not used [-Wunused-but-set-variable]
37 | ll mxind = 0;
| ^~~~~
prize.cpp:175:1: warning: control reaches end of non-void function [-Wreturn-type]
175 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3416 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3416 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3416 KB |
Integer 200000 violates the range [0, 199999] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3416 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3416 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3416 KB |
Integer 200000 violates the range [0, 199999] |
| 5 |
Halted |
0 ms |
0 KB |
- |
