Submission #565350

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
565350	2022-05-20T18:06:26 Z	trytovoi	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	277 ms	20812 KB

jobs

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

template<typename T> bool ckmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool ckmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}

const char el = '\n';

void solve() {
    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    int l = 0, r = m;
    sort(all(a));
    int ans = (int) 1e18;
    while (l <= r) {
        int mid = (l + r) >> 1LL;
        
        bool ok = true;
        for (int i = 1, j = 0; i <= n && j < m; ++i) {
            int cnt = 0;
            while (j < m && cnt < mid && a[j].first <= i && a[j].first + d >= i) {
                ++cnt;
                ++j;
            } 
            if (j < m && a[j].first + d < i) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ckmin(ans, mid);
            r = mid - 1;
        } else l = mid + 1;
    }
    cout << ans << el;
    for (int i = 1, j = 0; i <= n; ++i) {
        int cnt = 0;
        while (j < m && cnt < ans && a[j].first <= i && a[j].first + d >= i) {
            cout << a[j].second << " ";
            ++cnt;
            ++j;
        } 
        cout << "0\n";
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int testcase = 1; /// cin >> testcase;
    while (testcase--) {
        solve();
    }
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	2388 KB	Output is correct
2	Correct	17 ms	2404 KB	Output is correct
3	Correct	19 ms	2408 KB	Output is correct
4	Correct	23 ms	2508 KB	Output is correct
5	Correct	19 ms	2408 KB	Output is correct
6	Correct	18 ms	2404 KB	Output is correct
7	Correct	36 ms	2380 KB	Output is correct
8	Correct	22 ms	2412 KB	Output is correct
9	Correct	33 ms	2660 KB	Output is correct
10	Correct	29 ms	2652 KB	Output is correct
11	Correct	26 ms	2388 KB	Output is correct
12	Correct	53 ms	4736 KB	Output is correct
13	Correct	83 ms	6928 KB	Output is correct
14	Correct	109 ms	9264 KB	Output is correct
15	Correct	124 ms	11472 KB	Output is correct
16	Correct	166 ms	13800 KB	Output is correct
17	Correct	188 ms	16012 KB	Output is correct
18	Correct	211 ms	18368 KB	Output is correct
19	Correct	277 ms	20812 KB	Output is correct
20	Correct	199 ms	16044 KB	Output is correct