제출 #511467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511467		anjroo	Job Scheduling (CEOI12_jobs)	Java	40 / 100	1098 ms	49996 KiB

jobs

import java.util.*;
import java.io.*;
public class jobs {
	static Kattio io = new Kattio();
 
	static int numDays;
	static int delay;
	static int numReqs;
	static Request[] requests;
	static int[] reqCount;
 
	public static void main(String[] args) {
		numDays = io.nextInt();
		delay = io.nextInt();
		numReqs = io.nextInt();
 
		requests = new Request[numReqs];
		reqCount = new int[numDays + 1];
 
		for(int i = 0; i < numReqs; i++) {
			int day = io.nextInt();
			requests[i] = new Request(day, i + 1); // 1-indexed
		}
		Arrays.sort(requests);
 
		// count how many requests per day
		int reqPointer = 0;
		for(int i = 1; i <= numDays; i++) {
			while(reqPointer < numReqs && requests[reqPointer].day == i) {
				reqCount[i]++;
				reqPointer++;
			}
		}

		// binary search for smallest value that works
		int lo = 0;
		int hi = numReqs;
 
		while(lo < hi) {
			int mid = (hi + lo) / 2;
			if(machinesWork(mid)) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
 
		io.println(lo);
 
        // print the schedule for each day
		int requestsPointer = 0;

        for(int day = 1; day <= numDays; day++) {
            if(requestsPointer == numReqs) {
                io.println(0); // no more requests
                continue;
            }

            for(int i = 0; i < lo; i++) {
                if(requests[requestsPointer].day > day) {
                    break;
                }
                io.print(requests[requestsPointer++].id + " ");
            }
            io.println(0);
        }
 
		io.close();
	}
 
	static boolean machinesWork(int amt) {
		int fromPrev = 0;
 
		for(int i = 1; i <= numDays; i++) {
			if(amt * (delay + 1) < (reqCount[i] + fromPrev)) {
				return false;
			}
			fromPrev = Math.max(0, reqCount[i] + fromPrev - amt);
		}
 
		return true;
	}
 
	static class Request implements Comparable<Request> {
		int day;
		int id;
 
		public Request(int day, int id) {
			this.day = day;
			this.id = id;
		}
 
		public int compareTo(Request r) {
			return Integer.compare(day, r.day);
		}
	}
 
	static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st = new StringTokenizer("");
		private String token;
 
		// 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(new FileWriter(problemName+".out"));
			r = new BufferedReader(new FileReader(problemName+".in"));
		}
 
		private String peek() {
			if (token == null)
				try {
					while (!st.hasMoreTokens()) {
						String line = r.readLine();
						if (line == null) return null;
						st = new StringTokenizer(line);
					}
					token = st.nextToken();
				} catch (IOException e) { }
			return token;
		}
		public boolean hasMoreTokens() { return peek() != null; }
		public String next() {
			String ans = peek(); 
			token = null;
			return ans;
		}
		
		public int nextInt() { return Integer.parseInt(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
}

• Subtask 1: 40 / 100