Submission #1183006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183006		eysbutno	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1101 ms	119872 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();
        
        int[][] jobs = new int[m][2];
        for (int i = 0; i < m; i++) {
            int day = io.nextInt();
            jobs[i] = new int[]{day, i + 1}; // {request date, index[1...m]}
        }

		/*
		 * we sort the jobs by the request date in ascending order
		 * so that we can test them using isFeasible() in linear time whether they
		 * can be done in given time using a certain amount of machines
		 */
		Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));
        
        int lo = 1, hi = m;
        while (lo < hi) {
            int machineNum = (lo + hi) / 2;
            
			/* 
			 * if it's possible, we set the right bound as the tested 
			 * machine number and save the current schedule
			 */
            if (isFeasible(n, d, m, machineNum, jobs)) {
                hi = machineNum;
            } else {
				/* 
				 * otherwise, we set the left bound to be the tested number + 1
				 * and test the next machine_num again
				 */
                lo = machineNum + 1;
            }
        }

        List<Integer>[] result = constructSchedule(n, d, m, lo, jobs);

		io.println(lo);
        for (List<Integer> daySchedule : result) {
            for (int idx : daySchedule) {
                io.print(idx + " ");
            }
            io.println(0);
        }

		io.close();
	}

    private static List<Integer>[] constructSchedule(int n, int d, int m, int machineCount, int[][] jobs) {
		// Create an array of ArrayLists using casting.
		@SuppressWarnings("unchecked")
		List<Integer>[] schedule = (List<Integer>[]) new ArrayList[n];
		for (int i = 0; i < n; i++) {
			schedule[i] = new ArrayList<>();
		}
		
		int reqNum = 0;
		
		// Simulate days from 1 to n.
		for (int day = 1; day <= n; day++) {
			for (int j = 0; j < machineCount; j++) {
				// If no job is available or the next job's request date is later than the current day, move to the next day.
				if (reqNum >= m || jobs[reqNum][0] > day) {
					break;
				}
				
				// Check if the job is still within the deadline (job request day + d >= current day).
				if (jobs[reqNum][0] + d >= day) {
					schedule[day - 1].add(jobs[reqNum][1]);
					reqNum++;
				} else {
					// If the deadline is missed, return an empty array (or handle infeasibility as needed).
					@SuppressWarnings("unchecked")
					List<Integer>[] emptySchedule = (List<Integer>[]) new ArrayList[0];
					return emptySchedule;
				}
				
				// If all jobs have been processed, return the schedule.
				if (reqNum == m) {
					return schedule;
				}
			}
		}
		
		// If not all requests can be scheduled within the given days, return an empty schedule.
		@SuppressWarnings("unchecked")
		List<Integer>[] emptySchedule = (List<Integer>[]) new ArrayList[0];
		return emptySchedule;
	}
	

	/** @return true along with schedule if it feasible to finish the jobs otherwise false */
	private static boolean isFeasible(int n, int d, int m, int machineCount, int[][] jobs) {
        int reqNum = 0;
        
		/*
		 * we simulate from day 1 until the last day n
		 * we move to the next day if all the machines are used or
		 * there is no more job requests left on or before this day
		 */
        for (int day = 1; day <= n; day++) {
            for (int j = 0; j < machineCount; j++) {

				/*
				 * if all jobs before and on this day are finished,
				 * we can go to the next day, even if there are usable machines left
				 * we can determine that since the vector jobs is sorted
				 */
                if (reqNum >= m || jobs[reqNum][0] > day) {
                    break;
                }
                
				/*
				 * if the current date is before the deadline for the job
				 * we can add this job to the schedule and move to the next
				 * job request
				 */
                if (jobs[reqNum][0] + d < day) {
                    return false;
				}

                reqNum++;
                
				/*
				 * if we have processed all the requests, we have found a 
				 * feasible solution
				 */
                if (reqNum == m) {
                    return true;
                }
            }
        }
        
		/*
		 * if not all the requests can be processed within the given n days,
		 * then it is not feasible
		 */
		return false;
    }

	// CodeSnip{Kattio}

	static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st;
		// standard input
		public Kattio() { this(System.in, System.out); }
		public Kattio(InputStream i, OutputStream o) {
			super(o);
			r = new BufferedReader(new InputStreamReader(i));
		}
		// USACO-style file input
		public Kattio(String problemName) throws IOException {
			super(problemName + ".out");
			r = new BufferedReader(new FileReader(problemName + ".in"));
		}
		// returns null if no more input
		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