제출 #405426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405426		Jasiekstrz	Hiring (IOI09_hiring)	C++17	40 / 100	1592 ms	23444 KiB

hiring

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=5e5;
struct Worker
{
	long long s,q;
	int id;
	Worker(long long _s=0,long long _q=1,int _id=0) : s(_s), q(_q), id(_id) {};
	bool operator<(const Worker &oth) const
	{
		return s*oth.q<oth.s*q;
	}
	bool operator<=(const Worker &oth) const
	{
		return s*oth.q<=oth.s*q;
	}
};
Worker tab[N+10];
priority_queue<pair<int,int>> us,nus;
Worker solve(int n,long long w,int mid,Worker brk)
{
	while(!us.empty())
		us.pop();
	while(!nus.empty())
		nus.pop();
	Worker mn={w+1,1};
	long long sum=0;
	for(int i=1;i<=n;i++)
	{
		if(us.size()==mid-1)
			mn=min(mn,Worker((sum+tab[i].q)*tab[i].s,tab[i].q));
		if(mn.s*brk.q==mn.q*brk.s)
		{
			us.push({tab[i].q,i});
			return mn;
		}
		if(us.size()==mid-1 && mid>1)
		{
			sum-=us.top().fi;
			nus.push({-us.top().fi,us.top().se});
			us.pop();
		}
		nus.push({-tab[i].q,i});
		if(mid>1)
		{
			us.push({-nus.top().fi,nus.top().se});
			sum-=nus.top().fi;
			nus.pop();
		}
	}
	return mn;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	long long w;
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	{
		cin>>tab[i].s>>tab[i].q;
		tab[i].id=i;
	}
	sort(tab+1,tab+n+1);
	int bg=0,en=n;
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		if(solve(n,w,mid,Worker(-1,1))<=Worker(w,1))
			bg=mid;
		else
			en=mid-1;
	}
	cout<<bg<<"\n";
	solve(n,w,bg,solve(n,w,bg,Worker(-1,1)));
	while(!us.empty())
	{
		cout<<us.top().se<<"\n";
		us.pop();
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

hiring.cpp: In function 'Worker solve(int, long long int, int, Worker)':
hiring.cpp:32:15: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |   if(us.size()==mid-1)
      |      ~~~~~~~~~^~~~~~~
hiring.cpp:39:15: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |   if(us.size()==mid-1 && mid>1)
      |      ~~~~~~~~~^~~~~~~

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