Submission #666552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
666552	2022-11-29T02:29:14 Z	bruhgamer	Job Scheduling (CEOI12_jobs)	Java 11	40 / 100	1000 ms	53956 KB

jobs

import java.util.*;
import java.io.*;
public class jobs {
	public static int n;
	public static int d;
	public static Edge[]arr;
	public static int ans = 0;
	static class Edge implements Comparable<Edge> {
		int pos, val;
		public Edge(int _a, int _b) { pos = _a; val = _b;  }
		public int compareTo(Edge y) { return Integer.compare(val,y.val); }
	}
	public static void search(int start, int end) {
		if(start == end) {
			ans = start;
			return;
		}
		int mid = (start + end - 1)/2;
		if(works(mid)) {
			search(start, mid);
		}
		else {
			search(mid+1, end);
		}
	}
	public static boolean works(int machines) {
		int arrpos = 0;
		for(int i = 1; i <= n; i++) {
			int machinesused = 0;
			while(arrpos < arr.length && arr[arrpos].val <= i && machinesused < machines) {
				if(i - arr[arrpos].val > d) {
					return false;
				}
				machinesused++;
				arrpos++;
			}
			if(arrpos == arr.length) {
				break;
			}
		}
		if(arrpos < arr.length) {
			return false;
		}
		return true;
	}
	public static void main(String[]args) throws IOException{
		Kattio io = new Kattio();
		n = io.nextInt();
		d = io.nextInt();
		int m = io.nextInt();
		arr = new Edge[m];
		for(int i = 0; i < m; i++) {
			arr[i] = new Edge(i+1, io.nextInt());
		}
		Arrays.sort(arr);
		search(0, m);
		int arrpos = 0;
		io.println(ans);
		for(int i = 1; i <= n; i++) {
			int machinesused = 0;
			while(arrpos < arr.length && arr[arrpos].val <= i && machinesused < ans) {
				io.print(arr[arrpos].pos + " ");
				machinesused++;
				arrpos++;
			}
			io.println("0");
		}
		io.close();
	}
	static 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()); }
	}
		
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	493 ms	19004 KB	Output is correct
2	Correct	471 ms	19016 KB	Output is correct
3	Correct	500 ms	18856 KB	Output is correct
4	Correct	482 ms	19288 KB	Output is correct
5	Correct	484 ms	19132 KB	Output is correct
6	Correct	480 ms	18920 KB	Output is correct
7	Correct	499 ms	19092 KB	Output is correct
8	Correct	491 ms	18940 KB	Output is correct
9	Execution timed out	1087 ms	18064 KB	Time limit exceeded
10	Execution timed out	1096 ms	18028 KB	Time limit exceeded
11	Execution timed out	1088 ms	19168 KB	Time limit exceeded
12	Execution timed out	1089 ms	21420 KB	Time limit exceeded
13	Execution timed out	1092 ms	26220 KB	Time limit exceeded
14	Execution timed out	1090 ms	31084 KB	Time limit exceeded
15	Execution timed out	1087 ms	35880 KB	Time limit exceeded
16	Execution timed out	1078 ms	41704 KB	Time limit exceeded
17	Execution timed out	1088 ms	44252 KB	Time limit exceeded
18	Execution timed out	1089 ms	46060 KB	Time limit exceeded
19	Execution timed out	1091 ms	53956 KB	Time limit exceeded
20	Execution timed out	1090 ms	44268 KB	Time limit exceeded