Submission #899718

#TimeUsernameProblemLanguageResultExecution timeMemory
899718KarootJob Scheduling (CEOI12_jobs)C++17
100 / 100
333 ms22868 KiB
#include <iostream> #include <cmath> #include <unordered_map> #include <map> #include <set> #include <queue> #include <vector> #include <string> #include <iomanip> #include <algorithm> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; typedef long long ll; ll linf = 1e15+1; inline void scoobydoobydoo(){ ios::sync_with_stdio(false); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int MAXN = 1e5+1; vector<int> v[MAXN]; vector<int> schedule[MAXN]; int n, d, m; bool isPossible(int machines){ queue<pair<int, int> > q; for (int i = 0; i < n; i++){ schedule[i].clear(); for (int x : v[i])q.push({x, i+d}); for (int j = 0; j < machines && !q.empty(); j++){ int node = q.front().first; int t = q.front().second; q.pop(); schedule[i].push_back(node); if (t < i)return false; } } return true; } int main(){ scoobydoobydoo(); cin >> n >> d >> m; for (int i = 0; i < m; i++){ int a; cin >> a; v[--a].push_back(i+1); } int a = 1, b = 1000001; int ret = -1; while (a < b){ int k = (a+b)>>1; if (isPossible(k)){ b = k; ret = k; } else { a = k+1; } } isPossible(ret); cout << ret << endl; for (int i = 0; i < n; i++){ for (int x : schedule[i])cout << x << " "; cout << 0 << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...