Submission #565350

#	Time	Username	Problem	Language	Result	Execution time	Memory
565350		trytovoi	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	277 ms	20812 KiB

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 / 100