제출 #1254308

#제출 시각아이디문제언어결과실행 시간메모리
1254308erfang1382Job Scheduling (CEOI12_jobs)C++20
0 / 100
178 ms24504 KiB
#include  <bits/stdc++.h>
#include <cstdint>

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<int>> jpd(days);
   ll _max=-1;
   vector<int> all_jobs;
   for(int 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(int 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<int,int> curr_job={0,0};
        int index=0;
        for(int day=0;day<days;day++){
            int _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(int 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=_max+1;
    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();

}
#Verdict Execution timeMemoryGrader output
Fetching results...