제출 #598750

#제출 시각아이디문제언어결과실행 시간메모리
598750gcconureJob Scheduling (CEOI12_jobs)C++17
100 / 100
240 ms20940 KiB
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
ll n,d,m; 
vector<pair<ll,ll>> v;
 
bool ok(ll dd){
  	ll c = 0; ll day = 1;
   	for(int i = 0; i < m; i++){
    	if(day>n){
          return false;
        }
      	if(day>v[i].first+d){
          return false;
        }
      	if(day<v[i].first){
      	    c=0;
            day=v[i].first;
        }
      	c++;
      	if(c==dd){
          day++;
          c=0;
        }
    }
    return true;
}
 
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
 
    cin >> n >> d >> m;
    
    
    for(ll i = 0; i < m; i++){
        ll x; cin >> x;
        v.push_back({x,i});
    }
    
    sort(v.begin(), v.end());
    
    ll l = 1,r=m;
    
    while(l<r){
        ll mid = (l+r)/2;
        if(ok(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    ll counter=0;
    ll cur = 0;
    cout << l << "\n";
    while(cur<m){
        counter++;
        for(ll i = 0; i < l; i++){
            cout << v[cur].second+1 << " ";
            cur++;
            if(cur==m){
                break;
            }
        }
        cout << "0\n";
    }
   
    for(ll i = 0; i < n-counter; i++){
        cout << 0 << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...