Submission #705736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
705736	2023-03-05T04:13:26 Z	hex	Job Scheduling (CEOI12_jobs)	Java 11	50 / 100	1000 ms	53788 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	329 ms	16800 KB	Output is correct
2	Correct	329 ms	16888 KB	Output is correct
3	Correct	332 ms	16716 KB	Output is correct
4	Correct	336 ms	16712 KB	Output is correct
5	Correct	336 ms	16924 KB	Output is correct
6	Correct	328 ms	16864 KB	Output is correct
7	Correct	328 ms	16644 KB	Output is correct
8	Correct	334 ms	16612 KB	Output is correct
9	Correct	979 ms	18008 KB	Output is correct
10	Execution timed out	1052 ms	18040 KB	Time limit exceeded
11	Correct	945 ms	18040 KB	Output is correct
12	Execution timed out	1084 ms	23020 KB	Time limit exceeded
13	Execution timed out	1081 ms	25488 KB	Time limit exceeded
14	Execution timed out	1075 ms	31080 KB	Time limit exceeded
15	Execution timed out	1083 ms	36436 KB	Time limit exceeded
16	Execution timed out	1091 ms	41624 KB	Time limit exceeded
17	Execution timed out	1080 ms	44100 KB	Time limit exceeded
18	Execution timed out	1090 ms	46300 KB	Time limit exceeded
19	Execution timed out	1090 ms	53788 KB	Time limit exceeded
20	Execution timed out	1073 ms	44440 KB	Time limit exceeded