Submission #970951

#	Time	Username	Problem	Language	Result	Execution time	Memory
970951		aZvezda	Hiring (IOI09_hiring)	C++14	55 / 100	271 ms	26636 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<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 >> arr[i].second;
	}

	if (n <= 20) {
		#define HAS(mask, x) ((bool)(mask & (1 << i)))

		ll mx = 0;
		long double ans = 0;
		ll who = 0;
		for (int mask = 0; mask < (1 << n); mask ++) {
			ll sum = 0;
			long double mn = 0;
			for (int i = 0; i < n; i ++) if (HAS(mask, i)) {
				sum += arr[i].second;
				chkmax(mn, (long double)arr[i].first / arr[i].second);
			}

			ll total = __builtin_popcount(mask);
			if (total > mx && sum * mn <= w) {
				mx = total;
				ans = sum * mn;
				who = mask;
			} else if(total == mx && sum * mn <= ans) {
				ans = sum * mn;
				who = mask;
			}
		}

		std::cout << __builtin_popcount(who) << endl;
		for (int i = 0; i < n; i ++) if (HAS(who, i)) {
			std::cout << i + 1 << endl;
		}
		return 0;
	}

	std::sort(arr, arr + n, [](const auto &x, const auto &y) {
		if (x.first * y.second == x.second * y.first) {
			return x.second < y.second;
		}
		return x.first * y.second < x.second * y.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].second;
			pq.push({arr[i].second, i});
			if (i != n - 1 && (arr[i].first * arr[i + 1].second == arr[i].second * arr[i + 1].first)) {
				continue;
			}
			while (sum * arr[i].first > w * arr[i].second) {
				sum -= pq.top().first;
				pq.pop();
			}
			long double curr = (long double)sum / arr[i].second * (long double)arr[i].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].second;
			pq.push({arr[i].second, i});
		}

		while (sum * arr[best_ind].first > w * arr[best_ind].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:86: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]
   86 |    if (pq.size() > best) {
      |        ~~~~~~~~~~^~~~~~
hiring.cpp:90: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]
   90 |    } else if(pq.size() == best) {
      |              ~~~~~~~~~~^~~~~~~

• Subtask 1: 20 / 30
• Subtask 2: 14 / 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