제출 #1239385

#제출 시각아이디문제언어결과실행 시간메모리
1239385papauloJob Scheduling (CEOI12_jobs)C++20
100 / 100
183 ms20868 KiB
#include <bits/stdc++.h>
using namespace std;

struct Job {
    int day, id;
    Job(int d, int i) : day(d), id(i) {}
    Job() : Job(0, 0) {}
    bool operator<(const Job &j) const {
        if(day!=j.day) return day<j.day;
        return id>j.id;
    }
};

#define MAXM 1001000
#define MAXN 100100
Job jobs[MAXM];
vector<int> ans[MAXN];

int n, d, m;

bool can(int qnt) {
    for(int i=1;i<=n;i++) ans[i].clear();
    int j=0;
    for(int i=1;i<=n;i++) {
        while(ans[i].size()<qnt&&j<m&&i>=jobs[j].day) {
            if(jobs[j].day+d<i) return false;
            ans[i].push_back(jobs[j].id);
            j++;
        }
    }
    return j==m;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> d >> m;
    for(int i=0;i<m;i++) cin >> jobs[i].day;
    for(int i=0;i<m;i++) jobs[i].id=i+1;
    sort(jobs, jobs+m);
    int l=1, r=m;
    while(l<r) {
        int mid=(l+r)/2;
        if(can(mid)) r=mid;
        else l=mid+1;
    }
    can(l);
    cout << l << "\n";
    for(int i=1;i<=n;i++) {
        for(auto v : ans[i]) cout << v << " ";
        cout << "0\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...