Submission #1119460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119460		johu	Job Scheduling (CEOI12_jobs)	Java	Compilation error	0 ms	0 KiB

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);
    }
}

Compilation message (stderr)

jobs.java:4: error: class Jobs is public, should be declared in a file named Jobs.java
public class Jobs {
       ^
1 error