제출 #302188

#제출 시각아이디문제언어결과실행 시간메모리
302188TMJN커다란 상품 (IOI17_prize)C++17
20 / 100
67 ms3556 KiB
#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]); } for(int i=0;i<s;i++){ int l=-1; int r=n-1; while(l+1!=r){ int m=(l+r)/2; 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; } } return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...