oj.uz

Submission #907573

# Submission time Handle Problem Language Result Execution time Memory
907573 2024-01-15T21:24:05 Z Mathias Hiring (IOI09_hiring) C++14
100 / 100
 755 ms 46344 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int MAXN = 5e5+7;
const ll INF = 1e18;
ll m[MAXN];
ll q[MAXN];
pair<ld,ll> t[MAXN];
multiset<pair<ld,ll> >s;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll suma=0,res=0,n,b;
	pair<ld,ll> p;
	ld mini=INF;
	ld st,x;
	cin>>n>>b;
	for(int i=1;i<=n;i++){
		cin>>m[i]>>q[i];
		st=(ld)m[i]/(ld)q[i];
		t[i]={st,i};
	}
	sort(t+1,t+n+1);
	for(int i=1;i<=n;i++){
		s.insert({-q[t[i].second],t[i].second});
		suma+=q[t[i].second];
		x=t[i].first;
		while(1){
			if((ld)suma*x<=(ld)b) break;
			p=*s.begin();
			suma+=p.first;
			s.erase(s.begin());
		}
		if(s.size()>res){
			res=s.size();
			mini=suma*x;
		}
		else if(s.size()==res){
			mini=min(mini,(ld)suma*x);
		}
	}
	s.clear(); suma=0;
	for(int i=1;i<=n;i++){
		s.insert({-q[t[i].second],t[i].second});
		suma+=q[t[i].second];
		x=t[i].first;
		while(1){
			if((ld)suma*x<=(ld)b) break;
			p=*s.begin();
			suma+=p.first;
			s.erase(s.begin());
		}
		if(s.size()==res and mini==(ld)suma*x){
			break;
		}
	}
	cout<<res<<'\n';
	for(auto xd:s){
		cout<<xd.second<<'\n';
	}
	return 0;
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:34:14: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   34 |   if(s.size()>res){
      |      ~~~~~~~~^~~~
hiring.cpp:38:19: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |   else if(s.size()==res){
      |           ~~~~~~~~^~~~~
hiring.cpp:53:14: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   53 |   if(s.size()==res and mini==(ld)suma*x){
      |      ~~~~~~~~^~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 4 ms 4832 KB Output is correct
11 Correct 5 ms 6748 KB Output is correct
12 Correct 6 ms 7256 KB Output is correct
13 Correct 5 ms 7092 KB Output is correct
14 Correct 9 ms 7256 KB Output is correct
15 Correct 10 ms 7260 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 13 ms 7636 KB Output is correct
5 Correct 27 ms 8236 KB Output is correct
6 Correct 323 ms 30624 KB Output is correct
7 Correct 455 ms 39696 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 13160 KB Output is correct
2 Correct 107 ms 13396 KB Output is correct
3 Correct 96 ms 13356 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 22864 KB Output is correct
2 Correct 147 ms 22736 KB Output is correct
3 Correct 148 ms 22868 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 41848 KB Output is correct
2 Correct 562 ms 41932 KB Output is correct
3 Correct 481 ms 41848 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 46188 KB Output is correct
2 Correct 755 ms 46344 KB Output is correct
3 Correct 721 ms 46164 KB Output is correct