Submission #1183000

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

jobs

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

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

        int n = io.nextInt();
        int d = io.nextInt();
        int m = io.nextInt();
        
        // Use two arrays to store the job request day and its 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;
        }
        
        // Instead of using a 2D array, we will use a single array for 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]));

        List<List<Integer>> result = new ArrayList<>();

        int lo = 1, hi = m;
        while (lo < hi) {
            int machineNum = (lo + hi) / 2;
            // Test if using machineNum machines can finish the jobs on time.
            List<List<Integer>> currResult = isFeasible(n, d, m, machineNum, order, jobDays, jobIds);
            
            if (!currResult.isEmpty()) {
                hi = machineNum;
                result = currResult;
            } else {
                lo = machineNum + 1;
            }
        }
        io.println(lo);
        for (List<Integer> daySchedule : result) {
            for (int idx : daySchedule) {
                io.print(idx + " ");
            }
            io.println(0);
        }

        io.close();
    }
    
    /**
     * Checks if it is feasible to complete the jobs within n days given a deadline d
     * and using machineCount machines per day. Returns the schedule if feasible, otherwise an empty list.
     */
    private static List<List<Integer>> isFeasible(int n, int d, int m, int machineCount,
                                                    Integer[] order, int[] jobDays, int[] jobIds) {
        List<List<Integer>> schedule = new ArrayList<>(n);
        // Preallocate each day's list
        for (int i = 0; i < n; i++) {
            schedule.add(new ArrayList<>(machineCount));
        }
        int reqNum = 0;
        
        // Simulate days 1 through n.
        for (int day = 1; day <= n && reqNum < m; day++) {
            // Try filling up available machines for the current day.
            for (int j = 0; j < machineCount && reqNum < m; j++) {
                int jobIdx = order[reqNum];
                // If the next available job is not yet requested by this day, break early.
                if (jobDays[jobIdx] > day) {
                    break;
                }
                // Check if the job's deadline is met.
                if (jobDays[jobIdx] + d >= day) {
                    schedule.get(day - 1).add(jobIds[jobIdx]);
                    reqNum++;
                } else {
                    // Job missed its deadline, scheduling is not feasible.
                    return new ArrayList<>();
                }
            }
        }
        
        // If not all jobs were scheduled, the schedule is not feasible.
        if (reqNum < m) {
            return new ArrayList<>();
        }
        return schedule;
    }

    // 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