제출 #73420

#제출 시각아이디문제언어결과실행 시간메모리
73420Sa1378커다란 상품 (IOI17_prize)C++17
20 / 100
1064 ms3128 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; #define N ((int)201*1000) int n,lft[N],rght[N]; int fen[N]; bool mark[N]; int query2(int x) { x++; int res=0; for(;x<=n+1;x+=x&-x)res+=fen[x]; return res; } void add(int x) { mark[x]=1; x++; for(;x>0;x-=x&-x)fen[x]++; } bool query(int x) { if(lft[x]+rght[x]>0)return 0; vector <int> vec;vec=ask(x); lft[x]=vec[0];rght[x]=vec[1]; return (lft[x]+rght[x]==0); } int find_best(int n2) { n=n2; int now=0,id; queue <pair<int,int> > q; q.push({-1,n}); for(int i=0;i<300 && q.size();i++) { int l=q.front().first,r=q.front().second;q.pop(); int mid=(l+r)/2; if(query(mid))return mid; if(now<lft[mid]+rght[mid]) now=lft[mid]+rght[mid],id=mid; if(mid<r-1)q.push({mid,r}); if(l<mid-1)q.push({l,mid}); } while(q.size())q.pop(); q.push({-1,n}); for(int i=0;i<300 && q.size();i++) { int l=q.front().first,r=q.front().second;q.pop(); int mid=(l+r)/2; if(now>lft[mid]+rght[mid]) add(mid); if(mid<r-1)q.push({mid,r}); if(l<mid-1)q.push({l,mid}); } while(1) { int l=-1,r=n; while(l<r-1) { int mid=(l+r)/2; for(int i=0;;i++) { if(mid+i<r && !mark[mid+i]) { mid=mid+i; break; } if(mid-i>l && !mark[mid-i]) { mid=mid-i; break; } } if(query(mid))return mid; if(lft[mid]+rght[mid]<now) { add(mid); break; } if((rght[mid]-query2(mid))-(rght[r]-query2(r))>0)l=mid; else r=mid; } } }

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:37:12: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  int now=0,id;
            ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...