Submission #1119447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119447	2024-11-27T04:24:23 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	267 ms	55248 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));
        String[] firstLine = br.readLine().split(" ");
        n = Integer.parseInt(firstLine[0]);
        d = Integer.parseInt(firstLine[1]);
        m = Integer.parseInt(firstLine[2]);

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

        for (int i = 0; i < m; i++) {
            int a = Integer.parseInt(br.readLine()) + d;
            Req[a].add(i + 1);
            Cn[a]++;
        }

        // Compute lower and upper bounds for binary search
        int left = 1, sol = 0, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) {
                if (r <= d) r++;
            } else {
                if ((Cn[x] + d) / (d + 1) > left) {
                    left = (Cn[x] + d) / (d + 1);
                }
                if (r * sol >= Cn[x]) {
                    r -= (Cn[x] + sol - 1) / sol;
                    r++;
                } else {
                    sol += (Cn[x] - r * sol + d) / (d + 1);
                    r = 1;
                }
            }
        }

        // Binary search to find the solution
        while (left < sol) {
            int mid = (left + sol) / 2;
            if (test(mid)) {
                sol = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(sol);

        // Output the schedule
        int dc = 1, dd = 1, x = 1;
        Iterator<Integer> p = Req[1].iterator();

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

            if (dd < x - d) {
                System.out.println("0");
                dd++;
                dc = 1;
            } else {
                System.out.print(p.next() + " ");
                if (++dc > sol) {
                    dc = 1;
                    dd++;
                    System.out.println("0");
                }
            }
        }

        if (dc > 1) {
            dd++;
            System.out.println("0");
        }
        while (dd++ <= n) {
            System.out.println("0");
        }
    }
}

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	157 ms	16440 KB	Execution failed because the return code was nonzero
2	Runtime error	146 ms	16720 KB	Execution failed because the return code was nonzero
3	Runtime error	153 ms	16580 KB	Execution failed because the return code was nonzero
4	Runtime error	153 ms	16320 KB	Execution failed because the return code was nonzero
5	Runtime error	160 ms	16232 KB	Execution failed because the return code was nonzero
6	Runtime error	161 ms	16692 KB	Execution failed because the return code was nonzero
7	Runtime error	154 ms	16468 KB	Execution failed because the return code was nonzero
8	Runtime error	149 ms	16544 KB	Execution failed because the return code was nonzero
9	Runtime error	193 ms	25620 KB	Execution failed because the return code was nonzero
10	Runtime error	202 ms	25428 KB	Execution failed because the return code was nonzero
11	Runtime error	160 ms	16160 KB	Execution failed because the return code was nonzero
12	Runtime error	154 ms	19860 KB	Execution failed because the return code was nonzero
13	Runtime error	165 ms	21680 KB	Execution failed because the return code was nonzero
14	Runtime error	189 ms	28536 KB	Execution failed because the return code was nonzero
15	Runtime error	180 ms	28576 KB	Execution failed because the return code was nonzero
16	Runtime error	209 ms	36140 KB	Execution failed because the return code was nonzero
17	Runtime error	221 ms	39768 KB	Execution failed because the return code was nonzero
18	Runtime error	205 ms	37712 KB	Execution failed because the return code was nonzero
19	Runtime error	267 ms	55248 KB	Execution failed because the return code was nonzero
20	Runtime error	217 ms	39600 KB	Execution failed because the return code was nonzero