Submission #1299571

#TimeUsernameProblemLanguageResultExecution timeMemory
1299571mlecioJob Scheduling (CEOI12_jobs)C++20
10 / 100
306 ms14628 KiB
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,d;
    cin>>n>>d>>m;
    vector<int>cnt(n+1),cnt2(n+1);
    vector<pair<int,int>>xd(m);
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        cnt[x]++;
        cnt2[x]++;
        xd[i]={x,i+1};
    }
    sort(xd.begin(),xd.end());
    int lewo=1,prawo=m+1;
    while(lewo<=prawo){
        int mid=lewo+((prawo-lewo)/2);
        int akt=1;
        bool flaga=true;
        int przew=mid;
        for(int i=0;i<=n;i++){
            if(cnt2[i]==0)
            continue;
            if(cnt2[i]>przew){
                if(przew!=0){
                    akt++;
                    cnt2[i]-=przew;
                }
                przew=mid;
                while(cnt2[i]>przew){
                    cnt2[i]-=przew;
                    akt++;
                    przew=mid;
                }
                if(akt>i+d)
                flaga=false;
                przew-=cnt2[i];
                cnt2[i]=0;
            }
            else {
                przew-=cnt2[i];
                cnt2[i]=0;
                if(akt>i+d)
                flaga=false;
            }
        }
        cnt2=cnt;
        if(flaga)
        prawo=mid-1;
        else
        lewo=mid+1;
    }
    cout<<lewo<<'\n';
    int ile=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<lewo;j++){
            if(ile<m)
            cout<<xd[ile].second<<' ';
            ile++;
        }
        cout<<0<<'\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...