# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
925962 | 2024-02-12T12:02:30 Z | boris_mihov | Hiring (IOI09_hiring) | C++17 | 0 ms | 0 KB |
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <queue> #include <set> typedef long long llong; const int MAXN = 500000 + 10; const int INF = 1e9; int n; llong s[MAXN]; llong q[MAXN]; int perm[MAXN]; std::priority_queue <std::pair <llong,int>> pq; llong sum; llong w; void solve() { std::iota(perm + 1, perm + 1 + n, 1); std::sort(perm + 1, perm + 1 + n, [&](int x, int y) { return s[x] * q[y] < s[y] * q[x]; }); int ans = 0; int cnt = 0; int maxPos = 0; for (int i = 1 ; i <= n ; ++i) { pq.push({q[perm[i]], perm[i]}); sum += q[perm[i]]; cnt++; while (sum * s[perm[i]] > w * q[perm[i]]) { cnt--; sum -= pq.top().first; pq.pop(); } if (cnt > ans) { maxPos = i; ans = cnt; } } while (pq.size()) { pq.pop(); } sum = 0; cnt = 0; std::cout << ans << '\n'; for (int i = 1 ; i <= maxPos ; ++i) { pq.push({q[perm[i]], perm[i]}); sum += q[perm[i]]; cnt++; while (sum * s[perm[i]] > w * q[perm[i]]) { cnt--; sum -= pq.top().first; pq.pop(); } } assert(pq.size() == ans); std::set <int> s; while (pq.size()) { std::cout << pq.top().second << '\n'; assert(!s.count(pq.top().second)); s.inside(pq.top().second); pq.pop(); } } void input() { std::cin >> n >> w; for (int i = 1 ; i <= n ; ++i) { std::cin >> s[i] >> q[i]; } } void fastIOI() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int main() { fastIOI(); input(); solve(); return 0; }