# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
925960 | 2024-02-12T12:01:29 Z | boris_mihov | Hiring (IOI09_hiring) | C++17 | 299 ms | 15944 KB |
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <queue> 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); while (pq.size()) { std::cout << pq.top().second << '\n'; 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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 1 ms | 4444 KB | Partially correct |
2 | Partially correct | 1 ms | 4444 KB | Partially correct |
3 | Correct | 1 ms | 4444 KB | Output is correct |
4 | Partially correct | 1 ms | 4444 KB | Partially correct |
5 | Partially correct | 1 ms | 4444 KB | Partially correct |
6 | Partially correct | 1 ms | 4444 KB | Partially correct |
7 | Partially correct | 1 ms | 4444 KB | Partially correct |
8 | Partially correct | 1 ms | 4444 KB | Partially correct |
9 | Correct | 2 ms | 4444 KB | Output is correct |
10 | Partially correct | 3 ms | 4700 KB | Partially correct |
11 | Correct | 3 ms | 4444 KB | Output is correct |
12 | Partially correct | 4 ms | 4700 KB | Partially correct |
13 | Partially correct | 3 ms | 4444 KB | Partially correct |
14 | Correct | 6 ms | 4936 KB | Output is correct |
15 | Partially correct | 9 ms | 4952 KB | Partially correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4440 KB | Output is correct |
2 | Partially correct | 1 ms | 4444 KB | Partially correct |
3 | Correct | 1 ms | 4444 KB | Output is correct |
4 | Partially correct | 8 ms | 4700 KB | Partially correct |
5 | Partially correct | 21 ms | 9184 KB | Partially correct |
6 | Correct | 148 ms | 11008 KB | Output is correct |
7 | Partially correct | 220 ms | 14792 KB | Partially correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 1 ms | 4440 KB | Partially correct |
2 | Partially correct | 1 ms | 4444 KB | Partially correct |
3 | Correct | 1 ms | 4444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4444 KB | Output is correct |
2 | Partially correct | 1 ms | 4440 KB | Partially correct |
3 | Correct | 1 ms | 4440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4444 KB | Output is correct |
2 | Partially correct | 1 ms | 4444 KB | Partially correct |
3 | Correct | 1 ms | 4444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 55 ms | 9816 KB | Partially correct |
2 | Partially correct | 58 ms | 9936 KB | Partially correct |
3 | Correct | 55 ms | 9940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 88 ms | 10956 KB | Partially correct |
2 | Partially correct | 90 ms | 11008 KB | Partially correct |
3 | Correct | 89 ms | 10840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 229 ms | 14020 KB | Output is correct |
2 | Partially correct | 246 ms | 14280 KB | Partially correct |
3 | Correct | 231 ms | 14156 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 275 ms | 15304 KB | Output is correct |
2 | Partially correct | 299 ms | 15944 KB | Partially correct |
3 | Correct | 275 ms | 15212 KB | Output is correct |