Submission #1243625

#TimeUsernameProblemLanguageResultExecution timeMemory
1243625felipehanadaJob Scheduling (CEOI12_jobs)C++20
0 / 100
166 ms14016 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define f first #define s second int n, d, m; vector<pii> subs; bool validate(int k) { auto it = subs.begin(); int carry = 0; while (it != subs.end()) { auto ub = upper_bound(subs.begin(), subs.end(), pii(it->f, m+1)); carry += distance(it, ub) - k; carry = max(carry, 0); it = ub; } return carry == 0; // return carry <= k * (n+d-subs.rbegin()->f); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> d >> m; int x; for (int i=0; i<m; i++) { cin >> x; subs.push_back({x, i+1}); } sort(subs.begin(), subs.end()); int lower = 0; int upper = m; while (lower < upper) { int mid = lower + (upper-lower)/2; if (validate(mid)) { upper = mid; } else { lower = mid+1; } } cout << upper << '\n'; auto it = subs.begin(); for (int curr = 1; curr <= n; curr++) { for (int i=0; i<upper && it != subs.end() && it->f <= curr; i++) { cout << it->s << ' '; it++; } cout << "0\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...