Submission #333280

#	Time	Username	Problem	Language	Result	Execution time	Memory
333280		kshitij_sodani	Hiring (IOI09_hiring)	C++14	100 / 100	526 ms	61120 KiB

hiring

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,w;
llo aa[500001];
llo bb[500001];
llo ind[500001];
bool cmp(pair<pair<llo,llo>,llo> cc,pair<pair<llo,llo>,llo> dd){
	return cc.a.a*dd.a.b<cc.a.b*dd.a.a;
}
llo tree[500001];
void u(llo i,llo j){
	while(i<=n){
		tree[i]+=j;
		i+=(i&-i);
	}
}
llo s(llo i){
	llo su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
llo tree2[500001];
void u2(llo i,llo j){
	while(i<=n){
		tree2[i]+=j;
		i+=(i&-i);
	}
}
llo s2(llo i){
	llo su=0;
	while(i>0){
		su+=tree2[i];
		i-=(i&-i);
	}
	return su;
}
pair<llo,pair<llo,llo>> ans={0,{0,1}};
llo ma=0;
llo cot=0;
void remax(pair<llo,pair<llo,llo>> cc){

	if(cc.a>ans.a){
		ans=cc;
		ma=cot;
	}
	else if(cc.a==ans.a){
		if(cc.b.a*ans.b.b<cc.b.b*ans.b.a){
			ans=cc;
			ma=cot;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>w;
	vector<pair<pair<llo,llo>,llo>> ss;
	vector<pair<llo,llo>> tt;
	for(llo i=0;i<n;i++){
		cin>>aa[i]>>bb[i];
		ss.pb({{aa[i],bb[i]},i});
		tt.pb({bb[i],i});
	}
	
	sort(ss.begin(),ss.end(),cmp);
	sort(tt.begin(),tt.end());
	for(llo i=0;i<n;i++){
		ind[tt[i].b]=i;
	}
	for(auto j:ss){
		cot++;
		u(ind[j.b]+1,j.a.b);
		u2(ind[j.b]+1,1);
		llo cur=0;
		llo cur2=0;
		//cout<<j.a.a<<"::"<<j.a.b<<endl;
		for(llo i=19;i>=0;i--){
			if(cur+(1<<i)<=n){
				if((cur2+tree[cur+(1<<i)])*j.a.a<=w*j.a.b){
					cur+=(1<<i);
					cur2+=tree[cur];
				}
			}
		}
	//	cout<<s2(cur)<<",,"<<cur<<",,"<<cur2<<endl;

		remax({s2(cur),{cur2*j.a.a,j.a.b}});
	}

	//cout<<ans.a<<" "<<ans.b.a<<","<<ans.b.b<<endl;
	cout<<ans.a<<endl;
	if(ans.a>0){
		vector<pair<llo,llo>> kk;
		for(llo i=0;i<ma;i++){
			kk.pb({ss[i].a.b,ss[i].b});
		}
		sort(kk.begin(),kk.end());
		for(llo i=0;i<ans.a;i++){
			cout<<kk[i].b+1<<endl;
		}
	}


 
 
	return 0;
}

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