#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define mp make_pair
using pi = pair<int, int>;
using vi = vector<int>;
int N, D, M;
// test if it is possible to finish the jobs using given # of machines
// return: first: possible or not, second: if possible, the schedule for the jobs
pair<bool, vector<vi>> isFeasible(const vector<pi> &jobs, int machineCount)
{
vector<vi> schedule(N);
int reqNum = 0;
// we simulate from day 1 ultil the last day N
// we move to the next day if all the machines are used or
// there is no more job requests left on or before this day
for (int day = 1; day <= N; day++)
{
for (int j = 0; j < machineCount; j++)
{
// if all jobs before and on this day are finished,
// we can go to the next day, even if there are usable machines left
// we can determine that since the vector jobs is sorted
if (jobs[reqNum].first > day)
break;
// if the current date is before the deadline for the job
// we can add this job to the schedule and move to the next job request
if (jobs[reqNum].first + D >= day)
schedule[day - 1].push_back(jobs[reqNum++].second);
// otherwise, it is not feasible due to deadline
else
return mp(false, schedule);
// if we have processed all the requests, we have found a feasible sol
if (reqNum == M)
return mp(true, schedule);
}
}
// if not all the requests can be processed within the given N days,
// then it is not feasible
return mp(false, schedule);
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cin >> N >> D >> M;
vector<pi> jobs(M);
for (int i = 0; i < M; i++)
{
int day;
cin >> day;
// first: request date, second: index [1..M]
jobs[i] = mp(day, i + 1);
}
// we sort the jobs by the request date in ascending order
// sothat we can test them using isFeasible() in linear time whether they
// can be done in given time using a certain amount of machines
sort(all(jobs));
vector<vi> result;
// binary search on the number of machines for the minimum possible solution
// left and right bound, l and r
// (M + D) / (D + 1) as integer division is equivalent to ceiling(M / (D + 1))
int l = 1, r = (M + D) / (D + 1);
while (l < r)
{
int machineNum = (l + r) / 2;
// test if the jobs would finish within the deadline
// using the current # of machines, machineNum
pair<bool, vector<vi>> curResult = isFeasible(jobs, machineNum);
// if it's possible, we set the right bound as the tested machine number
// and save the current schedule
if (curResult.first)
{
r = machineNum;
result = curResult.second;
}
// otherwise, we set the left bound to be the tested number + 1
// and test the next machineNum again
else
l = machineNum + 1;
}
cout << l << "\n";
for (int i = 0; i < N; i++)
{
for (int &idx : result[i])
cout << idx << " ";
cout << 0 << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
2384 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
28 ms |
2396 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
28 ms |
2412 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
28 ms |
2408 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
28 ms |
2424 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
29 ms |
2408 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
30 ms |
2376 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
29 ms |
2372 KB |
Execution killed with signal 11 |
| 9 |
Correct |
89 ms |
9632 KB |
Output is correct |
| 10 |
Correct |
94 ms |
9724 KB |
Output is correct |
| 11 |
Correct |
43 ms |
2816 KB |
Output is correct |
| 12 |
Correct |
93 ms |
4960 KB |
Output is correct |
| 13 |
Correct |
126 ms |
8540 KB |
Output is correct |
| 14 |
Correct |
179 ms |
10876 KB |
Output is correct |
| 15 |
Correct |
255 ms |
10920 KB |
Output is correct |
| 16 |
Correct |
298 ms |
15844 KB |
Output is correct |
| 17 |
Correct |
370 ms |
18716 KB |
Output is correct |
| 18 |
Correct |
370 ms |
23196 KB |
Output is correct |
| 19 |
Correct |
476 ms |
26416 KB |
Output is correct |
| 20 |
Correct |
370 ms |
18620 KB |
Output is correct |
