제출 #679817

#제출 시각아이디문제언어결과실행 시간메모리
679817peijarJob Scheduling (CEOI12_jobs)C++17
0 / 100
501 ms36288 KiB
#include <bits/stdc++.h> #define int long long using namespace std; namespace std { template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) { out << "["; for (int i = 0; i < (int)vec.size(); ++i) { out << vec[i]; if (i + 1 < (int)vec.size()) out << ", "; } return out << "]"; } } // namespace std void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int nbJours, nbTravaux, deadline; cin >> nbJours >> deadline >> nbTravaux; vector<int> debut(nbTravaux); for (int &x : debut) { cin >> x; --x; } vector<int> order(nbTravaux); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) { return debut[i] < debut[j]; }); auto check = [&](int nbMachines) -> bool { queue<int> dispo; for (int i = 0; i < nbJours; ++i) dispo.push(i); vector<int> surTemps(nbJours); for (int i : order) { int t = debut[i]; while (!dispo.empty() and dispo.front() < t) dispo.pop(); if (dispo.empty() or dispo.front() > t + deadline) return false; int tt = dispo.front(); if (tt > t + deadline) return false; surTemps[tt]++; if (surTemps[tt] == nbMachines) dispo.pop(); } return true; }; int lo = 1, up = nbTravaux; while (lo < up) { int mid = (lo + up) / 2; if (check(mid)) up = mid; else lo = mid + 1; } cout << lo << endl; vector<vector<int>> onDay(nbJours); queue<int> dispo; for (int i = 0; i < nbJours; ++i) dispo.push(i); vector<int> surTemps(nbJours); for (int i : order) { int t = debut[i]; while (!dispo.empty() and dispo.front() < t) dispo.pop(); if (dispo.empty() or dispo.front() > t + deadline) assert(false); int tt = dispo.front(); if (tt > t + deadline) assert(false); surTemps[tt]++; onDay[tt].push_back(i + 1); if (surTemps[tt] == lo) dispo.pop(); } for (int i = 0; i < nbJours; ++i) { cout << onDay[i].size() << ' '; for (int x : onDay[i]) cout << x << ' '; cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...