# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
964984 | 2024-04-18T01:26:43 Z | fzyzzz_z | Hiring (IOI09_hiring) | C++17 | 604 ms | 31784 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fs first #define sc second int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; ll k; cin >> n >> k; vector<pair<int, int>> a(n); vector<int> ord(n); for (int i = 0; i < n; ++i) { cin >> a[i].sc >> a[i].fs; ord[i] = i; } sort(ord.begin(), ord.end(), [&](int & x, int & y){ if (a[x].fs * a[y].sc == a[x].sc * a[y].fs) return a[x].sc < a[y].sc; return (a[y].fs * a[x].sc <= a[y].sc * a[x].fs); }); set<pair<int, int>> st; int ans = 0; ll cs = 0; for (int i = 0; i < n; ++i) { int x = a[ord[i]].fs, y = a[ord[i]].sc; cs += x; st.insert({x, i}); // cout << "at " << i << ' ' << ord[i] << ' ' << x << ' ' << y << '\n'; while (cs * y > k * x) { pair<int, int> v = *st.rbegin(); cs -= v.fs; st.erase(v); } // cout << cs << ' ' << '\n'; // cout << "S " << st.size() << '\n'; // for (auto x: st) { // cout << x.sc << '\n'; // } if (st.size() > ans) { ans = st.size(); } } st.clear(); cs = 0; for (int i = 0; i < n; ++i) { int x = a[ord[i]].fs, y = a[ord[i]].sc; cs += x; st.insert({x, ord[i]}); while (cs * y > k * x) { pair<int, int> v = *st.rbegin(); cs -= v.fs; st.erase(v); } if (st.size() == ans) { cout << ans << "\n"; set<int> xs; for (auto v: st) xs.insert(v.sc); for (auto v: xs) { cout << v + 1 << "\n"; } return 0; } } assert(false); return 0; }
Compilation message
# | 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 | Correct | 1 ms | 348 KB | Output is correct |
4 | Partially correct | 1 ms | 348 KB | Partially correct |
5 | Partially correct | 0 ms | 348 KB | Partially correct |
6 | Partially correct | 1 ms | 464 KB | Partially correct |
7 | Partially correct | 1 ms | 348 KB | Partially correct |
8 | Partially correct | 2 ms | 600 KB | Partially correct |
9 | Correct | 3 ms | 548 KB | Output is correct |
10 | Partially correct | 3 ms | 724 KB | Partially correct |
11 | Correct | 3 ms | 600 KB | Output is correct |
12 | Partially correct | 7 ms | 1116 KB | Partially correct |
13 | Partially correct | 4 ms | 604 KB | Partially correct |
14 | Correct | 8 ms | 1116 KB | Output is correct |
15 | Partially correct | 10 ms | 1004 KB | Partially correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Partially correct | 1 ms | 344 KB | Partially correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Partially correct | 12 ms | 1552 KB | Partially correct |
5 | Partially correct | 24 ms | 2860 KB | Partially correct |
6 | Correct | 275 ms | 17140 KB | Output is correct |
7 | Partially correct | 311 ms | 24264 KB | Partially correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 1 ms | 344 KB | Partially correct |
2 | Partially correct | 1 ms | 348 KB | Partially correct |
3 | Correct | 1 ms | 464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 500 KB | Output is correct |
2 | Partially correct | 1 ms | 348 KB | Partially correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Partially correct | 1 ms | 348 KB | Partially correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 101 ms | 6828 KB | Partially correct |
2 | Partially correct | 91 ms | 6912 KB | Partially correct |
3 | Correct | 92 ms | 6936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 128 ms | 11700 KB | Partially correct |
2 | Partially correct | 120 ms | 11860 KB | Partially correct |
3 | Correct | 120 ms | 11732 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 419 ms | 26560 KB | Output is correct |
2 | Partially correct | 411 ms | 26552 KB | Partially correct |
3 | Correct | 392 ms | 26488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 604 ms | 31784 KB | Output is correct |
2 | Partially correct | 604 ms | 31676 KB | Partially correct |
3 | Correct | 585 ms | 31592 KB | Output is correct |