Submission #1119450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119450	2024-11-27T04:30:50 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	463 ms	65536 KB

jobs

import java.io.*;
import java.util.*;

public class jobs {
    static final int MAXN = 100001;
    static int[] Cn = new int[MAXN];
    static Deque<Integer>[] Req = new ArrayDeque[MAXN];
    static int n, m, d;

    public static boolean test(int k) {
        int dd = 1, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) continue;
            if (dd < x - d) {
                dd = x - d;
                r = 0;
            }
            dd += (Cn[x] + r) / k;
            r = (Cn[x] + r) % k;
            if (dd > x + 1 || (dd == x + 1 && r > 0)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int x = 0; x <= n; x++) {
            Req[x] = new ArrayDeque<>();
            Cn[x] = 0;
        }

        while (m-- > 0) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            int a = Integer.parseInt(st.nextToken()) + d;
            Req[a].add(m + 1);
            Cn[a]++;
        }

        int left = 1, sol = 0, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) {
                if (r <= d) r++;
            } else {
                int bound = (Cn[x] + d) / (d + 1);
                if (bound > left) {
                    left = bound;
                }
                int reduced = (Cn[x] + sol - 1) / sol;
                if (r * sol >= Cn[x]) {
                    r -= reduced;
                    r++;
                } else {
                    sol += (Cn[x] - r * sol + d) / (d + 1);
                    r = 1;
                }
            }
        }

        while (left < sol) {
            int mid = (left + sol) / 2;
            if (test(mid)) {
                sol = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(sol);

        StringBuilder output = new StringBuilder();
        int dc = 1, dd = 1, x = 1;

        while (dd <= n) {
            if (Req[x].isEmpty()) {
                x++;
                while (x <= n && Req[x].isEmpty()) x++;
                if (x > n) break;
            }

            if (dd < x - d) {
                output.append("0\n");
                dd++;
                dc = 1;
            } else {
                output.append(Req[x].pollFirst()).append(" ");
                if (++dc > sol) {
                    dc = 1;
                    dd++;
                    output.append("0\n");
                }
            }
        }

        if (dc > 1) {
            dd++;
            output.append("0\n");
        }
        while (dd++ <= n) {
            output.append("0\n");
        }

        System.out.print(output);
    }
}

Compilation message

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	214 ms	18368 KB	Execution failed because the return code was nonzero
2	Runtime error	218 ms	18420 KB	Execution failed because the return code was nonzero
3	Runtime error	223 ms	18412 KB	Execution failed because the return code was nonzero
4	Runtime error	214 ms	18032 KB	Execution failed because the return code was nonzero
5	Runtime error	217 ms	18176 KB	Execution failed because the return code was nonzero
6	Runtime error	228 ms	18332 KB	Execution failed because the return code was nonzero
7	Runtime error	222 ms	18372 KB	Execution failed because the return code was nonzero
8	Runtime error	223 ms	18300 KB	Execution failed because the return code was nonzero
9	Runtime error	277 ms	29172 KB	Execution failed because the return code was nonzero
10	Runtime error	265 ms	29060 KB	Execution failed because the return code was nonzero
11	Runtime error	224 ms	17472 KB	Execution failed because the return code was nonzero
12	Runtime error	253 ms	21436 KB	Execution failed because the return code was nonzero
13	Runtime error	282 ms	25324 KB	Execution failed because the return code was nonzero
14	Runtime error	327 ms	28480 KB	Execution failed because the return code was nonzero
15	Runtime error	302 ms	31128 KB	Execution failed because the return code was nonzero
16	Runtime error	396 ms	37588 KB	Execution failed because the return code was nonzero
17	Runtime error	409 ms	41964 KB	Execution failed because the return code was nonzero
18	Runtime error	385 ms	45096 KB	Execution failed because the return code was nonzero
19	Runtime error	463 ms	65536 KB	Execution killed with signal 9
20	Runtime error	447 ms	41092 KB	Execution failed because the return code was nonzero