# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
635625 | nayhz | Job Scheduling (CEOI12_jobs) | C++17 | 561 ms | 38764 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// CEOI 2012 Dau 1 Job Scheduling
#include <bits/stdc++.h>
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pair<int, int>>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;
/*
>>>>>>>>>>>>>>>>>>>>>>>>>>END OF TEMPLATE HEADER<<<<<<<<<<<<<<<<<<<<<<<<
*/
void solve () {
int n, d, m; cin >> n >> d >> m;
vpii a(m);
for (int i = 0; i < m; i++) {cin >> a[i].fi; a[i].se = i + 1;}
sort(all(a));
vector<vi> ans(n);
int l = 1, r = m, mid, day, i, cnt;
vector<vi> ret(n);
function<pair<bool, vector<vi>> ()> check = [&] () {
for (auto &x : ret) x.clear();
cnt = 0;
for (day = 1; day <= n; day++) {
for (i = 0; i < mid; i++) {
if (a[cnt].fi > day) break;
if (a[cnt].fi + d >= day){
ret[day - 1].pb(a[cnt++].se);
}
else return mp(false, ret);
if (cnt == m) {
return mp(true, ret);
}
}
}
return mp(false, ret);
};
pair<bool, vector<vi>> temp;
while (l < r) {
mid = l + ((r - l) >> 1);
temp = check();
if (temp.fi) {
r = mid, ans = temp.se;
} else l = mid + 1;
}
cout << l << '\n';
for (i = 0; i < n; i++) {
for (int j = 0; j < (int)ans[i].size(); j++) cout << ans[i][j] << ' ';
cout << "0\n";
}
}
signed main () {
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |