Submission #751845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
751845	2023-06-01T15:36:28 Z	ndh990	Job Scheduling (CEOI12_jobs)	C++11	80 / 100	509 ms	45432 KB

jobs

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> pairs;
using vi = vector<ll>;
const ll MOD = 1e9+7;
#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

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	5300 KB	Output is correct
2	Correct	34 ms	5272 KB	Output is correct
3	Correct	32 ms	5236 KB	Output is correct
4	Correct	32 ms	5276 KB	Output is correct
5	Correct	35 ms	5288 KB	Output is correct
6	Correct	34 ms	5352 KB	Output is correct
7	Correct	40 ms	5248 KB	Output is correct
8	Correct	42 ms	5268 KB	Output is correct
9	Correct	86 ms	11924 KB	Output is correct
10	Correct	83 ms	11968 KB	Output is correct
11	Correct	41 ms	4884 KB	Output is correct
12	Correct	96 ms	8956 KB	Output is correct
13	Correct	138 ms	14388 KB	Output is correct
14	Correct	213 ms	19672 KB	Output is correct
15	Correct	241 ms	21524 KB	Output is correct
16	Correct	317 ms	27232 KB	Output is correct
17	Runtime error	371 ms	34868 KB	Memory limit exceeded
18	Runtime error	399 ms	39764 KB	Memory limit exceeded
19	Runtime error	509 ms	45432 KB	Memory limit exceeded
20	Runtime error	418 ms	35024 KB	Memory limit exceeded