Submission #705736

#	Time	Username	Problem	Language	Result	Execution time	Memory
705736		hex	Job Scheduling (CEOI12_jobs)	Java	50 / 100	1091 ms	53788 KiB

jobs

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

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()); }
}

public class jobs {
	static Req[] reqs;
	static int numReq;
	static int delay;
 
	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 day = reqs[0].day - delay;
		for (int r = 0; r < numReq; r += numMachine) {
			if (reqs[r].day < day) return false;
			day++;
		}
		return true;
	}
 
	public static void main (String[] args) throws IOException {
		Kattio io = new Kattio();
		int days = io.nextInt();
		delay = io.nextInt();
		numReq = io.nextInt();
		reqs = new Req[numReq];
		for (int r = 0; r < numReq; r++) {
			reqs[r] = new Req(io.nextInt() + delay, r + 1);
		}
		Arrays.sort(reqs);
 
		int lt = 1;
		int rt = numReq + 1;
		int mid;
		while (lt < rt) {
			mid = (lt + rt) / 2;
			if (valid(mid)) {
				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
		
		io.println(lt);
		for (int d = 1; d <= days; d++) {
			io.println(0);
		}
		/*
		for (int d = 1; d < reqs[0].day - delay; d++) {
			io.println(0);
		}
		int r = 0;
		for (int d = reqs[0].day - delay; d <= days; d++) {
			int num = 0;
			while (r < reqs.length && num < lt) {
				io.print(reqs[r].id + " ");
				r++;
				num++;
			}
			io.println(0);
			//out.println();
		}
		//out.println(valid(1, delay, reqs));
		*/
		io.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: 50 / 100