# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
467549 | Ilsiya | Job Scheduling (CEOI12_jobs) | C++17 | 692 ms | 31296 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>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef long double ld;
#define F first
#define S second
ll n, d, m;
pair<ll, ll> jobs[1000000];
bool cmp(pair<ll, ll> i, pair<ll, ll> j) {
if (i.F == j.F) return i.S < j.S;
else return i.F < j.F;
}
bool f(ll x) {
ll numb = 0;
for (ll i = 1; i <= n; i++) {
for (ll j = 0; j < x; j++) {
if (jobs[numb].F > i) {
break;
}
if (jobs[numb].F + d >= i) {
numb++;
}
else {
return false;
}
if (numb + 1 == m) {
return true;
}
}
}
return false;
}
int main() {
cin >> n >> d >> m;
for (ll i = 0; i < m; i++) {
cin >> jobs[i].F;
jobs[i].S = i + 1;
}
sort(jobs, jobs + m);
ll start = 0, end = m, mid = 0;
while (start + 1 < end) {
mid = (start + end) / 2;
if (f(mid)) {
end = mid;
}
else {
start = mid;
}
}
cout << end << "\n";
vll ans[n];
ll p1 = 0;
for (ll i = 1; i <= n; i++) {
for (ll j = 0; j < end; j++) {
if (jobs[p1].F > i) {
break;
}
if (jobs[p1].F + d >= i) {
ans[i - 1].push_back(jobs[p1].S);
p1++;
}
}
}
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < ans[i].size(); j++) {
cout << ans[i][j] << " ";
}
cout << "0" << "\n";
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |