Submission #783657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783657	2023-07-15T07:37:28 Z	uy842003	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	282 ms	30312 KB

jobs

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
#define endl '\n'

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, d, m;
    cin >> n >> d >> m;
    vector<vector<int>> job(n + 1);
    for (int i = 1; i <= m; i++) {
        int start;
        cin >> start;
        job[start].push_back(i);
    }

    vector<vector<int>> ans;
    int ll = 0, rr = m;
    while (ll < rr) {
        int mm = (ll + rr) / 2;
        vector<vector<int>> tans(n + 1);
        queue<pair<int, int>> in_process;
        for (int i = 1; i <= n; i++) {
            for (int j : job[i])
                in_process.push({j, i + d});
            for (int j = 0; j < mm; j++) {
                if (in_process.size() == 0) break;
                auto tmp = in_process.front();
                if (tmp.second < i) break;
                tans[i].push_back(tmp.first);
                in_process.pop();
            }
        }
        if (in_process.size() > 0)
            ll = mm + 1;
        else {
            rr = mm;
            ans = tans;
        }
    }

    cout << rr << endl;
    for (int i = 1; i <= n; i++) {
        for (int j : ans[i])
            cout << j << ' ';
        cout << 0 << endl;
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3740 KB	Output is correct
2	Correct	22 ms	3732 KB	Output is correct
3	Correct	22 ms	3820 KB	Output is correct
4	Correct	22 ms	3748 KB	Output is correct
5	Correct	22 ms	3748 KB	Output is correct
6	Correct	22 ms	3740 KB	Output is correct
7	Correct	22 ms	3768 KB	Output is correct
8	Correct	22 ms	3728 KB	Output is correct
9	Correct	39 ms	10148 KB	Output is correct
10	Correct	39 ms	10224 KB	Output is correct
11	Correct	24 ms	3076 KB	Output is correct
12	Correct	58 ms	5448 KB	Output is correct
13	Correct	90 ms	9056 KB	Output is correct
14	Correct	123 ms	13076 KB	Output is correct
15	Correct	114 ms	13540 KB	Output is correct
16	Correct	174 ms	17612 KB	Output is correct
17	Correct	282 ms	22760 KB	Output is correct
18	Correct	190 ms	21876 KB	Output is correct
19	Correct	236 ms	30312 KB	Output is correct
20	Correct	214 ms	22772 KB	Output is correct