Submission #1276239

#TimeUsernameProblemLanguageResultExecution timeMemory
1276239nanaseyuzukiJob Scheduling (CEOI12_jobs)C++20
100 / 100
168 ms21076 KiB
#include <bits/stdc++.h> // Author: Kazuki_Will_Win_VOI_8703 #define fi first #define se second #define pii pair<int, int> #define int long long #define all(a) a.begin(), a.end() using namespace std; const int mn = 1e6 + 5; int n, d, m, cnt[mn]; vector <pii> Megumi; bool check(int mid){ int left = mid, Reina = 1; for(int day = 1; day <= n; day++){ if(Reina < day) Reina = day, left = mid; if(cnt[day] <= left) left -= cnt[day]; else{ int extra = cnt[day] - left; int add = (extra + mid - 1) / mid; Reina += add; left = add * mid - extra; if(Reina > day + d) return false; } } if(Reina > n) return false; return true; } void solve(){ cin >> n >> d >> m; int r = 0; for(int i = 1; i <= m; i++){ int x; cin >> x; Megumi.push_back({x, i}); cnt[x] ++; r = max(r, cnt[x]); } int l = 1, ans = -1; sort(all(Megumi)); while(l <= r){ int mid = (l + r) >> 1; if(check(mid)){ r = mid - 1; ans = mid; } else l = mid + 1; } cout << ans << '\n'; int left = ans, Reina = 1; for(auto [day, i] : Megumi){ while(Reina < day){ cout << 0 << '\n'; left = ans; Reina ++; } if(left == 0){ cout << 0 << '\n'; Reina ++, left = ans; } cout << i << ' '; left --; } while(Reina <= n){ cout << 0 << '\n'; Reina ++; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...