Submission #1196340

#TimeUsernameProblemLanguageResultExecution timeMemory
1196340dostsJob Scheduling (CEOI12_jobs)C++20
100 / 100
480 ms21060 KiB
#include <bits/stdc++.h> #pragma GCC target("lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define all(x) x.begin(),x.end() #define sp << " " << using namespace std; const int inf = 2e18; const int N = 2e5+1; int n,d,m; inline int check(const vector<pii>& v,int mach,int construct) { if (construct) cout << mach << '\n'; int ptr = 0; for (int i = 1;i<=n;i++) { for (int j = 0;j<mach && ptr < m;j++) { if (v[ptr].ff+d < i) return 0; if (v[ptr].ff > i) continue; if (construct) cout << v[ptr].ss << ' '; ptr++; } if (construct) cout << "0\n"; } if (ptr<m) return 0; return 1; } void solve() { cin >> n >> d >> m; vector<pii> v; for (int i=1;i<=m;i++){ int x; cin >> x; v.push_back({x,i}); } sort(all(v)); int l = 0; int r = (m+d-1)/d; while (l<=r) { int m = (l+r) >> 1; if (check(v,m,0)) r = m-1; else l = m+1; } check(v,l,1); } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...