| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1138415 | mrsmartypants | Job Scheduling (CEOI12_jobs) | C++17 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Request {
int id, day;
Request(int id, int day) : id(id), day(day) {}
};
struct Return {
bool worked;
vector<vector<int>> schedule;
Return(bool worked, vector<vector<int>> schedule) : worked(worked), schedule(schedule) {}
};
vector<vector<int>> schedule;
int N, D, M;
Return test(int numMachines, vector<Request>& jobs) {
vector<vector<int>> schedule(N);
int reqNum = 0;
for (int day = 1; day <= N; ++day) {
for (int j = 0; j < numMachines; ++j) {
if (reqNum >= M || jobs[reqNum].day > day) break;
if (jobs[reqNum].day + D >= day) {
schedule[day - 1].push_back(jobs[reqNum].id);
++reqNum;
} else {
return Return(false, schedule);
}
if (reqNum == M) return Return(true, schedule);
}
}
return Return(false, schedule);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> D >> M;
vector<Request> jobs(M);
for (int i = 0; i < M; ++i) {
cin >> jobs[i].day;
jobs[i].id = i + 1;
}
sort(jobs.begin(), jobs.end(), [](const Request& a, const Request& b) {
return a.day < b.day;
});
int lo = 1, hi = M + 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
Return r = test(mid, jobs);
if (r.worked) {
hi = mid;
schedule = r.schedule;
} else {
lo = mid + 1;
}
}
cout << lo << "\n";
for (int i = 0; i < N; ++i) {
for (int idx : schedule[i]) {
cout << idx << " ";
}
cout << "0\n";
}
return 0;
}