# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
532335 | Alex_tz307 | Job Scheduling (CEOI12_jobs) | C++17 | 172 ms | 17588 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, dq[kM];
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) {
int l = 0, r = -1;
for (int i = 0; i < k; ++i) {
dq[++r] = 0;
}
for (int i = 0; i < m; ++i) {
int t = dq[l++];
if (t > a[i].first + d) {
return false;
}
dq[++r] = max(a[i].first + 1, t + 1);
if (ok) {
sol[dq[r] - 1].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;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << l << '\n';
check(l, 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... |