Submission #498121

#TimeUsernameProblemLanguageResultExecution timeMemory
498121LouayFarahJob Scheduling (CEOI12_jobs)C++14
75 / 100
430 ms61568 KiB
#include "bits/stdc++.h" using namespace std; #define endl "\n" #define ll long long int #define pb push_back #define mp make_pair #define fi first #define se second const long long MOD = 1e9+7; const long long INF = 1e18; int nx[4] = {0, 0, -1, 1}; int ny[4] = {1, -1, 0, 0}; vector<ll> RES; bool f(queue<pair<ll, ll>> q, ll d, ll mid, ll n) { vector<ll> temp(0); ll currd = 1; ll c = mid; while(!q.empty()) { if(c==0) { currd++; c = mid; } ll task = q.front().fi; ll id = q.front().se; if(currd<task) { currd = task; c = mid; } if(currd>task+d) { return false; } q.pop(); c--; temp.pb(id); } RES = temp; return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n, d, m; cin >> n >> d >> m; RES.assign(n, {}); vector<pair<ll, ll>> arr; for(int i = 0; i<m; i++) { ll x; cin >> x; arr.pb(mp(x, i+1)); } sort(arr.begin(), arr.end()); //vector<ll> occ(n+1, 0); queue<pair<ll, ll>> q; for(int i = 0; i<m; i++) { //occ[arr[i].fi]++; q.push(arr[i]); } /*ll lim = 0; for(int i = 0; i<=n; i++) { lim = max(lim, occ[i]); }*/ ll l = 0; //l is bad ll r = m+1; //r is good while(l+1<r) { ll mid = (l+r)/2; if(f(q, d, mid, n)) { r = mid; } else { l = mid; } } cout << r << endl; ll curr = 0; for(int i = 0; i<n; i++) { ll li = 0; while(curr<m) { if(li==r) break; cout << RES[curr] << ' '; li++; curr++; } cout << 0 << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...