# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
831226 | 2023-08-20T00:33:31 Z | TimAni | Job Scheduling (CEOI12_jobs) | C++17 | 190 ms | 13756 KB |
#include <algorithm> #include <cassert> #include <cstdio> #include <iostream> #include <string> #include <vector> #include <set> #include <map> #include <numeric> #include <stack> #include <queue> #include <cmath> //#ifndef ONLINE_JUDGE //#include "/home/linux/Learning/headers/debug.h" //#else //#define debug(...) //#endif using namespace std; using ll = long long; void setIO(string File_name) { cin.tie(0)->sync_with_stdio(0); if (File_name.size()) { freopen((File_name + ".in").c_str(), "r", stdin); freopen((File_name + ".out").c_str(), "w", stdout); } } void sol() { int n, d, m; cin >> n >> d >> m; vector<pair<int, int>> v(m); for (int i = 0; i < m; i++) cin >> v[i].first, v[i].second = i + 1; sort(v.begin(), v.end()); auto good = [&](int mid) { for (int i = 0, day = 0, free = mid; i < m; day++, free = mid) { while (i < m && v[i].first <= day && free > 0) { if (day - v[i].first > d) return false; i++; free--; } } return true; }; int l = 0, r = m + 1; while (r > l) { int mid = l + (r - l) / 2; if (good(mid)) r = mid; else l = mid + 1; } cout << r << '\n'; int day = v[0].first; int free = r; for (int i = 0, j = 1; j <= n; j++) { while (i < m && v[i].first <= day && free > 0) { cout << v[i].second << ' '; i++; free--; } cout << "0\n"; day++; free = r; } } int main() { setIO(""); int T = 1; //cin >> T; while (T--) sol(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 1620 KB | Output is correct |
2 | Correct | 14 ms | 1732 KB | Output is correct |
3 | Correct | 14 ms | 1684 KB | Output is correct |
4 | Correct | 14 ms | 1632 KB | Output is correct |
5 | Correct | 14 ms | 1620 KB | Output is correct |
6 | Correct | 14 ms | 1632 KB | Output is correct |
7 | Correct | 15 ms | 1628 KB | Output is correct |
8 | Correct | 14 ms | 1680 KB | Output is correct |
9 | Correct | 27 ms | 1868 KB | Output is correct |
10 | Correct | 21 ms | 1876 KB | Output is correct |
11 | Correct | 24 ms | 1632 KB | Output is correct |
12 | Correct | 41 ms | 3176 KB | Output is correct |
13 | Correct | 62 ms | 4576 KB | Output is correct |
14 | Correct | 89 ms | 6144 KB | Output is correct |
15 | Correct | 107 ms | 7628 KB | Output is correct |
16 | Correct | 131 ms | 9116 KB | Output is correct |
17 | Correct | 155 ms | 10576 KB | Output is correct |
18 | Correct | 180 ms | 12084 KB | Output is correct |
19 | Correct | 190 ms | 13756 KB | Output is correct |
20 | Correct | 160 ms | 10596 KB | Output is correct |