Submission #1280396

#TimeUsernameProblemLanguageResultExecution timeMemory
1280396NipphitchJob Scheduling (CEOI12_jobs)C++20
0 / 100
222 ms26840 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first 
#define s second
const int N=1e6+5;

int n,d,m;
pii a[N];
vector <vector <int>> ans;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d >> m;
    for(int i=1;i<=m;i++){
        cin >> a[i].f;
        a[i].s=i;
    }
    sort(a+1,a+1+m);
    int l=1,r=N;
    while(l<r){
        int mid=(l+r)/2;
        vector <vector <int>> v;
        vector <int> now;
        bool ok=true;
        for(int i=1;i<=m;i++){
            if(v.size()+1>=a[i].f+d){
                ok=false;
                break;
            }
            while(v.size()+1<a[i].f){
                v.push_back(now);
                now.clear();
            }
            now.push_back(a[i].s);
            if(now.size()==mid){
                v.push_back(now);
                now.clear();
            }
        }
        if(ok){
            r=mid;
            ans=v;
        }
        else l=mid+1;
    }
    cout << l << "\n";
    for(int i=0;i<ans.size();i++) ans[i].push_back(0);
    while(ans.size()<n){
        vector <int> tmp;
        tmp.push_back(0);
        ans.push_back(tmp);
    }
    for(auto v:ans){
        for(int x:v) cout << x << " ";
        cout << "\n";
    }
}

/*
8 2 12 
1 2 4 2 1 3 5 6 2 3 6 4
*/
#Verdict Execution timeMemoryGrader output
Fetching results...