Submission #903892

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
903892	2024-01-11T13:30:59 Z	absolutePi	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	563 ms	29264 KB

jobs

#include <bits/stdc++.h>

using namespace std;

int n,d,m;

pair<bool,vector<vector<int>>> works(vector<pair<int,int>> &jobs,int machines){
    int temp=0;
    vector<vector<int>> schedule(n);
    for(int day=1;day<=n;day++){
        for(int mac=0;mac<machines;mac++){
            if(jobs[temp].first>day){
                break;
            }
            if(jobs[temp].first+d>=day){
                schedule[day-1].push_back(jobs[temp++].second);
            }
            else{
                return {false,schedule};
            }
            if(temp==m){return {true,schedule};}
        }
    }
    return {false,schedule};
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cin >> n >> d >> m;
    vector<pair<int,int>> jobs(m);
    for(int i=0;i<m;i++){
        int day;
        cin >> day;
        //date,index
        jobs[i] = {day,i+1};
    }
    sort(jobs.begin(),jobs.end());
    vector<vector<int>> ans;
    int l=0,r=m,mid;
    while(l<r){
        mid = l+(r-l)/2;
        pair<bool,vector<vector<int>>> res = works(jobs,mid);
        if(res.first){
            r=mid;
            ans = res.second;
        }
        else{
            l=mid+1;
        }
    }
    cout << l << endl;
    for(int i=0;i<n;i++){
        for(auto j : ans[i]){
            cout << j << ' ';
        }
        cout << 0 << endl;
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	3340 KB	Output is correct
2	Correct	46 ms	3376 KB	Output is correct
3	Correct	44 ms	3480 KB	Output is correct
4	Correct	50 ms	3472 KB	Output is correct
5	Correct	48 ms	3480 KB	Output is correct
6	Correct	64 ms	3468 KB	Output is correct
7	Correct	43 ms	3392 KB	Output is correct
8	Correct	43 ms	3364 KB	Output is correct
9	Correct	186 ms	10072 KB	Output is correct
10	Correct	206 ms	10260 KB	Output is correct
11	Correct	40 ms	3204 KB	Output is correct
12	Correct	89 ms	5624 KB	Output is correct
13	Correct	125 ms	9788 KB	Output is correct
14	Correct	211 ms	12752 KB	Output is correct
15	Correct	208 ms	12644 KB	Output is correct
16	Correct	304 ms	18500 KB	Output is correct
17	Correct	369 ms	21932 KB	Output is correct
18	Correct	378 ms	21172 KB	Output is correct
19	Correct	563 ms	29264 KB	Output is correct
20	Correct	361 ms	21660 KB	Output is correct