Submission #1009695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009695		ZeroCool	Hiring (IOI09_hiring)	C++14	60 / 100	212 ms	24820 KiB

hiring

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array
#define int long long
#define ld long double

const int N = (1 << 18) + 20;
const int M = 105;
const int MOD = 998244353;

struct Node{
	int s, q, id;


	bool operator<(Node o) const {
		return s * o.q < q * o.s;
	}
	
};

signed main(){ios::sync_with_stdio(false);cin.tie(0);
	int n, w;
	cin>>n>>w;
	//cout<<n;
	Node A[n];
	for(int i = 0;i < n;i++){
		cin>>A[i].s>>A[i].q;
		A[i].id = i;
	}
	
	sort(A, A+n);
	int l = 0;
	int ans = 0;
	int sum = 0;
	priority_queue<int> q;
	for(int r = 0;r < n;r++){
		sum += A[r].q;
		q.push(A[r].q);
		while(sum * A[r].s > w * A[r].q){
			sum -= q.top();
			q.pop();
		}
		ans = max(ans, (int)q.size());
	}
	sum = 0;
	cout<<ans<<'\n';
	if(ans){
		priority_queue<ar<int, 2>> q;
		for(int r = 0;r < n;r++){
			sum += A[r].q;
			q.push({A[r].q, A[r].id});
			while(sum * A[r].s > w * A[r].q){
				sum -= q.top()[0];
				q.pop();
			}
			if(q.size() == ans){
				while(q.size()){
					cout<<q.top()[1] + 1<<'\n';
					q.pop();
				}
				
				return 0;
				return 0;
			}
		}
	}
}	

// abba
//baab

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:58:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |    if(q.size() == ans){
      |       ~~~~~~~~~^~~~~~
hiring.cpp:34:6: warning: unused variable 'l' [-Wunused-variable]
   34 |  int l = 0;
      |      ^

• Subtask 1: 19 / 30
• Subtask 2: 20 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 3 / 6
• Subtask 8: 3 / 6
• Subtask 9: 3 / 6