Submission #1119446

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119446	2024-11-27T04:23:47 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	277 ms	54904 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 reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.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;
        }

        for (int i = 0; i < m; i++) {
            int a = Integer.parseInt(reader.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	156 ms	16532 KB	Execution failed because the return code was nonzero
2	Runtime error	157 ms	16384 KB	Execution failed because the return code was nonzero
3	Runtime error	148 ms	16668 KB	Execution failed because the return code was nonzero
4	Runtime error	153 ms	16368 KB	Execution failed because the return code was nonzero
5	Runtime error	146 ms	16568 KB	Execution failed because the return code was nonzero
6	Runtime error	175 ms	16580 KB	Execution failed because the return code was nonzero
7	Runtime error	154 ms	16412 KB	Execution failed because the return code was nonzero
8	Runtime error	147 ms	16292 KB	Execution failed because the return code was nonzero
9	Runtime error	190 ms	25660 KB	Execution failed because the return code was nonzero
10	Runtime error	217 ms	25436 KB	Execution failed because the return code was nonzero
11	Runtime error	160 ms	15988 KB	Execution failed because the return code was nonzero
12	Runtime error	149 ms	19912 KB	Execution failed because the return code was nonzero
13	Runtime error	162 ms	21756 KB	Execution failed because the return code was nonzero
14	Runtime error	191 ms	28544 KB	Execution failed because the return code was nonzero
15	Runtime error	175 ms	28172 KB	Execution failed because the return code was nonzero
16	Runtime error	183 ms	36220 KB	Execution failed because the return code was nonzero
17	Runtime error	201 ms	39948 KB	Execution failed because the return code was nonzero
18	Runtime error	213 ms	37684 KB	Execution failed because the return code was nonzero
19	Runtime error	277 ms	54904 KB	Execution failed because the return code was nonzero
20	Runtime error	202 ms	39804 KB	Execution failed because the return code was nonzero