oj.uz

Submission #522253

# Submission time Handle Problem Language Result Execution time Memory
522253 2022-02-04T10:25:45 Z new_acc Hiring (IOI09_hiring) C++14
100 / 100
 477 ms 27988 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (int)(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
struct st{
	ll a,b;
	int id;
	bool operator>(st pom){
		return a*pom.b>b*pom.a;
	}
	st operator*(st pom){
		st res;
		res.a=a*pom.a;
		res.b=b*pom.b;
		ll g=__gcd(res.a,res.b);
		res.a/=g,res.b/=g;
		return res;
	}
};
const int N=5e5+10;
st t[N];
void solve(){
	int n,il;
	ll w;
	cin>>n>>w;
	rep(i,n){ cin>>t[i].a>>t[i].b; t[i].id=i;}
	sort(t,t+n,[](st a,st b){
		return b>a;
	});
	multiset<pair<int,int> >mul;
	ll curr=0;
	st mini;
	rep(i,n){
		ll xd=(w*t[i].b)/t[i].a;
		mul.insert({t[i].b,t[i].id});
		curr+=t[i].b;
		while(curr>xd){
			auto it=mul.end();
			it--;
			curr-=(*(it)).fi;
			mul.erase(it);
		}
		if(il<=(int)mul.size()){
			st akt;
			akt.a=curr,akt.b=1;
			akt=akt*t[i];
			if(il<(int)mul.size()) mini=akt;
			else if(mini>akt) mini=akt;
		}
		il=max(il,(int)mul.size());
	}
	mul.clear();
	curr=0;
	rep(i,n){
		ll xd=(w*t[i].b)/t[i].a;
		mul.insert({t[i].b,t[i].id});
		curr+=t[i].b;
		while(curr>xd){
			auto it=mul.end();
			it--;
			curr-=(*(it)).fi;
			mul.erase(it);
		}
		if((int)mul.size()==il){
			st akt;
			akt.a=curr,akt.b=1;
			akt=akt*t[i];
			if(mini.a==akt.a and mini.b==akt.b) break;
		}
	}
	cout<<il<<"\n";
	for(auto it=mul.begin();it!=mul.end();it++) cout<<(*(it)).se+1<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message

hiring.cpp: In function 'void solve()':
hiring.cpp:75:12: warning: 'il' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |  cout<<il<<"\n";
      |            ^~~~
hiring.cpp:72:21: warning: 'mini.st::b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |    if(mini.a==akt.a and mini.b==akt.b) break;
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hiring.cpp:72:4: warning: 'mini.st::a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |    if(mini.a==akt.a and mini.b==akt.b) break;
      |    ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 436 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 5 ms 764 KB Output is correct
13 Correct 5 ms 588 KB Output is correct
14 Correct 8 ms 844 KB Output is correct
15 Correct 8 ms 844 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 12 ms 1248 KB Output is correct
5 Correct 22 ms 2408 KB Output is correct
6 Correct 230 ms 12684 KB Output is correct
7 Correct 317 ms 18484 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5028 KB Output is correct
2 Correct 89 ms 5044 KB Output is correct
3 Correct 84 ms 4988 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 8648 KB Output is correct
2 Correct 120 ms 8768 KB Output is correct
3 Correct 108 ms 8644 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 20936 KB Output is correct
2 Correct 373 ms 24264 KB Output is correct
3 Correct 331 ms 24316 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 24676 KB Output is correct
2 Correct 472 ms 27988 KB Output is correct
3 Correct 452 ms 27952 KB Output is correct