Submission #1119453

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119453	2024-11-27T04:49:42 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	54 / 100	403 ms	46032 KB

jobs

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

public class jobs {
    static int[] Cn; // Job counts per day
    static int[] requests; // Flat array of all job requests
    static int[] startIndices; // Start indices for each day's jobs in `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];
        requests = new int[m];
        startIndices = new int[n + 2]; // Extra space for boundary checking

        int index = 0;
        for (int i = 0; i < m; i++) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            int a = Integer.parseInt(st.nextToken()) + d;
            if (a <= n) { // Only store valid jobs within bounds
                requests[index++] = i + 1; // Store job index (1-based)
                Cn[a]++;
            }
        }

        // Compute start indices for each day
        int offset = 0;
        for (int x = 1; x <= n; x++) {
            startIndices[x] = offset;
            offset += Cn[x];
        }
        startIndices[n + 1] = offset; // Sentinel for boundary checks

        // 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;
        int reqIdx = startIndices[1]; // Start of jobs for the first day

        while (dd <= n) {
            if (reqIdx >= startIndices[x + 1]) {
                x++;
                while (x <= n && startIndices[x] == startIndices[x + 1]) x++;
                if (x > n) break;
                reqIdx = startIndices[x];
            }

            if (dd < x - d) {
                output.append("0\n");
                dd++;
                dc = 1;
            } else {
                output.append(requests[reqIdx++]).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	18960 KB	Output is correct
2	Correct	323 ms	19132 KB	Output is correct
3	Correct	330 ms	19012 KB	Output is correct
4	Correct	300 ms	19200 KB	Output is correct
5	Correct	308 ms	18828 KB	Output is correct
6	Correct	289 ms	21352 KB	Output is correct
7	Correct	302 ms	21456 KB	Output is correct
8	Correct	293 ms	19164 KB	Output is correct
9	Partially correct	282 ms	19116 KB	Partially correct
10	Partially correct	288 ms	19088 KB	Partially correct
11	Partially correct	290 ms	18452 KB	Partially correct
12	Partially correct	301 ms	21820 KB	Partially correct
13	Partially correct	331 ms	22876 KB	Partially correct
14	Partially correct	364 ms	27868 KB	Partially correct
15	Partially correct	355 ms	29508 KB	Partially correct
16	Runtime error	363 ms	37464 KB	Memory limit exceeded
17	Runtime error	383 ms	40164 KB	Memory limit exceeded
18	Runtime error	362 ms	41836 KB	Memory limit exceeded
19	Runtime error	403 ms	46032 KB	Memory limit exceeded
20	Runtime error	365 ms	40432 KB	Memory limit exceeded