Submission #543109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543109	2022-03-29T11:14:47 Z	Saeed_247	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	222 ms	16896 KB

jobs

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

const int N = 1e5 + 10;
int n, m, d, arr[N];
vector<int> adj[N];

bool check(int x) {
    queue<int> st;
    int delay = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < arr[i]; j++) st.push(i);
        int t = st.size();
        for (int j = 0; j < min(x, t); j++) {
            delay = max(delay, abs(i - st.front()));
            st.pop();
        }
    }
    if (!st.empty()) {
        return false;
    }
    return delay <= d;
}

void print(int x) {
    queue<int> st;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < arr[i]; j++) st.push(adj[i][j]);
        int t = st.size();
        for (int j = 0; j < min(x, t); j++) {
            cout << st.front() << ' ';
            st.pop();
        }
        cout << "0\n";
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) {
        int in; cin >> in;
        arr[in]++;
        adj[in].push_back(i + 1);
    }
    int lo = 1, hi = m;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) {
            hi = mid;
        }
        else {
            lo = mid + 1;
        }
    }
    cout << hi << '\n';
    print(hi);
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	4288 KB	Output is correct
2	Correct	25 ms	4312 KB	Output is correct
3	Correct	34 ms	4320 KB	Output is correct
4	Correct	24 ms	4308 KB	Output is correct
5	Correct	24 ms	4296 KB	Output is correct
6	Correct	25 ms	4300 KB	Output is correct
7	Correct	23 ms	4300 KB	Output is correct
8	Correct	25 ms	4284 KB	Output is correct
9	Correct	29 ms	4436 KB	Output is correct
10	Correct	29 ms	4356 KB	Output is correct
11	Correct	28 ms	4156 KB	Output is correct
12	Correct	46 ms	5744 KB	Output is correct
13	Correct	72 ms	7956 KB	Output is correct
14	Correct	116 ms	10244 KB	Output is correct
15	Correct	118 ms	10948 KB	Output is correct
16	Correct	157 ms	13736 KB	Output is correct
17	Correct	187 ms	16680 KB	Output is correct
18	Correct	188 ms	15720 KB	Output is correct
19	Correct	222 ms	16896 KB	Output is correct
20	Correct	186 ms	16564 KB	Output is correct