oj.uz

Submission #715831

# Submission time Handle Problem Language Result Execution time Memory
715831 2023-03-28T07:23:19 Z chkun3109 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 254 ms 20808 KB 
#include <algorithm>
#include <array>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define MOD 1000000007
#define ll long long
#define INF 1e9 + 10
#define lINF 1e18 + 10

using namespace std;

ll n, d, m;
pair<ll, ll> arr[1000001];

bool check(ll x) {
    ll day = 1;
    ll cnt = 0;
    for (ll i = 0; i < m; i++) {
        if (arr[i].first > day) {
            day = arr[i].first;
            cnt = 0;
        }
        if (cnt == x) {
            cnt = 0;
            day++;
        }
        if (arr[i].first + d < day) {
            return false;
        }
        cnt++;
    }
    if (day > n) return false;
    return true;
}
void construct(ll x) {
    ll day = 1;
    ll cnt = 0;
    for (ll i = 0; i < m; i++) {
        cout << arr[i].second << ' ';
        cnt++;
        if (cnt == x) {
            cnt = 0;
            cout << 0 << '\n';
            day++;
        }
    }
    for (; day <= n; day++) {
        cout << 0 << '\n';
    }
}

ll first_true(ll lo, ll hi) {
    hi++;
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        if (check(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

void solve() {
    cin >> n >> d >> m;
    for (ll i = 0; i < m; i++) {
        cin >> arr[i].first;
        arr[i].second = i + 1;
    }
    sort(arr, arr + m);
    ll ans = first_true(1, INF);
    cout << ans << '\n';
    construct(ans);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--) solve();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2388 KB Output is correct
2 Correct 20 ms 2492 KB Output is correct
3 Correct 19 ms 2404 KB Output is correct
4 Correct 18 ms 2476 KB Output is correct
5 Correct 18 ms 2388 KB Output is correct
6 Correct 21 ms 2476 KB Output is correct
7 Correct 20 ms 2480 KB Output is correct
8 Correct 18 ms 2388 KB Output is correct
9 Correct 37 ms 2648 KB Output is correct
10 Correct 37 ms 2640 KB Output is correct
11 Correct 25 ms 2404 KB Output is correct
12 Correct 52 ms 4684 KB Output is correct
13 Correct 84 ms 6928 KB Output is correct
14 Correct 110 ms 9260 KB Output is correct
15 Correct 141 ms 11468 KB Output is correct
16 Correct 165 ms 13788 KB Output is correct
17 Correct 222 ms 16116 KB Output is correct
18 Correct 213 ms 18296 KB Output is correct
19 Correct 254 ms 20808 KB Output is correct
20 Correct 203 ms 16144 KB Output is correct