Submission #106641

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
106641	2019-04-19T10:51:42 Z	naoai	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	487 ms	20700 KB

jobs

#include <bits/stdc++.h>

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

const int mmax = 1e6 + 5;

int n, d, m;
int a[mmax + 1];
pair<int, int> v[mmax + 1];

bool check (int val) {
    int i = 1;
    for (int z = 1; z <= n; ++ z) {
        int aux = i;
        for (int j = i; j < i + val && a[j] <= z && j <= m; ++ j, ++ aux) {
            if (a[j] + d < z)
                return 0;
        }
        i = aux;
    }

    return 1;
}

int main() {
   // ios::sync_with_stdio(0); cin.tie(nullptr);
    cin >> n >> d >> m;

    for (int i = 1; i <= m; ++ i) {
        int x;
        cin >> x;
        a[i] = x;
        v[i] = {x, i};
    }

    int n2 = 1;
    for (n2 = 1; (n2 << 1) <= m; n2 <<= 1) {
    }

    sort(a + 1, a + m + 1);

    int ans = m;
    for (int step = n2; step > 0; step >>= 1) {
        if (ans - step > 0 && check(ans - step)) {
            ans -= step;
        }
    }

    sort(v + 1, v + m + 1);

    cout << ans << "\n";

    int i = 1;
    for (int z = 1; z <= n; ++ z) {
        int aux = i;
        for (int j = i; j < i + ans && a[j] <= z && j <= m; ++ j, ++ aux) {
            cout << v[j].second << " ";
        }

        i = aux;
        cout << "0\n";
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	2424 KB	Output is correct
2	Correct	56 ms	2424 KB	Output is correct
3	Correct	53 ms	2548 KB	Output is correct
4	Correct	49 ms	2424 KB	Output is correct
5	Correct	49 ms	2424 KB	Output is correct
6	Correct	51 ms	2424 KB	Output is correct
7	Correct	36 ms	2424 KB	Output is correct
8	Correct	68 ms	2440 KB	Output is correct
9	Correct	45 ms	2580 KB	Output is correct
10	Correct	79 ms	2552 KB	Output is correct
11	Correct	60 ms	2472 KB	Output is correct
12	Correct	133 ms	4688 KB	Output is correct
13	Correct	155 ms	7012 KB	Output is correct
14	Correct	241 ms	9720 KB	Output is correct
15	Correct	257 ms	11640 KB	Output is correct
16	Correct	371 ms	14396 KB	Output is correct
17	Correct	405 ms	16612 KB	Output is correct
18	Correct	470 ms	18296 KB	Output is correct
19	Correct	487 ms	20700 KB	Output is correct
20	Correct	454 ms	16632 KB	Output is correct