Submission #1245448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245448		wedonttalkanymore	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	53 ms	20912 KiB

jobs

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

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 1 << 16;

int n, d, m;
int a[N];
vector <int> days[N];
vector <pii> comp;
bool check(int mid) {
    for (int i = 1; i <= n; i++) days[i].clear();
    int p = 0;
    bool check = true;
    for (int i = 1; i <= n; i++) {
        int x = mid;
        while(x > 0 && p < m) {
            days[i].push_back(comp[p].se);
            if (i - d > comp[p].fi) {
                check = false;
                break;
            }
            p++;
            x--;
        }
        if (!check) break;
        days[i].push_back(0);
    }
    return check;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> d >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        comp.emplace_back(a[i], i);
    }
    // sort(a + 1, a + m + 1);
    sort(comp.begin(), comp.end());
    // for (int i = 1; i <= m; i++) cout << a[i] << ' ';
    cout << '\n';
    int l = 1, r = 1e9, ans = 0;
    while(l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans << '\n';
    for (int i = 1; i <= n; i++) {
        for (auto v : days[i]) cout << v << ' ';
        cout << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 100