| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1083242 | Math4Life2020 | Ancient Books (IOI17_books) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
int triv(int N1) {
for (ll i=0;i<N1;i++) {
int *a0 = ask((int)i);
if ((a0[0]+a0[1])==0) {
return i;
}
}
return -1;
}
map<ll,pii> pts;
ll N;
ll gm;
ll ans = -1;
vector<bool> asked;
ll process(ll x) {
if (!asked[x]) {
int *a0 = ask((int)x);
pts[x]={a0[0],a0[1]};
asked[x]=1;
}
ll S = pts[x].first+pts[x].second;
if (S==0) {
return x;
}
if (S<gm) {
ll y = -1;
if (x>0 && !asked[x-1]) {
y=max(y,process(x-1));
}
if (x<(N-1) && !asked[x+1]) {
y=max(y,process(x+1));
}
return y;
}
return -1;
}
void query(ll a, ll b) {
if ((a+1)==b) {
return;
}
if (pts[a].first==pts[b].first) {
return;
}
ll c = (a+b)/2;
ans=max(ans,process(c));
if (ans!=-1) {
return;
}
auto A1 = pts.find(a); A1++;
query(a,(*A1).first);
auto B1 = pts.find(b); B1--;
query((*B1).first,b);
}
int find_best(int N0) {
N=N0;
gm=0;
ans = -1;
pts.clear();
asked.clear();
for (ll i=0;i<N;i++) {
asked.push_back(0);
}
if (N<=5000) {
return triv(N);
}
ll r = (N-1)/500;
for (ll i=1;i<=500;i++) {
int *a0 = ask((int)(i*r));
asked[i*r]=1;
pts[i*r]={a0[0],a0[1]};
}
for (auto A: pts) {
pii p0 = A.second;
gm = max(gm,p0.first+p0.second);
}
for (auto A: pts) {
ll v = process(A.first);
if (v!=-1) {
return v;
}
}
if (process(0)!=-1) {
return 0;
}
if (process(N-1)!=-1) {
return (N-1);
}
auto A = pts.begin(); auto B=A; B++;
do {
pii pa = (*A).second; pii pb = (*B).second;
if ((pa.first+pa.second+pb.first+pb.second)==(2*gm)) {
query((*A).first,(*B).first);
if (ans != -1) {
return ans;
}
}
A++; B++;
} while (B != pts.end());
return -1;
}