Submission #1299772

#TimeUsernameProblemLanguageResultExecution timeMemory
1299772hssaan_arifJob Scheduling (CEOI12_jobs)C++20
100 / 100
159 ms15736 KiB
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;

int n , A[N] , x , lis[N] , m , d;
vector<int> ind[N];

bool ch(int mid){
    queue<int> q;
    for (int i=1 ; i<=n ; i++){
        for (int j=0 ; j<lis[i] ; j++){
            q.push(i);
        }
        for (int j=0 ; j<mid ; j++){
            if (q.size()){
                if (i - q.front() > d){
                    return 0;
                }
                q.pop();
            }else{
                break;
            }
        }

    }
    if (q.size()){
        return 0;
    }
    return 1;
}

void solve(){
    cin >> n >> d >> m;
    for (int i=1 ; i<=m ; i++){
        cin >> x;
        lis[x]++;
        ind[x].pb(i);
    }
    int l=0 , r=1e9;
    while(l+1 < r){
        int mid = (l+r)>>1;
        if (ch(mid)){
            r = mid;
        }else{
            l = mid;
        }
    }
    cout << r << endl;
    queue<int> q;
    for (int i=1 ; i<=n ; i++){
        for (int j=0 ; j<lis[i] ; j++){
            q.push(i);
        }
        for (int j=0 ; j<r ; j++){
            if (q.size()){
                
                cout << ind[q.front()].back() << ' ';
                ind[q.front()].pop_back();
                q.pop();
            }else{
                break;
            }
        }
        cout << '0' << endl;
    }
    
}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    // cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...