Submission #1202483

#TimeUsernameProblemLanguageResultExecution timeMemory
1202483RaimondJob Scheduling (CEOI12_jobs)C++20
0 / 100
122 ms9784 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector <int>; using vvi = vector<vi>; using vll = vector<ll>; using vvll = vector<vll>; using vs = vector <string>; using vb = vector <bool>; using vd = vector <double>; using vc = vector <char>; using pii = pair<int, int>; using pll = pair<ll, ll>; using vpii = vector <pii>; int n, d, m; vpii quests; bool binarySearch(ll mid, vector<vi> &days){ int cnt = 0; int last = 1; for(int i = 0; i < m and last <= n; i++){ if(quests[i].first + d < last) return false; if(quests[i].first < last){ i--; last++; cnt = 0; continue; } if(cnt + 1 > mid) { last++; cnt = 0; if(last > n) break; } days[last - 1].push_back(quests[i].second); cnt++; } if(last > n) return false; return true; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>d>>m; quests = vpii(m); for(auto &x : quests) cin>>x.first; for(int i = 0; i < m; i++){ quests[i].second = i + 1; } sort(quests.begin(), quests.end()); int l = 1, r = m + 1; r = 4; vvi ans; while(l + 1 < r){ ll mid = (l + r) / 2; vector<vi> days(n); if(binarySearch(mid, days)){ r = mid; ans = days; } else{ l = mid; } } cout<<r<<'\n'; for(int i = 0; i < ans.size(); i++){ for(auto x : ans[i]){ cout<<x<<" "; } cout<<"0\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...