oj.uz

Submission #333280

# Submission time Handle Problem Language Result Execution time Memory
333280 2020-12-05T07:28:41 Z kshitij_sodani Hiring (IOI09_hiring) C++14
100 / 100
 526 ms 61120 KB 
//#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 4 ms 968 KB Output is correct
11 Correct 5 ms 1224 KB Output is correct
12 Correct 6 ms 1352 KB Output is correct
13 Correct 6 ms 1412 KB Output is correct
14 Correct 11 ms 1928 KB Output is correct
15 Correct 11 ms 2072 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 15 ms 2428 KB Output is correct
5 Correct 48 ms 6764 KB Output is correct
6 Correct 307 ms 35008 KB Output is correct
7 Correct 410 ms 50112 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 14316 KB Output is correct
2 Correct 103 ms 14316 KB Output is correct
3 Correct 100 ms 14316 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 25304 KB Output is correct
2 Correct 186 ms 25304 KB Output is correct
3 Correct 185 ms 25432 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 55104 KB Output is correct
2 Correct 453 ms 54976 KB Output is correct
3 Correct 457 ms 55104 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 61120 KB Output is correct
2 Correct 523 ms 60992 KB Output is correct
3 Correct 525 ms 60736 KB Output is correct