Submission #1119454

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119454	2024-11-27T04:51:11 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	60 / 100	685 ms	65536 KB

jobs

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

public class jobs {
    static int[] Cn; // Job counts per day
    static Map<Integer, List<Integer>> Req; // Sparse storage for job requests
    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());

        Cn = new int[n + 1]; // Use only [0, n] to minimize space
        Req = new HashMap<>(); // Sparse map to store job requests

        for (int i = 1; i <= m; i++) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            int a = Integer.parseInt(st.nextToken()) + d;
            Req.computeIfAbsent(a, k -> new ArrayList<>()).add(i);
            if (a <= n) {
                Cn[a]++;
            }
        }

        // Compute lower and upper bounds for binary search
        int left = 1, sol = 1, 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);

        // Output the schedule
        StringBuilder output = new StringBuilder();
        int dc = 1, dd = 1, x = 1;

        // Handle jobs sequentially from Req
        List<Integer> currentJobs = Req.getOrDefault(1, Collections.emptyList());
        int jobIndex = 0;

        while (dd <= n) {
            if (jobIndex >= currentJobs.size()) {
                x++;
                while (x <= n && !Req.containsKey(x)) x++;
                if (x > n) break;
                currentJobs = Req.get(x);
                jobIndex = 0;
            }

            if (dd < x - d) {
                output.append("0\n");
                dd++;
                dc = 1;
            } else {
                output.append(currentJobs.get(jobIndex++)).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);
    }
}

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	365 ms	24820 KB	Output is correct
2	Correct	350 ms	24492 KB	Output is correct
3	Correct	359 ms	24052 KB	Output is correct
4	Correct	360 ms	23120 KB	Output is correct
5	Correct	381 ms	23408 KB	Output is correct
6	Correct	387 ms	24228 KB	Output is correct
7	Correct	367 ms	25320 KB	Output is correct
8	Correct	363 ms	23420 KB	Output is correct
9	Correct	332 ms	22984 KB	Output is correct
10	Correct	328 ms	23568 KB	Output is correct
11	Correct	353 ms	24680 KB	Output is correct
12	Correct	381 ms	29156 KB	Output is correct
13	Runtime error	441 ms	32936 KB	Memory limit exceeded
14	Runtime error	605 ms	43204 KB	Memory limit exceeded
15	Runtime error	518 ms	45468 KB	Memory limit exceeded
16	Runtime error	681 ms	57652 KB	Memory limit exceeded
17	Runtime error	685 ms	65536 KB	Execution killed with signal 9
18	Runtime error	663 ms	65536 KB	Execution killed with signal 9
19	Runtime error	624 ms	65536 KB	Execution killed with signal 9
20	Runtime error	672 ms	65536 KB	Execution killed with signal 9