| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 520404 | AdamGS | The Big Prize (IOI17_prize) | 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.
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int tr[4*LIM], ile, N=1;
int T[LIM][2], wynik=-1;
void pytaj(int x) {
if(T[x][0]!=-1) return;
vector<int>V=ask(x);
T[x][0]=V[0];
T[x][1]=V[1];
if(T[x][0]+T[x][1]==0) wynik=x;
}
void upd(int v) {
v+=N;
tr[v]=1;
v/=2;
while(v) {
tr[v]=tr[2*v]+tr[2*v+1];
v/=2;
}
}
int cnt(int l, int r) {
if(r<l) return 0;
l+=N; r+=N;
int ans=tr[l];
if(l!=r) ans+=tr[r];
while(l/2!=r/2) {
if(l%2==0) ans+=tr[l+1];
if(r%2==1) ans+=tr[r-1];
l/=2; r/=2;
}
return ans;
}
void solve(int l, int r) {
int mid=(l+r)/2;
pytaj(mid);
if(wynik!=-1) return;
while(T[mid][0]+T[mid][1]<ile && mid<r) {
upd(mid);
++mid;
pytaj(mid);
if(wynik!=-1) return;
}
if(T[mid][0]+T[mid][1]<ile) {
upd(mid);
mid=(l+r)/2;
pytaj(mid);
if(wynik!=-1) return;
while(T[mid][0]+T[mid][1]<ile && mid>l) {
upd(mid);
--mid;
pytaj(mid);
if(wynik!=-1) return;
}
if(T[mid][0]+T[mid][1]<ile) return;
}
if(cnt(0, mid-1)<T[mid][0]) solve(l, mid-1);
if(wynik!=-1) return;
if(cnt(mid+1, n-1)<T[mid][1]) solve(mid+1, r);
}
int find_best(int n) {
rep(i, n) T[i][0]=-1;
while(N<n) N*=2;
rep(i, min(n, 500)) {
pytaj(i);
ile=max(ile, T[i][0]+T[i][1]);
if(wynik!=-1) return i;
}
solve(0, n-1);
return wynik;
}