Submission #1183007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183007		sur	Job Scheduling (CEOI12_jobs)	Java	0 / 100	364 ms	131072 KiB

jobs

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

public class jobs {
    // Maximum number of days (plus a safety margin) to accommodate job requests.
    private static final int MAX_DAYS = (int) 1e6 + 5;

    // totalDays: Total available days.
    // numJobRequests: Total number of job requests.
    // deadlineDuration: Extra days allowed after a job is requested.
    private static int totalDays, numJobRequests, deadlineDuration;
    
    // requestCountByDay[i] stores how many jobs are requested on day i.
    private static int[] requestCountByDay = new int[MAX_DAYS];

    /**
     * Checks if a given daily machine capacity is sufficient to process all jobs
     * within their deadlines.
     *
     * @param dailyMachineCapacity The number of jobs that can be processed per day.
     * @return true if all jobs can be processed within totalDays and deadlines,
     *         false otherwise.
     */
    private static boolean isScheduleFeasible(int dailyMachineCapacity) {
        // Use a double-ended queue to track the deadlines of pending jobs.
        Deque<Integer> deadlineQueue = new ArrayDeque<>();

        // Simulate processing from day 1 to totalDays.
        for (int currentDay = 1; currentDay <= totalDays; currentDay++) {
            // If the job with the earliest deadline is already overdue (i.e., its deadline is before the current day),
            // then the current capacity is not sufficient.
            if (!deadlineQueue.isEmpty() && deadlineQueue.peekFirst() < currentDay) {
                return false;
            }
            
            // For every job requested on the current day, add its deadline (currentDay + deadlineDuration)
            // to the deadlineQueue.
            for (int j = 0; j < requestCountByDay[currentDay]; j++) {
                deadlineQueue.addLast(currentDay + deadlineDuration);
            }
            
            // Process (simulate) up to dailyMachineCapacity jobs on the current day.
            // These represent the available machines processing the jobs.
            for (int j = 0; j < dailyMachineCapacity; j++) {
                // If there are no pending jobs, break out early.
                if (deadlineQueue.isEmpty()) {
                    break;
                }
                // Remove the job with the earliest deadline from the queue (i.e., complete it).
                deadlineQueue.pollFirst();
            }
        }
        // After processing all days, if there are no pending jobs left,
        // it means the given daily capacity successfully processed all jobs within their deadlines.
        return deadlineQueue.isEmpty();
    }

    public static void main(String[] args) throws IOException {
        // Set up input reading.
        DataInputStream dataInput = new DataInputStream(System.in);
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(dataInput));

        // The first input line contains totalDays, deadlineDuration, and numJobRequests.
        StringTokenizer firstLine = new StringTokenizer(bufferedReader.readLine());
        totalDays = Integer.parseInt(firstLine.nextToken());
        deadlineDuration = Integer.parseInt(firstLine.nextToken());
        numJobRequests = Integer.parseInt(firstLine.nextToken());

        // The second input line contains the request day for each job.
        // Initialize the requestCountByDay array to zero.
        Arrays.fill(requestCountByDay, 0);
        StringTokenizer secondLine = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < numJobRequests; i++) {
            int requestDay = Integer.parseInt(secondLine.nextToken());
            requestCountByDay[requestDay]++;
        }

        // Binary search to determine the minimum daily machine capacity (jobs processed per day)
        // that allows all jobs to be completed within the allowed deadlines.
        int left = 1, right = numJobRequests, optimalDailyCapacity = 0;
        while (left <= right) {
            int midCapacity = (left + right) >> 1;
            if (isScheduleFeasible(midCapacity)) {
                // If the schedule is feasible with the current capacity,
                // try a smaller capacity (move the right bound).
                right = midCapacity - 1;
                optimalDailyCapacity = midCapacity;
            } else {
                // Otherwise, increase the capacity (move the left bound).
                left = midCapacity + 1;
            }
        }

        // Output the found minimum capacity required.
        System.out.println(optimalDailyCapacity);
        // The following prints an end-of-day marker (0) for each day,
        // conforming to the problem's specified output format.
        for (int day = 0; day < totalDays; day++) {
            System.out.println(0);
        }
    }
}

• Subtask 1: 0 / 100