This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prize.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define MAXN 200010
#define SQRT 500
#define fi first
#define se second
using namespace std;
int max_type, N, R, key;
pii dp[MAXN];
vector<int> ask1(int idx) {
if(dp[idx] != make_pair(0, 0)) {
vector<int> rez(2);
rez[0] = dp[idx].fi;
rez[1] = dp[idx].se;
return rez;
}
vector<int> rez = ask(idx);
dp[idx] = {rez[0], rez[1]};
return rez;
}
pii nadji_sled(int l, int r) {
int rez = N;
while(l <= r) {
int mid = (l+r)/2;
vector<int> r1 = ask1(mid);
if(r1[0]+r1[1] > max_type) {
rez = mid;
r = mid-1;
}
else if(r1[0]+r1[1] < max_type) {
if(r1[0]+r1[1] == 0) return {1, mid};
rez = mid,
r = mid-1;
}
else if(r1[0] > key) r = mid-1;
else l = mid+1;
}
vector<int> r1 = ask1(rez);
if(r1[0]+r1[1] > max_type) {
max_type = r1[0]+r1[1];
key = r1[0]-1;
}
return {0,rez};
}
bool prazno(int L, int R) {
vector<int> r = ask1(R);
if(r[0]+r[1] < max_type) return false;
if(r[0] > key) return false;
return true;
}
int find_best(int n) {
int za_max = min(n, 474);
N = n;
for(int i = 0; i < za_max; i++) {
vector<int> r = ask1(i);
int cur_ask = r[0] + r[1];
if(cur_ask == 0) return i;
max_type = max(max_type, cur_ask);
}
int tr = -1;
int posl_tr = -1;
int L = 0, R = min(n-1, SQRT);
while(tr < n) {
if(!prazno(L, R)) {
pii sled1 = nadji_sled(L, R);
if(sled1.fi == 1) return sled1.se;
int sled = sled1.se;
key++;
tr = sled;
L = sled1.se+1;
}
else L = R; R = L + SQRT;
L = min(L, n-1), R = min(R, n-1);
}
}
Compilation message (stderr)
prize.cpp: In function 'int find_best(int)':
prize.cpp:73:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
else L = R; R = L + SQRT;
^~~~
prize.cpp:73:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
else L = R; R = L + SQRT;
^
prize.cpp:62:9: warning: unused variable 'posl_tr' [-Wunused-variable]
int posl_tr = -1;
^~~~~~~
prize.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |