Submission #1239383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239383		papaulo	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	283 ms	24128 KiB

jobs

#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++;
        }
        ans[i].push_back(0);
    }
    return j==m;
}

int main() {
    cin >> n >> d >> m;
    cin.ignore();
    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 << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 100