| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 419347 | freshmintt | Job Scheduling (CEOI12_jobs) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define MAXN 1000005 //change. SET A SPACIOUS MAXN WHEN TESTING SO YOU DONT MESS UP WITH GARBAGE VALS OR SHIT
using namespace std;
typedef pair<long long,long long> pi;
typedef int ll;
typedef long double ld;
ll N, D, M;
#define FIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
vector<ll> jobs;
vector<pi> jobs_save;
ll days[MAXN];
vector<ll> plan[MAXN];
bool make_plan(ll machs) {
fill(days, days+MAXN, 0);
for (int i=0; i < M; i++) {
ll machID = i % machs;
days[machID] = max(days[machID]+1, jobs_save[i].first); // ++ vs +1, obstructs with comparison.
plan[days[machID]-1].push_back(jobs_save[i].second+1);
}
return true;
}
bool works(ll machs) {
fill(days, days+MAXN, 0);
for (int i=0; i < M; i++) {
ll machID = i % machs;
// cout << machID << " ";
days[machID] = max(days[machID]+1, jobs[i]); // ++ vs +1, obstructs with comparison.
if ((days[machID] - jobs[i]) > D){
return false;
}
}
return true;
}
int main() {
FIO;
cin >> N >> D >> M;
for (int i = 0; i < M; i ++) {
ll a; cin >> a; jobs.push_back(a); jobs_save.push_back({a,i});
}
sort(jobs.begin(), jobs.end());
sort(jobs_save.begin(), jobs_save.end());
ll a = 1; ll b = 1E6; ll mid;
while (a != b) {
mid = (a+b)/2;
// cout << a << " and " << mid << " and " << b<< endl;
if (works(mid)) {
b = mid;
}
else {
a = mid + 1;
}
}
cout << a << endl;
make_plan(a);
for (ll i = 0; i < N; i++) {
for (auto i : plan[i]) {
cout << i << " ";
}
cout << "0" << endl;
}
}