제출 #856997

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

jobs

#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> arr;
int n, m , d;
map<int, set<int>> day;
map<int, int> mac;
bool f(int mm){
    mac.clear();
    day.clear();
    set<int> s;
    for(int i=1;i<n+1;i++) day[i] = s;
    int del = 0;
    mac[1] += mm;
    for(int i=0;i<m;i++){
        auto it = mac.lower_bound(-1);
        int r = (*it).first;
        del = max(r - arr[i].first, d);
        day[r].insert(arr[i].second);
        mac[r + 1]++;
        if(mac[r] > 1) mac[r]--;
        else mac.erase(r);
    }
    return del <= d;
}

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 = -1;
    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(auto i : day){
        for(auto t : i.second) cout<<t+1<<" ";
        cout<<"0 \n";
    }
}

• Subtask 1: 0 / 100