Submission #1344176

#TimeUsernameProblemLanguageResultExecution timeMemory
1344176PakinDioxideJob Scheduling (CEOI12_jobs)C++17
40 / 100
180 ms20532 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, d, m; cin >> m >> d >> n;
    pair <int, int> a[n];
    int id = 1;
    for (auto &[x, y] : a) cin >> x, y = id++;
    sort(a, a+n);
    int cnt[m+1]; memset(cnt, 0, sizeof(cnt));
    vector <int> ans[m+1];
    multiset <pair <int, int>> ms;
    int L = 1, R = 0;
    for (auto &[x, y] : a) {
        while (R < x+d && R < m) {
            R++;
            ms.emplace(0, R);
        }
        while (L < x) {
            ms.erase(ms.find(make_pair(cnt[L], L)));
            L++;
        }
        auto [c, id] = *ms.begin();
        ms.erase(ms.begin());
        ans[id].emplace_back(y);
        cnt[id]++;
        ms.emplace(cnt[id], id);
    }
    int x = 0;
    for (int i = 1; i <= m; i++) x = max(x, cnt[i]);
    cout << x << '\n';
    for (int i = 1; i <= m; i++) {
        for (auto &e : ans[i]) cout << e << ' ';
        cout << 0 << '\n';
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...