# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
925963 | 2024-02-12T12:02:49 Z | boris_mihov | Hiring (IOI09_hiring) | C++17 | 343 ms | 24628 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.insert(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; }
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 | 4440 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 | 2 ms | 4444 KB | Partially correct |
8 | Partially correct | 2 ms | 4444 KB | Partially correct |
9 | Correct | 4 ms | 4700 KB | Output is correct |
10 | Partially correct | 3 ms | 4696 KB | Partially correct |
11 | Correct | 3 ms | 4444 KB | Output is correct |
12 | Partially correct | 5 ms | 4700 KB | Partially correct |
13 | Partially correct | 3 ms | 4444 KB | Partially correct |
14 | Correct | 7 ms | 4956 KB | Output is correct |
15 | Partially correct | 7 ms | 4700 KB | Partially 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 |
4 | Partially correct | 9 ms | 4952 KB | Partially correct |
5 | Partially correct | 22 ms | 9440 KB | Partially correct |
6 | Correct | 181 ms | 15748 KB | Output is correct |
7 | Partially correct | 239 ms | 20036 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 | 4444 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 | 65 ms | 11476 KB | Partially correct |
2 | Partially correct | 66 ms | 11472 KB | Partially correct |
3 | Correct | 68 ms | 11464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 101 ms | 13684 KB | Partially correct |
2 | Partially correct | 100 ms | 13508 KB | Partially correct |
3 | Correct | 100 ms | 13552 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 279 ms | 21252 KB | Output is correct |
2 | Partially correct | 327 ms | 20776 KB | Partially correct |
3 | Correct | 277 ms | 22204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 332 ms | 24628 KB | Output is correct |
2 | Partially correct | 343 ms | 24568 KB | Partially correct |
3 | Correct | 340 ms | 24000 KB | Output is correct |