제출 #1011792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011792		Ludissey	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	191 ms	24364 KiB

jobs

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;
 
int n,d,m;
vector<pair<int,int>> s;

bool f(int x){
    int j=0;
    for (int i = 1; i <= n; i++)
    {   
        if(s[j].first>i) continue;
        int k=0;
        for (k = j; k<j+x&&k<m; k++)
        {
            if(s[k].first>i) { k++; break; } 
            if(s[k].first+d<i) return false;
        }
        j=k;  
    }
    return true;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d >> m;
    s.resize(m);
    for (int i = 0; i < m; i++) cin >> s[i].first;
    for (int i = 0; i < m; i++) s[i].second=i;

    sort(all(s));
    int l=0;
    int r=m;
    while(l<r){
        int mid=(l+r)/2;
        if(f(mid)) r=mid;
        else l=mid+1;
    }
    cout << l << "\n";
    int j=0;
    for (int i = 1; i <= n; i++)
    {   
        int k=0;
        for (k = j; k<j+l&&k<m; k++)
        {
            if(s[k].first>i) { k++; break; } 
            if(s[k].first+d<i) return false;
            cout << s[k].second+1 << " ";
        }
        cout << "0\n";
        j=k;  
    }
    return 0;
}

• Subtask 1: 100 / 100