Submission #783077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783077	2023-07-14T15:04:48 Z	olisoe	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	412 ms	29848 KB

jobs

#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"
#include "set"
#include "unordered_set"
#include "stack"
#include "map"
#include "limits.h"
#include "cstdio"
#include "math.h"
#include <iomanip>
#include <numeric>
using namespace std;

int N,D,M;

pair<bool,vector<vector<int>>> works(const vector<pair<int,int>> &jobs, int machines)
{
    vector<vector<int>> schedule(N);
    int reqnum = 0;
    for(int day = 1; day<=N; day++)
    {
        for(int j = 0; j<machines; j++)
        {
            if(jobs[reqnum].first>day)break;
            if(jobs[reqnum].first+D>=day)
                schedule[day-1].push_back(jobs[reqnum++].second);
            else
                return make_pair(false,schedule);
            if(reqnum==M)
                return make_pair(true,schedule);
        }
    }
    return make_pair(false,schedule);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N>>D>>M;
    vector<pair<int,int>> jobs(M);
    for(int i = 0; i<M; i++)
    {
        int day;
        cin>>day;
        jobs[i]=make_pair(day,i+1);
    }
    sort(jobs.begin(),jobs.end());
    vector<vector<int>> result;
    int l = 1; int r= M;
    while(l<r)
    {
        int mid = (l+r)/2;
        pair<bool,vector<vector<int>>> res = works(jobs,mid);
        if(res.first == true)
        {
            r = mid;
            result = res.second;
        }
        else
            l = mid+1;
    }
    cout<<l<<endl;
    for(int i = 0; i<N; i++)
    {
        for(auto x: result[i])
        {
            cout<<x<<" ";
        }
        cout<<0<<endl;
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	3368 KB	Output is correct
2	Correct	32 ms	3376 KB	Output is correct
3	Correct	33 ms	3320 KB	Output is correct
4	Correct	31 ms	3288 KB	Output is correct
5	Correct	32 ms	3332 KB	Output is correct
6	Correct	38 ms	3332 KB	Output is correct
7	Correct	32 ms	3332 KB	Output is correct
8	Correct	37 ms	3340 KB	Output is correct
9	Correct	156 ms	10024 KB	Output is correct
10	Correct	196 ms	9984 KB	Output is correct
11	Correct	30 ms	3144 KB	Output is correct
12	Correct	59 ms	5704 KB	Output is correct
13	Correct	97 ms	9712 KB	Output is correct
14	Correct	145 ms	12720 KB	Output is correct
15	Correct	155 ms	12896 KB	Output is correct
16	Correct	224 ms	18972 KB	Output is correct
17	Correct	244 ms	22180 KB	Output is correct
18	Correct	266 ms	26332 KB	Output is correct
19	Correct	412 ms	29848 KB	Output is correct
20	Correct	243 ms	22076 KB	Output is correct