제출 #705717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705717		hex	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1082 ms	53416 KiB

jobs

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

public class jobs {
	static Req[] reqs;

	static class Req implements Comparable<Req> {
		int day;
		int id;

		public Req (int day, int id) {
			this.day = day;
			this.id = id;
		}
		
		public int compareTo (Req r) {
			//Comparing by id is not needed here.
			return Integer.compare(this.day, r.day);
		}
	}
	//Check if changing reqs to a static array will be fater
	static boolean valid (int numMachine, int delay) {
		int day = reqs[0].day;
		int r = 0;
		PriorityQueue<Integer> res = new PriorityQueue<Integer>();
		while (r < reqs.length) {
			int num = 0;
			while (res.size() > 0 && num < numMachine) {
				if (res.peek() + delay < day) return false;
				res.poll();
				num++;
			}
			num = 0;
			while (r < reqs.length && num < numMachine) {
				res.add(reqs[r].day);
				r++;
				num++;
			}
			day++;
		}
		return true;
	}

	public static void main (String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(reader.readLine());
		int days = Integer.parseInt(st.nextToken());
		int delay = Integer.parseInt(st.nextToken());
		int numReq = Integer.parseInt(st.nextToken());
		reqs = new Req[numReq];
	 	st = new StringTokenizer(reader.readLine());
		Set<Integer> diffs = new HashSet<Integer>();
		for (int r = 0; r < numReq; r++) {
			reqs[r] = new Req(Integer.parseInt(st.nextToken()), r + 1);
			diffs.add(reqs[r].day);
		}
		Arrays.sort(reqs);

		int lt = 1;
		int rt = (int) 10e6;
		int mid;
		while (lt < rt) {
			mid = (lt + rt) / 2;
			if (valid(mid, delay)) {
				rt = mid;
			} else {
				lt = mid + 1;
			}
		}

		//At the end, just loop through reqs in sorted order and print out lt ids in a single line, followed by a 0
		
		out.println(lt);
		for (int d = 1; d < reqs[0].day; d++) {
			out.println(0);
		}
		int r = 0;
		for (int d = 0; d < days; d++) {
			int num = 0;
			while (r < reqs.length && num < lt) {
				out.print(reqs[r].id + " ");
				r++;
				num++;
			}
			out.print("0");
			out.println();
		}
		//out.println(valid(1, delay, reqs));
		out.close();
	}
}
//Check N = 1.
//Check for needed longs.
//Use Long.parseLong() instead of Integer.parseInt().
//Use Long.MAX_VALUE instead of Integer.MAX_VALUE.
//Use an int array of ids instead of a boolean array of visited nodes during DFS.
//Declare a class variable instead of a method parameter, as passing by value could result in a TLE.

• Subtask 1: 0 / 100