Submission #522253

#	Time	Username	Problem	Language	Result	Execution time	Memory
522253		new_acc	Hiring (IOI09_hiring)	C++14	100 / 100	477 ms	27988 KiB

hiring

#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 (stderr)

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 / 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