Submission #1280326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280326		ducanh0811	Job Scheduling (CEOI12_jobs)	C++20	40 / 100	175 ms	25616 KiB

jobs

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 100005

int n, d, m;
vector<int> task[MAXN];
vector<int> res[MAXN];
deque<pair<int, int>> in_queue;

struct BIT {
    int n;
    vector<int> bit;
    BIT(int _n = 0){
        n = _n;
        bit.assign(n + 5, 0);
    }

    void upd(int p, int val){
        if (p == 0) return;
        for (; p <= n; p += p & -p) bit[p] += val;
    }

    int get(int x) {
        int res = 0;
        while (x) res += bit[x], x -= x & -x;
        return res;
    }

    int get(int u, int v) {
        return get(v) - get(u - 1);
    }
} robot;

int Find(int l, int r){
    int lo = l, hi = r, ans = -1;
    while (lo <= hi){
        int mid = (lo + hi) >> 1;
        if (robot.get(l, mid) > 0){
            ans = mid;
            hi = mid - 1;
        } else lo = mid + 1;
    }
    return ans;
}

void solve(){
    cin >> n >> d >> m;
    FOR(i, 1, m){
        int x; cin >> x;
        task[x + d].push_back(i);
    }
    robot = BIT(n);
    int need_robot = 0;
    REV(i, n, d + 1) {
        for (int &x : task[i]){
            int closest = Find(i - d, i);
            if (closest == -1){
                need_robot++;
                robot.upd(i - 1, 1);
                res[i].push_back(x);
            } else {
                robot.upd(closest, -1);
                res[closest].push_back(x);
                robot.upd(closest - 1, 1);
            }
        }
        int more = robot.get(i, i);
        if (more > 0){
            robot.upd(i, -more);
            robot.upd(i - 1, more);
        }
    }
    cout << need_robot << '\n';
    FOR(i, 1, n){
        for (int &x : res[i]) cout << x << ' ';
        cout << 0 << '\n';
    }
}

/**
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4

5 3 6
1 1 1 1 1 1
**/

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

• Subtask 1: 40 / 100