Submission #1294076

#TimeUsernameProblemLanguageResultExecution timeMemory
1294076harryleeeJob Scheduling (CEOI12_jobs)C++20
100 / 100
104 ms11240 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5; int n, d, m; vector<int> v[maxn + 1]; bool check(int ma){ queue<pair<int, int>> q; for (int i = 1; i <= n; ++i){ if (!q.empty() && i - q.front().first > d) return false; if (v[i].size() > 0) q.push({i, v[i].size()}); int cur = ma; while(cur > 0 && !q.empty()){ int lost = min(q.front().second, cur); q.front().second -= lost; cur -= lost; if (q.front().second == 0) q.pop(); } } if (q.empty()) return true; return false; } void print(int ma){ queue<pair<int, int>> q; for (int i = 1; i <= n; ++i){ if (v[i].size() > 0) q.push({i, 0}); int cur = ma; while(cur > 0 && !q.empty()){ int j = q.front().second; for (; j < min((int)v[q.front().first].size(), q.front().second + cur); ++j) cout << v[q.front().first][j] << ' '; int lost = min(j - q.front().second, cur); q.front().second = j; cur -= lost; if (q.front().second == v[q.front().first].size()) q.pop(); } cout << 0 << '\n'; } return; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> d >> m; for (int i = 1; i <= m; ++i){ int x; cin >> x; v[x].push_back(i); } int lo = 1, hi = m, ans = -1; while(lo <= hi){ int mid = (lo + hi) >> 1; if (check(mid)) ans = mid, hi = mid - 1; else lo = mid + 1; } cout << ans << '\n'; print(ans); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...