제출 #1183001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183001		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();      // number of days
        final int d = io.nextInt();      // extra days allowed after request
        final int m = io.nextInt();      // number of jobs
        
        // Use two arrays to store the job request day and its original index.
        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 indices and sort by jobDays.
        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 required.
        int lo = 1, hi = m;
        int[][] bestSchedule = null;  // schedule: bestSchedule[day] is an int[] of job IDs
        int[] bestSizes = null;       // bestSizes[day] indicates number of jobs scheduled on that day
        
        while (lo < hi) {
            int machineCount = (lo + hi) / 2;
            // Try scheduling with machineCount machines per day.
            TestResult res = isFeasible(n, d, m, machineCount, order, jobDays, jobIds);
            if (res != null) { 
                hi = machineCount; 
                bestSchedule = res.schedule;
                bestSizes = res.sizes;
            } else {
                lo = machineCount + 1;
            }
        }
        
        // Final output with the optimal machine count.
        io.println(lo);
        // Use bestSchedule if not null.
        if (bestSchedule == null) {
            TestResult finalRes = isFeasible(n, d, m, lo, order, jobDays, jobIds);
            bestSchedule = finalRes.schedule;
            bestSizes = finalRes.sizes;
        }
        
        // Output each day's schedule, with a trailing 0.
        for (int day = 0; day < n; day++) {
            for (int j = 0; j < bestSizes[day]; j++) {
                io.print(bestSchedule[day][j] + " ");
            }
            io.println(0);
        }
        io.close();
    }
    
    /**
     * TestResult holds the schedule arrays if the simulation is successful.
     */
    static class TestResult {
        int[][] schedule; // schedule for each day as fixed-size int array (length = machineCount)
        int[] sizes;      // number of jobs scheduled per day
        TestResult(int[][] schedule, int[] sizes) {
            this.schedule = schedule;
            this.sizes = sizes;
        }
    }
    
    /**
     * Simulates scheduling with a given number of machines per day.
     * Returns a TestResult if all jobs are scheduled successfully or null otherwise.
     */
    private static TestResult isFeasible(int n, int d, int m, int machineCount,
                                         Integer[] order, int[] jobDays, int[] jobIds) {
        // Preallocate an array for each day. Each day will hold at most machineCount jobs.
        int[][] schedule = new int[n][machineCount];
        int[] sizes = new int[n];  // How many jobs assigned on each day
        
        int reqNum = 0;
        // Iterate over days from 1 to n.
        for (int day = 1; day <= n && reqNum < m; day++) {
            // Fill up each day using up to machineCount machines.
            for (int j = 0; j < machineCount && reqNum < m; j++) {
                int jobIndex = order[reqNum];  // current job index in sorted order
                // If the job request day is greater than the current day, no more jobs can be scheduled today.
                if (jobDays[jobIndex] > day) {
                    break;
                }
                // Check if job can be done: its deadline is jobDays + d.
                if (jobDays[jobIndex] + d >= day) {
                    schedule[day - 1][sizes[day - 1]++] = jobIds[jobIndex];
                    reqNum++;
                } else {
                    // Job deadline missed, scheduling is impossible.
                    return null;
                }
            }
        }
        // If we have not scheduled all jobs, return null.
        return (reqNum == m) ? new TestResult(schedule, sizes) : null;
    }

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

• Subtask 1: 0 / 100