Submission #851774

#	Time	Username	Problem	Language	Result	Execution time	Memory
851774		nhphucqt	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	251 ms	23684 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+7;
const int DAY = 1e5+7;
int numDay, delay, numTask;
pair<int, int> beg[N];
vector<int> res[DAY];

bool isOk(int numWorker, bool isTrace = false) {
    queue<pair<int,int>> q;
    for (int i = 1, j = 1; i <= numDay; ++i) {
        while (j <= numTask && beg[j].first == i) {
            q.emplace(beg[j].first+delay, beg[j].second);
            j++;
        }
        if (!q.empty() && q.front().first < i) {
            return false;
        }
        int cnt = 0;
        while (!q.empty() && ++cnt <= numWorker) {
            if (isTrace) {
                res[i].push_back(q.front().second);
            }
            q.pop();
        }
    }
    return true;
}

int solve() {
    int l = 1;
    int r = numTask;
    while (l < r) {
        int m = l+r>>1;
        if (isOk(m)) {
            r = m;
        } else {
            l = m+1;
        }
    }
    return l;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    #ifdef NHPHUCQT
    freopen("demo.inp", "r", stdin);
    freopen("demo.out", "w", stdout);
    #endif

    cin >> numDay >> delay >> numTask;
    for (int i = 1; i <= numTask; ++i) {
        cin >> beg[i].first;
        beg[i].second = i;
    }

    sort(beg+1,beg+numTask+1);

    // for (int i = 1; i <= numTask; ++i) {
    //     cerr << beg[i].first << ' ';
    // }
    // cerr << '\n';

    int num = solve();
    isOk(num, true);

    cout << num << '\n';
    for (int i = 1; i <= numDay; ++i) {
        for (int x : res[i]) {
            cout << x << ' ';
        }
        cout << 0 << '\n';
    }

    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int solve()':
jobs.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int m = l+r>>1;
      |                 ~^~

• Subtask 1: 100 / 100