Submission #857013

#TimeUsernameProblemLanguageResultExecution timeMemory
857013AminMDNZJob Scheduling (CEOI12_jobs)C++14
0 / 100
367 ms20292 KiB
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> arr;
int n, m , d;
vector<vector<int>> day;
bool f(int mm){
    int del = 0;
    day.clear();
    day.resize(n+1);
    queue<int> mac;
    for(int i=0;i<mm;i++) mac.push(1);
    for(int i=0;i<m;i++){
        int r = mac.front();
        del = max(r - arr[i].first, del);
        if(del > d) return false;
        day[r].push_back(arr[i].second);
        mac.pop();
        mac.push(r+1);
    }
    return true;
}
 
int main(){
    cin>>n>>d>>m;
    arr.resize(m);
    for(int i=0;i<m;i++){
        arr[i].second = i;
        cin>>arr[i].first;
    }
    sort(arr.begin(), arr.end());
    int mm;
    int r = m;
    int l = 1;
    int ans = -1;
    while(r >= l){
        mm = l + (r - l)/2;
        if(f(mm)){
            r = mm - 1;
            ans = mm;
        }
        else{
            l = mm + 1;
        }
    }
    f(ans);
    cout<<ans<<endl;
    for(int i=1;i<n+1;i++){
        for(auto t : day[i]) cout<<t+1<<" ";
        cout<<"0 \n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...