Submission #751846

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
751846	2023-06-01T15:38:41 Z	ndh990	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	422 ms	26436 KB

jobs

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<int, int> pairs;
using vi = vector<ll>;
#define mp make_pair
 ll n,d,m;
pair<bool, vector<vi>> isFeasible(const vector<pairs> &jobs, int machineCount) {
        vector<vi> schedule(n);
        ll reqNum = 0;
for (ll day = 1; day <= n; day++) {
    for (ll j = 0; j < machineCount; j++) {
            if(jobs[reqNum].first>day)
        {
            break;
        }
        if(jobs[reqNum].first+d>=day)
        {
            schedule[day-1].push_back(jobs[reqNum++].second);
        }
        else return mp(false, schedule);
        if (reqNum == m) return mp(true, schedule);
    }
}
return mp(false, schedule);
}
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> d >> m;
    vector <pairs> jobs(m);
    for(int i=0;i<m;i++)
    {
        cin >> jobs[i].first;
        jobs[i].second=i+1;
    }
    sort(jobs.begin(),jobs.end());
    int l =1;
    int r =m;
    vector<vi> result;
    while (l < r) {
		int machineNum = l+(r - l) / 2;
		pair<bool, vector<vi>> curResult = isFeasible(jobs, machineNum);
		if (curResult.first) {
			r = machineNum;
			result = curResult.second;
		}
		else
			l = machineNum + 1;
    }
    cout << l << "\n";
	for (int i = 0; i < n; i++) {
		for (auto &idx : result[i]) cout << idx << " ";
		cout << 0 << "\n";
	}







}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	3084 KB	Output is correct
2	Correct	33 ms	2984 KB	Output is correct
3	Correct	30 ms	2972 KB	Output is correct
4	Correct	32 ms	2972 KB	Output is correct
5	Correct	34 ms	3064 KB	Output is correct
6	Correct	32 ms	3064 KB	Output is correct
7	Correct	30 ms	2980 KB	Output is correct
8	Correct	32 ms	2968 KB	Output is correct
9	Correct	85 ms	9640 KB	Output is correct
10	Correct	90 ms	9688 KB	Output is correct
11	Correct	38 ms	2748 KB	Output is correct
12	Correct	78 ms	5080 KB	Output is correct
13	Correct	133 ms	8672 KB	Output is correct
14	Correct	185 ms	10788 KB	Output is correct
15	Correct	209 ms	10972 KB	Output is correct
16	Correct	277 ms	16056 KB	Output is correct
17	Correct	309 ms	18808 KB	Output is correct
18	Correct	355 ms	23244 KB	Output is correct
19	Correct	422 ms	26436 KB	Output is correct
20	Correct	323 ms	18744 KB	Output is correct