oj.uz

Submission #970951

# Submission time Handle Problem Language Result Execution time Memory
970951 2024-04-27T15:53:55 Z aZvezda Hiring (IOI09_hiring) C++14
55 / 100
 271 ms 26636 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 10 ms 504 KB Output is correct
5 Correct 75 ms 348 KB Output is correct
6 Partially correct 1 ms 504 KB Partially correct
7 Partially correct 1 ms 344 KB Partially correct
8 Partially correct 1 ms 348 KB Partially correct
9 Partially correct 2 ms 604 KB Partially correct
10 Partially correct 2 ms 544 KB Partially correct
11 Partially correct 3 ms 600 KB Partially correct
12 Partially correct 4 ms 860 KB Partially correct
13 Partially correct 3 ms 604 KB Partially correct
14 Partially correct 6 ms 3084 KB Partially correct
15 Partially correct 6 ms 3092 KB Partially correct

Subtask #2
14.0 / 28.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 8 ms 3040 KB Partially correct
5 Partially correct 19 ms 3676 KB Partially correct
6 Partially correct 148 ms 16324 KB Partially correct
7 Partially correct 190 ms 24120 KB Partially correct

Subtask #3
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 344 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct

Subtask #4
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 604 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct

Subtask #5
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct

Subtask #6
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 56 ms 6748 KB Partially correct
2 Partially correct 55 ms 6960 KB Partially correct
3 Partially correct 55 ms 6744 KB Partially correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 89 ms 14712 KB Partially correct
2 Partially correct 88 ms 13708 KB Partially correct
3 Partially correct 93 ms 14912 KB Partially correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 230 ms 25896 KB Partially correct
2 Partially correct 229 ms 25812 KB Partially correct
3 Partially correct 230 ms 25608 KB Partially correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 271 ms 26032 KB Partially correct
2 Partially correct 264 ms 26144 KB Partially correct
3 Partially correct 263 ms 26636 KB Partially correct