제출 #1183002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183002		sur	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1098 ms	131072 KiB

jobs

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

public class jobs {
    public static void main(String[] args) {
        Kattio io = new Kattio();

        final int n = io.nextInt();  // Total number of days
        final int d = io.nextInt();  // Extra days allowed after request
        final int m = io.nextInt();  // Number of job requests

        // Read jobs: jobDays[j] is the request day; jobIds[j] is the job number (1-indexed)
        int[] jobDays = new int[m];
        int[] jobIds = new int[m];
        for (int i = 0; i < m; i++) {
            jobDays[i] = io.nextInt();
            jobIds[i] = i + 1;
        }
        
        // Create an array of job indices and sort them by jobDays ascending.
        Integer[] order = new Integer[m];
        for (int i = 0; i < m; i++) {
            order[i] = i;
        }
        Arrays.sort(order, Comparator.comparingInt(i -> jobDays[i]));

        // Binary search for the minimum number of machines (i.e. jobs per day capacity)
        int lo = 1, hi = m;
        int[] bestAssigned = null;   // For storing best assignment: bestAssigned[job index] = assigned day
        int bestMachineCount = -1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            int[] assigned = simulate(n, d, m, mid, order, jobDays);
            if (assigned != null) { 
                hi = mid;
                bestAssigned = assigned;
                bestMachineCount = mid;
            } else {
                lo = mid + 1;
            }
        }
        // If binary search ends without storing bestAssigned (or for safety, re-simulate),
        // use lo as the optimal machine count.
        if (bestAssigned == null) {
            bestMachineCount = lo;
            bestAssigned = simulate(n, d, m, lo, order, jobDays);
        }
        
        // Output the optimal number of machines
        io.println(bestMachineCount);
        
        // Build the schedule per day.
        // Using an array of ArrayLists; day 1 is at index 0.
        ArrayList<Integer>[] schedule = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            schedule[i] = new ArrayList<>();
        }
        // We'll use the simulation order (i.e. the sorted order) since our simulation
        // processed jobs in that order and assigned non-decreasing days.
        for (int i = 0; i < m; i++) {
            int jobIndex = order[i];
            int day = bestAssigned[jobIndex]; // day is 1-indexed.
            schedule[day - 1].add(jobIds[jobIndex]);
        }
        
        // Output each day's schedule terminated by 0.
        for (int day = 0; day < n; day++) {
            for (int id : schedule[day]) {
                io.print(id + " ");
            }
            io.println(0);
        }

        io.close();
    }
    
    /**
     * Simulation of scheduling with the given daily capacity (machineCount). 
     * Returns an integer array "assigned" of length m where assigned[j] is the day on which job j is scheduled.
     * If scheduling fails (a job cannot be assigned within its deadline, or the day exceeds n), returns null.
     *
     * This simulation uses a single pass over the jobs in the sorted order:
     *   - currentDay is advanced as needed.
     *   - Each day may take at most machineCount jobs.
     *   - For job j (with original index from order[]), the earliest available day is max(currentDay, jobDays[j]).
     *   - It fails if that day is later than jobDays[j]+d or exceeds n.
     */
    private static int[] simulate(int n, int d, int m, int machineCount,
                                  Integer[] order, int[] jobDays) {
        int[] assigned = new int[m]; // assigned[j] will store the day (1-indexed) of job j.
        int currentDay = 1;
        int count = 0;  // Count of jobs already assigned on currentDay
        for (int i = 0; i < m; i++) {
            int j = order[i]; // original job index
            // Ensure we start no earlier than the request day of the job.
            if (currentDay < jobDays[j]) {
                currentDay = jobDays[j];
                count = 0;  // reset counter for the new day
            }
            // If currentDay exceeds the allowed deadline or total days, scheduling fails.
            if (currentDay > jobDays[j] + d || currentDay > n) {
                return null;
            }
            assigned[j] = currentDay;
            count++;
            // When current day is full, move to the next day.
            if (count == machineCount) {
                currentDay++;
                count = 0;
            }
        }
        return assigned;
    }

    // Kattio class for fast I/O.
    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;
        public Kattio() { 
            this(System.in, System.out); 
        }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        public Kattio(String problemName) throws IOException {
            super(problemName + ".out");
            r = new BufferedReader(new FileReader(problemName + ".in"));
        }
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

=======

• Subtask 1: 0 / 100