Submission #1183004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183004		eysbutno	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1099 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();
        
        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<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<List<Integer>> constructSchedule(int n, int d, int m, int machineCount, int[][] jobs) {
        List<List<Integer>> schedule = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            schedule.add(new ArrayList<>());
        }
        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) {
                    schedule.get(day - 1).add(jobs[reqNum++][1]);
				} else { // otherwise, it is not feasible due to deadline
					return new ArrayList<>();
                }
                
				/*
				 * if we have processed all the requests, we have found a 
				 * feasible solution
				 */
                if (reqNum == m) {
                    return schedule;
                }
            }
        }
        
		/*
		 * if not all the requests can be processed within the given n days,
		 * then it is not feasible
		 */
		return new ArrayList<>();
    }

	/** @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) {
        List<List<Integer>> schedule = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            schedule.add(new ArrayList<>());
        }
        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