Submission #1119461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119461	2024-11-27T04:55:51 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	54 / 100	405 ms	45956 KB

jobs

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

public class jobs {
    static int[] Cn; // Job counts per day
    static int[] jobIndices; // Flat array of job indices
    static int[] jobStart; // Start indices for jobs per day in `jobIndices`
    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 only for relevant days
        jobIndices = new int[m]; // Flat array to store all job requests
        jobStart = new int[n + 2]; // Start indices of jobs per day (last as sentinel)

        // Read input and populate job counts and job indices
        int jobCounter = 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) {
                Cn[a]++;
                jobIndices[jobCounter++] = i; // Store job number
            }
        }

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

        // Binary search for the minimum valid value of `k`
        int left = 1, sol = m;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] > 0) {
                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);

        // Generate the schedule output
        StringBuilder output = new StringBuilder();
        int dc = 1, dd = 1, x = 1;
        int currentJobIndex = jobStart[1];

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

            if (dd < x - d) {
                output.append("0\n");
                dd++;
                dc = 1;
            } else {
                output.append(jobIndices[currentJobIndex++]).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	314 ms	17300 KB	Output is correct
2	Correct	329 ms	17604 KB	Output is correct
3	Correct	334 ms	17300 KB	Output is correct
4	Correct	325 ms	17536 KB	Output is correct
5	Correct	352 ms	17852 KB	Output is correct
6	Correct	336 ms	17716 KB	Output is correct
7	Correct	331 ms	17436 KB	Output is correct
8	Correct	309 ms	17680 KB	Output is correct
9	Partially correct	315 ms	17544 KB	Partially correct
10	Partially correct	309 ms	17544 KB	Partially correct
11	Partially correct	313 ms	16748 KB	Partially correct
12	Partially correct	298 ms	20224 KB	Partially correct
13	Partially correct	328 ms	21172 KB	Partially correct
14	Partially correct	348 ms	27352 KB	Partially correct
15	Partially correct	374 ms	28544 KB	Partially correct
16	Runtime error	362 ms	34364 KB	Memory limit exceeded
17	Runtime error	366 ms	40212 KB	Memory limit exceeded
18	Runtime error	361 ms	41660 KB	Memory limit exceeded
19	Runtime error	405 ms	45956 KB	Memory limit exceeded
20	Runtime error	362 ms	38300 KB	Memory limit exceeded