제출 #858049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858049		AminMDNZ	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	403 ms	20220 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> arr;
int n, m, d;
vector<vector<int>> day;

bool f(int mm){
    int del = 0;
    day.clear();
    day.resize(n+1);
    queue<int> mac;
    for(int i=0;i<mm;i++) mac.push(1);
    for(int i=0;i<m;i++){
        int r = mac.front();
        del = max(r - arr[i].first, del);
        if(del > d) return false;
        day[max(r, arr[i].first)].push_back(arr[i].second);
        mac.pop();
        mac.push(max(r, arr[i].first)+1);
    }
    return true;
}
 
int main(){
    cin>>n>>d>>m;
    arr.resize(m);
    for(int i=0;i<m;i++){
        arr[i].second = i;
        cin>>arr[i].first;
    }
    sort(arr.begin(), arr.end());
    int mm;
    int r = m;
    int l = 1;
    int ans = m;
    while(r >= l){
        mm = l + (r - l)/2;
        if(f(mm)){
            r = mm - 1;
            ans = mm;
        }
        else{
            l = mm + 1;
        }
    }
    f(ans);
    cout<<ans<<endl;
    for(int i=1;i<n+1;i++){
        for(auto t : day[i]) cout<<t+1<<" ";
        cout<<"0\n";
    }
}

• Subtask 1: 100 / 100