Submission #1182951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182951		sosuke	Job Scheduling (CEOI12_jobs)	Java	0 / 100	542 ms	131072 KiB

jobs

import java.util.*;

public class jobs {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input: number of days (n), duration (d), and number of jobs (m)
        int n = scanner.nextInt();
        int d = scanner.nextInt();
        int m = scanner.nextInt();

        // Array to store jobs as pairs {request date, index}
        int[][] jobs = new int[m][2];
        for (int i = 0; i < m; i++) {
            int day = scanner.nextInt();
            jobs[i][0] = day; // request date
            jobs[i][1] = i + 1; // job index (1-based)
        }

        // Sort jobs by request date in ascending order
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));

        // Binary search to find the minimum number of machines required
        int lo = 1, hi = m;
        List<List<Integer>> res = null;

        while (lo < hi) {
            int machineNum = (lo + hi) / 2;

            // Test feasibility with the current number of machines
            List<List<Integer>> currResult = isFeasible(n, d, m, jobs, machineNum);

            // If feasible, update the upper bound and save the result
            if (currResult != null) {
                hi = machineNum;
                res = currResult;
            } else {
                // Otherwise, update the lower bound
                lo = machineNum + 1;
            }
        }

        // Output the result
        System.out.println(lo);
        for (int i = 0; i < n; i++) {
            if (res.get(i) != null) {
                for (int idx : res.get(i)) {
                    System.out.print(idx + " ");
                }
            }
            System.out.println(0);
        }
    }

    private static List<List<Integer>> isFeasible(int n, int d, int m, int[][] jobs, int machineCount) {
        // Initialize schedule as an array of nulls to save memory
        List<List<Integer>> schedule = new ArrayList<>(Collections.nCopies(n, null));
        int reqNum = 0;

        // Simulate each day from 1 to n
        for (int day = 1; day <= n; day++) {
            int usedMachines = 0;

            // Assign jobs to machines for the current day
            while (usedMachines < machineCount && reqNum < m && jobs[reqNum][0] <= day) {
                if (jobs[reqNum][0] + d >= day) {
                    // Add job to the schedule
                    if (schedule.get(day - 1) == null) {
                        schedule.set(day - 1, new ArrayList<>());
                    }
                    schedule.get(day - 1).add(jobs[reqNum][1]);
                    reqNum++;
                    usedMachines++;
                } else {
                    // Job cannot be completed within its deadline
                    return null;
                }
            }

            // If all jobs are processed, return the schedule
            if (reqNum == m) {
                return schedule;
            }
        }

        // If not all requests are processed within n days, return null
        return null;
    }
}

• Subtask 1: 0 / 100