Submission #705731

#	Time	Username	Problem	Language	Result	Execution time	Memory
705731		hex	Job Scheduling (CEOI12_jobs)	Java	45 / 100	1084 ms	53676 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 - delay;
		for (int r = 0; r < reqs.length; r += numMachine) {
			if (reqs[r].day < day) return false;
			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());
		for (int r = 0; r < numReq; r++) {
			reqs[r] = new Req(Integer.parseInt(st.nextToken()) + delay, r + 1);
		}
		Arrays.sort(reqs);

		int lt = 1;
		int rt = numReq;
		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 <= days; d++) {
			out.println(0);
		}
		/*
		for (int d = 1; d < reqs[0].day - delay; d++) {
			out.println(0);
		}
		int r = 0;
		for (int d = reqs[0].day - delay; d <= days; d++) {
			int num = 0;
			while (r < reqs.length && num < lt) {
				out.print(reqs[r].id + " ");
				r++;
				num++;
			}
			out.println(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: 45 / 100