Submission #1254311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254311		erfang1382	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	178 ms	29160 KiB

jobs

#include  <bits/stdc++.h>

using namespace std;

typedef  long long   ll;
typedef  long double lld;

vector<string> s;

void solve(){
   ll days,D,jobs_num;
   cin>>days>>D>>jobs_num;
   vector<vector<ll>> jpd(days);
   ll _max=-1;
   vector<ll> all_jobs;
   for(ll i=0;i<jobs_num;i++){
       ll a;
       cin>>a;
       jpd[a-1].push_back(i+1);
       _max=max(_max,(ll)jpd[a-1].size());
    } 
    for(ll i=0;i<jpd.size();i++){
     all_jobs.push_back(jpd[i].size());
    }
    vector<vector<ll>> result(days);
    
    auto check=[&](ll m,bool fill=false)->bool{
        pair<ll,ll> curr_job={0,0};
        ll index=0;
        for(ll day=0;day<days;day++){
            ll _m=m;
            while(_m && index<=day){
                if(curr_job.second==0){
                    curr_job={index,all_jobs[index]};
                    index++;
                    
                }
                ll can_do=min(_m,curr_job.second);
                if(fill)
                for(ll i=curr_job.second-1;i>=curr_job.second-can_do;i--){
                    result[day].push_back(jpd[curr_job.first][i]);
                }
                _m-=can_do;
                curr_job.second-=can_do;
                if(day-curr_job.first>D){
                    return false;
                    
                }
            }
            
            
        }
        return true;
        
        
        
    };
    ll hi=1e8;
    ll lo=0;
   
   while(lo<hi){
    ll mid=lo+(hi-lo)/2;

    if(check(mid)){
        hi=mid;
    }else{
        lo=mid+1;
    }

   }
   check(hi,true);
   cout<<hi<<endl;
   for(auto i:result){
    for(auto j:i){
        cout<<j<<' ';
    }
    cout<<0<<"\n";
   }



     

}
int main(){
    
    solve();

}

• Subtask 1: 100 / 100