Submission #851776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
851776	2023-09-20T15:03:49 Z	nhphucqt	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1000 ms	18820 KB

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) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<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.top().first < i) {
            return false;
        }
        int cnt = 0;
        while (!q.empty() && ++cnt <= numWorker) {
            if (isTrace) {
                res[i].push_back(q.top().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

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

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	6992 KB	Output is correct
2	Correct	146 ms	7024 KB	Output is correct
3	Correct	140 ms	7120 KB	Output is correct
4	Correct	138 ms	7084 KB	Output is correct
5	Correct	138 ms	7020 KB	Output is correct
6	Correct	141 ms	7112 KB	Output is correct
7	Correct	140 ms	7132 KB	Output is correct
8	Correct	138 ms	7124 KB	Output is correct
9	Correct	119 ms	5980 KB	Output is correct
10	Correct	136 ms	6120 KB	Output is correct
11	Correct	81 ms	5744 KB	Output is correct
12	Correct	256 ms	7112 KB	Output is correct
13	Correct	306 ms	10668 KB	Output is correct
14	Correct	388 ms	12268 KB	Output is correct
15	Correct	472 ms	12372 KB	Output is correct
16	Correct	391 ms	15564 KB	Output is correct
17	Correct	554 ms	18496 KB	Output is correct
18	Execution timed out	1014 ms	18736 KB	Time limit exceeded
19	Execution timed out	1048 ms	14416 KB	Time limit exceeded
20	Correct	552 ms	18820 KB	Output is correct