Submission #1011792

#TimeUsernameProblemLanguageResultExecution timeMemory
1011792LudisseyJob Scheduling (CEOI12_jobs)C++14
100 / 100
191 ms24364 KiB
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;
 
int n,d,m;
vector<pair<int,int>> s;

bool f(int x){
    int j=0;
    for (int i = 1; i <= n; i++)
    {   
        if(s[j].first>i) continue;
        int k=0;
        for (k = j; k<j+x&&k<m; k++)
        {
            if(s[k].first>i) { k++; break; } 
            if(s[k].first+d<i) return false;
        }
        j=k;  
    }
    return true;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d >> m;
    s.resize(m);
    for (int i = 0; i < m; i++) cin >> s[i].first;
    for (int i = 0; i < m; i++) s[i].second=i;

    sort(all(s));
    int l=0;
    int r=m;
    while(l<r){
        int mid=(l+r)/2;
        if(f(mid)) r=mid;
        else l=mid+1;
    }
    cout << l << "\n";
    int j=0;
    for (int i = 1; i <= n; i++)
    {   
        int k=0;
        for (k = j; k<j+l&&k<m; k++)
        {
            if(s[k].first>i) { k++; break; } 
            if(s[k].first+d<i) return false;
            cout << s[k].second+1 << " ";
        }
        cout << "0\n";
        j=k;  
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...