# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
532342 | Alex_tz307 | Job Scheduling (CEOI12_jobs) | C++17 | 858 ms | 23260 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int kN = 1e5;
const int kM = 1e6;
int n, d, m;
pair<int, int> a[kM];
vector<int> sol[1 + kN];
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/
bool check(int k, bool ok = false) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < k; ++i) {
pq.emplace(0);
}
for (int i = 0; i < m; ++i) {
int t = pq.top();
pq.pop();
if (t >= a[i].first + d) {
return false;
}
if (t < a[i].first) {
t = a[i].first;
}
pq.emplace(t + 1);
if (ok) {
sol[t].emplace_back(a[i].second + 1);
}
}
return true;
}
void testCase() {
cin >> n >> d >> m;
for (int i = 0; i < m; ++i) {
cin >> a[i].first;
a[i].second = i;
}
sort(a, a + m);
int l = 1, r = m, ans = m;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << '\n';
check(ans, true);
for (int i = 1; i <= n; ++i) {
sol[i].emplace_back(0);
for (int x : sol[i]) {
cout << x << ' ';
}
cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |