# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
979028 | Amaarsaa | Job Scheduling (CEOI12_jobs) | C++14 | 292 ms | 16564 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;
using ll = long long ;
int n, d;
vector < pair < int, int > >v;
bool can(int mid) {
int i, s, cnt = 0, l, r;
l = 0;
for (i = 1; i <= n; i ++) {
if ( l >= v.size()) return 1;
if ( v[l].first < i) return 0;
i = max(i, v[l].first - d);
r = min(int(v.size() - 1), l + mid - 1);
if ( l > r) return 0;
l = r + 1;
}
if ( l >= v.size()) return 1;
return 0;
}
void Ans(int mid) {
int i, s, cnt = 0, l, r;
l = 0;
for (i = 1; i <= n; i ++) {
i = max(i, v[l].first - d);
r = min(int(v.size() - 1), l + mid - 1);
for (int j = l; j <= r; j ++) cout << v[j].second << " ";
cout << 0 << endl;
l = r + 1;
}
return ;
}
int main() {
// freopen("moocast.in", "r", stdin);
// freopen("moocast.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
int m, i,x, lo, hi, mid;
cin >> n >> d >> m;
for (i = 1; i <= m; i ++) {
cin >> x;
v.push_back({x + d, i});
}
sort(v.begin(), v.end());
lo = 0;
hi = m;
while (lo < hi) {
mid = (lo + hi)/2;
if (!can(mid)) lo = mid + 1;
else hi = mid;
}
cout << lo << endl;
Ans(lo );
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |