Submission #387971

#	Time	Username	Problem	Language	Result	Execution time	Memory
387971		Bill_00	Hiring (IOI09_hiring)	C++14	80 / 100	1590 ms	59484 KiB

hiring

#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';
	}
}

Compilation message (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;
      |          ~^~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6