Submission #1009696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009696		ZeroCool	Hiring (IOI09_hiring)	C++14	100 / 100	221 ms	19784 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;
	pair<int, ld> ans = {0, 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 * 1.0 * A[r].s / A[r].q});
	}
	sum = 0;
	cout<<ans.first<<'\n';
	if(ans.first){
		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.first && -sum * 1.0 * A[r].s / A[r].q == ans.second){
				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.first && -sum * 1.0 * A[r].s / A[r].q == ans.second){
      |       ~~~~~~~~~^~~~~~~~~~~~
hiring.cpp:34:6: warning: unused variable 'l' [-Wunused-variable]
   34 |  int l = 0;
      |      ^

• 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