제출 #73425

#제출 시각아이디문제언어결과실행 시간메모리
73425Sa1378커다란 상품 (IOI17_prize)C++17
20 / 100
188 ms12612 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; } set <int> s; void add(int x) { mark[x]=1;s.erase(x); 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}); } for(int i=0;i<n;i++)s.insert(i); 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}); } for(int t=0;t<600;t++) { int l=-1,r=n; while(l<r-1) { int mid=(l+r)/2; auto it=s.lower_bound(mid); if(it==s.end() || *it>=r)it--; mid=*it; 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:39:12: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  int now=0,id;
            ^~
prize.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...