이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int L[200000],R[200000],tree[1<<19];
void update(int x){
x+=1<<18;
while(x){
tree[x]++;
x/=2;
}
}
int calc(int l,int r){
l+=1<<18;
r+=1<<18;
int a=0;
while(l<r){
if(l&1)a+=tree[l];
if(~r&1)a+=tree[r];
l=(l+1)/2;
r=(r-1)/2;
}
if(l==r)a+=tree[l];
return a;
}
int find_best(int n){
for(int i=0;i<n;i++){
L[i]=R[i]=-1;
}
int s=-1;
mt19937 E(869120);
for(int i=0;i<min(600,n);i++){
int t;
do{
t=E()%n;
}while(L[t]!=-1);
vector<int>v=ask(t);
L[t]=v[0];
R[t]=v[1];
s=max(s,L[t]+R[t]);
}
int last_val=-1;
for(int i=0;i<s;i++){
int l=last_val;
int r=n-1;
while(l+1!=r){
int m=(l+l+r)/3;
if(l==m)m++;
if(L[m]==-1){
vector<int>v=ask(m);
L[m]=v[0];
R[m]=v[1];
}
if(L[m]+R[m]!=s){
r=m;
}
else if(L[m]-calc(0,m)>0){
r=m;
}
else{
l=m;
}
}
if(L[r]==-1){
vector<int>v=ask(r);
L[r]=v[0];
R[r]=v[1];
}
update(r);
if(L[r]==0&&R[r]==0){
return r;
}
last_val=r;
}
return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |