Submission #970967

#	Time	Username	Problem	Language	Result	Execution time	Memory
970967		aZvezda	Hiring (IOI09_hiring)	C++14	100 / 100	271 ms	26600 KiB

hiring

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

#ifndef LOCAL
#define cerr if (false) cerr
#endif
#define endl "\n"

template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
const ll mod = 1e9 + 7;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//

const ll MAX_N  = 5e5 + 10;
std::pair<std::pair<ll, ll>, ll> arr[MAX_N];
ll n, w;

signed main() {
#ifndef LOCAL
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#endif
	cin >> n >> w;
	for (ll i = 0; i < n; i ++) {
		cin >> arr[i].first.first >> arr[i].first.second;
		arr[i].second = i;
	}

	std::sort(arr, arr + n, [](const auto &x, const auto &y) {
		if (x.first.first * y.first.second == x.first.second * y.first.first) {
			return x.first.second < y.first.second;
		}
		return x.first.first * y.first.second < x.first.second * y.first.first;
	});

	ll best = 0;
	long double best2 = 1e18;
	ll best_ind = -1;

	{
		std::priority_queue<std::pair<ll, ll> > pq = {};
		ll sum = 0;
		for (ll i = 0; i < n; i ++) {
			sum += arr[i].first.second;
			pq.push({arr[i].first.second, i});
			if (i != n - 1 && (arr[i].first.first * arr[i + 1].first.second == arr[i].first.second * arr[i + 1].first.first)) {
				continue;
			}
			while (sum * arr[i].first.first > w * arr[i].first.second) {
				sum -= pq.top().first;
				pq.pop();
			}
			long double curr = (long double)sum / arr[i].first.second * (long double)arr[i].first.first;
			if (pq.size() > best) {
				best = pq.size();
				best_ind = i;
				best2 = curr;
			} else if(pq.size() == best) {
				if (best2 > curr) {
					best2 = curr;
					best_ind = i;
				}
			}
		}
	}

	{
		std::priority_queue<std::pair<ll, ll> > pq = {};
		ll sum = 0;
		for (ll i = 0; i <= best_ind; i ++) {
			sum += arr[i].first.second;
			pq.push({arr[i].first.second, arr[i].second});
		}

		while (sum * arr[best_ind].first.first > w * arr[best_ind].first.second) {
			sum -= pq.top().first;
			pq.pop();
		}

		std::cout << pq.size() << endl;
		std::vector<ll> ret = {};
		while(!pq.empty()) {
			ret.push_back(pq.top().second + 1);
			pq.pop();
		}
		std::sort(ret.begin(), ret.end());
		for (const auto it : ret) {
			std::cout << it << endl;
		}
	}

	return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:55:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   55 |    if (pq.size() > best) {
      |        ~~~~~~~~~~^~~~~~
hiring.cpp:59:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   59 |    } else if(pq.size() == best) {
      |              ~~~~~~~~~~^~~~~~~

• 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