제출 #387971

#제출 시각아이디문제언어결과실행 시간메모리
387971Bill_00Hiring (IOI09_hiring)C++14
80 / 100
1590 ms59484 KiB
#include <bits/stdc++.h> #define pb push_back #define ff first #define ss second #define ll long long #define N 500005 const int c=1000; using namespace std; struct node{ double sum; int cnt; }; node a[4*N]; ll w; int n,in[N]; double s[N],q[N]; pair<int,pair<double,int> >ans; vector<pair<double,int> >e; vector<pair<pair<double,double>,int> >v; int query(int id,int l,int r,int k){ if(l==r){ return l; } int m=l+r>>1; if(a[id*2].cnt>=k){ return query(id*2,l,m,k); } else return query(id*2+1,m+1,r,k-a[id*2].cnt); } double querysum(int id,int l,int r,int k){ if(k<l) return 0; if(r<=k) return a[id].sum; int m=l+r>>1; return querysum(id*2,l,m,k)+querysum(id*2+1,m+1,r,k); } void update(int id,int l,int r,int k,double u){ if(l==r){ a[id].sum+=u; ++a[id].cnt; return; } int m=l+r>>1; if(m>=k) update(id*2,l,m,k,u); else update(id*2+1,m+1,r,k,u); a[id].sum=a[id*2].sum+a[id*2+1].sum; ++a[id].cnt; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> w; for(int i=1;i<=n;i++){ cin >> s[i] >> q[i]; v.pb({{s[i]/q[i],q[i]},i}); } sort(v.begin(),v.end()); for(int i=0;i<v.size();i++){ e.pb({v[i].ff.ss,i}); } sort(e.begin(),e.end()); for(int i=0;i<e.size();i++){ in[e[i].ss]=i; } for(int i=0;i<v.size();i++){ int l=1,r=i,p=0; double x=v[i].ff.ss,y=v[i].ff.ff; double z=x*y; // cout << l << ' ' << r << ' ' << z << '\n'; while(l<=r){ int m=l+r>>1; int k=query(1,0,n-1,m); double res=querysum(1,0,n-1,k); // cout << l << ' ' << r << ' ' << res << '\n'; if(((res+x)*y)<=w){ p=m; z=max(z,(res+x)*y); l=m+1; // cout << i << ' ' << l << ' ' << r << ' '<< z << '\n'; } else r=m-1; } ans=max(ans,{p,{-z,i}}); update(1,0,n-1,in[i],x); } vector<pair<double,int> >t; for(int i=0;i<ans.ss.ss;i++){ t.pb({v[i].ff.ss,v[i].ss}); } sort(t.begin(),t.end()); cout << ans.ff+1 << '\n'; cout << v[ans.ss.ss].ss << '\n'; for(int i=0;i<ans.ff;i++){ cout << t[i].ss << '\n'; } }

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

hiring.cpp: In function 'int query(int, int, int, int)':
hiring.cpp:24:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int m=l+r>>1;
      |        ~^~
hiring.cpp: In function 'double querysum(int, int, int, int)':
hiring.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m=l+r>>1;
      |        ~^~
hiring.cpp: In function 'void update(int, int, int, int, double)':
hiring.cpp:42:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int m=l+r>>1;
      |        ~^~
hiring.cpp: In function 'int main()':
hiring.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
hiring.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<e.size();i++){
      |              ~^~~~~~~~~
hiring.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
hiring.cpp:71:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |    int m=l+r>>1;
      |          ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...