Submission #851774

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
851774	2023-09-20T15:02:24 Z	nhphucqt	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	251 ms	23684 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) {
    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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	6992 KB	Output is correct
2	Correct	23 ms	6992 KB	Output is correct
3	Correct	21 ms	6744 KB	Output is correct
4	Correct	24 ms	6736 KB	Output is correct
5	Correct	22 ms	6744 KB	Output is correct
6	Correct	22 ms	6900 KB	Output is correct
7	Correct	21 ms	7000 KB	Output is correct
8	Correct	22 ms	6992 KB	Output is correct
9	Correct	31 ms	6224 KB	Output is correct
10	Correct	31 ms	6268 KB	Output is correct
11	Correct	25 ms	5968 KB	Output is correct
12	Correct	55 ms	8020 KB	Output is correct
13	Correct	76 ms	11856 KB	Output is correct
14	Correct	107 ms	14028 KB	Output is correct
15	Correct	128 ms	13904 KB	Output is correct
16	Correct	153 ms	18508 KB	Output is correct
17	Correct	185 ms	21968 KB	Output is correct
18	Correct	212 ms	21740 KB	Output is correct
19	Correct	251 ms	23684 KB	Output is correct
20	Correct	183 ms	21912 KB	Output is correct