Submission #1119456

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119456	2024-11-27T04:53:02 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	54 / 100	426 ms	47324 KB

jobs

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

public class jobs {
    static int[] Cn; // Job counts per day
    static HashMap<Integer, int[]> 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

        int[] jobBuffer = new int[m]; // Temporary buffer to store jobs
        int jobCount = 0;

        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) {
                jobBuffer[jobCount++] = i; // Store job index (1-based)
                Cn[a]++;
            }
        }

        // Transfer to Req in a memory-efficient way
        int offset = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] > 0) {
                Req.put(x, Arrays.copyOfRange(jobBuffer, offset, offset + Cn[x]));
                offset += Cn[x];
            }
        }

        // 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) {
                if (r <= d) r++;
            } else {
                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;

        int[] currentJobs = Req.getOrDefault(1, new int[0]);
        int jobIndex = 0;

        while (dd <= n) {
            if (jobIndex >= currentJobs.length) {
                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[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

54.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	309 ms	18716 KB	Output is correct
2	Correct	309 ms	19024 KB	Output is correct
3	Correct	318 ms	18348 KB	Output is correct
4	Correct	300 ms	19172 KB	Output is correct
5	Correct	295 ms	19620 KB	Output is correct
6	Correct	320 ms	19120 KB	Output is correct
7	Correct	311 ms	19128 KB	Output is correct
8	Correct	330 ms	18988 KB	Output is correct
9	Partially correct	317 ms	19296 KB	Partially correct
10	Partially correct	316 ms	19504 KB	Partially correct
11	Partially correct	297 ms	20284 KB	Partially correct
12	Partially correct	313 ms	22828 KB	Partially correct
13	Partially correct	306 ms	23296 KB	Partially correct
14	Partially correct	360 ms	29660 KB	Partially correct
15	Partially correct	322 ms	30540 KB	Partially correct
16	Runtime error	415 ms	38684 KB	Memory limit exceeded
17	Runtime error	426 ms	44572 KB	Memory limit exceeded
18	Runtime error	399 ms	45132 KB	Memory limit exceeded
19	Runtime error	421 ms	47324 KB	Memory limit exceeded
20	Runtime error	423 ms	43176 KB	Memory limit exceeded