Submission #1119457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119457	2024-11-27T04:54:06 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	65 / 100	748 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]; // Allocate memory only for relevant days
        Req = new HashMap<>(); // Use sparse storage for job requests

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

        // Compute lower and upper bounds for binary search
        int left = 1, sol = m, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) continue;
            int bound = (Cn[x] + d) / (d + 1);
            left = Math.max(left, bound);
        }

        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;

        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.getOrDefault(x, Collections.emptyList());
                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

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	370 ms	20548 KB	Output is correct
2	Correct	374 ms	20548 KB	Output is correct
3	Correct	378 ms	21788 KB	Output is correct
4	Correct	379 ms	21620 KB	Output is correct
5	Correct	370 ms	21932 KB	Output is correct
6	Correct	400 ms	21592 KB	Output is correct
7	Correct	383 ms	21800 KB	Output is correct
8	Correct	404 ms	21612 KB	Output is correct
9	Correct	366 ms	19996 KB	Output is correct
10	Correct	374 ms	20272 KB	Output is correct
11	Correct	377 ms	19288 KB	Output is correct
12	Correct	402 ms	27216 KB	Output is correct
13	Correct	420 ms	30000 KB	Output is correct
14	Runtime error	550 ms	40636 KB	Memory limit exceeded
15	Runtime error	465 ms	42908 KB	Memory limit exceeded
16	Runtime error	628 ms	54968 KB	Memory limit exceeded
17	Runtime error	711 ms	65536 KB	Execution killed with signal 9
18	Runtime error	567 ms	64632 KB	Memory limit exceeded
19	Runtime error	614 ms	65536 KB	Execution killed with signal 9
20	Runtime error	748 ms	65536 KB	Execution killed with signal 9