제출 #507637

#제출 시각아이디문제언어결과실행 시간메모리
507637anjrooJob Scheduling (CEOI12_jobs)Java
0 / 100
1105 ms53232 KiB
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++;
			}
		}

		// io.println(machinesWork(3));/

		// binary search for smallest value that works
		int lo = 0;
		int hi = 1000000;

		while(lo < hi) {
			int mid = (hi + lo) / 2;
			if(machinesWork(mid)) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}

		io.println(lo);

		int requestsPointer = 0;
		int curDay = 1;

		while(requestsPointer < numReqs) {
			for(int i = 0; i < lo; i++) { // lo is max per day
				if(requestsPointer == numReqs || requests[requestsPointer].day > curDay) {
					// no more to do
					break;
				}
				io.print(requests[requestsPointer++].id + " ");
			}

			io.println(0);
			curDay++;
		}

		for(int i = curDay; i < numDays; i++) {
			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()); }
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...