oj.uz

답안 #970967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
970967 2024-04-27T16:09:24 Z aZvezda Hiring (IOI09_hiring) C++14
100 / 100
 271 ms 26600 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<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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 5 ms 2828 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Correct 6 ms 3044 KB Output is correct
15 Correct 6 ms 2836 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 2908 KB Output is correct
5 Correct 19 ms 3304 KB Output is correct
6 Correct 146 ms 15532 KB Output is correct
7 Correct 209 ms 23704 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 7780 KB Output is correct
2 Correct 57 ms 7668 KB Output is correct
3 Correct 56 ms 7792 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 14236 KB Output is correct
2 Correct 105 ms 13080 KB Output is correct
3 Correct 89 ms 13464 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 24736 KB Output is correct
2 Correct 236 ms 23540 KB Output is correct
3 Correct 230 ms 24148 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 26152 KB Output is correct
2 Correct 263 ms 26600 KB Output is correct
3 Correct 265 ms 26008 KB Output is correct