Submission #1304139

#TimeUsernameProblemLanguageResultExecution timeMemory
1304139rayxuJob Scheduling (CEOI12_jobs)C++20
40 / 100
186 ms20932 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("schedule.in","r",stdin);
    int n,d,m; cin>>n>>d>>m;
    vector<pair<int,int>> jobs(m);
    for (int i=0;i<m;i++) {
        cin>>jobs[i].first;
        jobs[i].second = i+1;
    }
    sort(jobs.begin(),jobs.end());
    int lo=1,hi=m;
    auto test=[&](int x) {
        int pt=0,day=0;
        while (pt<m) {
            day++;
            if ((jobs[pt].first-d)>day) return false;
            int had=0;
            while (pt<m && had<x) {
                if (jobs[pt].first>day) break;
                pt++;
                had++;
            }
        }
        return (day<=n);
    } ;
    while (lo<hi) {
        int mid=lo+(hi-lo)/2;
        if (test(mid)) hi = mid;
        else lo = mid+1;
    }
    cout<<lo<<"\n";
    int pt=0,day=0;
    while (pt<m) {
        day++;
        int had=0;
        while (pt<m && had<lo) {
            if (jobs[pt].first>day) break;
            cout<<jobs[pt].second<<" ";
            pt++;
            had++;
        }
        cout<<0<<"\n";
    }
    for (int i=day;i<n;i++) cout<<0<<"\n";
    return 0;
}
// if you get WA, go and read the question carefully again
// Then read the code for mixed variables, mistype, not considering a condition, etc.
#Verdict Execution timeMemoryGrader output
Fetching results...