Submission #751843

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
751843	2023-06-01T15:34:40 Z	ndh990	Job Scheduling (CEOI12_jobs)	C++11	80 / 100	581 ms	47036 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 >> 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	43 ms	5528 KB	Output is correct
2	Correct	44 ms	5532 KB	Output is correct
3	Correct	47 ms	5516 KB	Output is correct
4	Correct	45 ms	5528 KB	Output is correct
5	Correct	43 ms	5524 KB	Output is correct
6	Correct	46 ms	5520 KB	Output is correct
7	Correct	45 ms	5540 KB	Output is correct
8	Correct	49 ms	5532 KB	Output is correct
9	Correct	89 ms	12088 KB	Output is correct
10	Correct	92 ms	12204 KB	Output is correct
11	Correct	55 ms	5308 KB	Output is correct
12	Correct	121 ms	9604 KB	Output is correct
13	Correct	185 ms	15208 KB	Output is correct
14	Correct	324 ms	20948 KB	Output is correct
15	Correct	333 ms	22684 KB	Output is correct
16	Correct	401 ms	28708 KB	Output is correct
17	Runtime error	503 ms	36696 KB	Memory limit exceeded
18	Runtime error	486 ms	41212 KB	Memory limit exceeded
19	Runtime error	581 ms	47036 KB	Memory limit exceeded
20	Runtime error	479 ms	36640 KB	Memory limit exceeded