Submission #508893

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
508893	2022-01-14T01:01:17 Z	williamli	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65540 KB

jobs

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

public class jobs {
	public static int n, d, m;
	public static PriorityQueue<Integer> jobs;
	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new FileReader(".in"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(".out")));
		PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
		String[] in = br.readLine().split(" ");
		n = Integer.parseInt(in[0]);
		d = Integer.parseInt(in[1]);
		m = Integer.parseInt(in[2]);
		jobs = new PriorityQueue<>();
		HashMap<Integer, ArrayList<Integer>> timeid = new HashMap<>();
		in = br.readLine().split(" ");
		for(int i = 0;i < m;i++) {
			int cur = Integer.parseInt(in[i]);
			jobs.add(cur);
			if(!timeid.containsKey(cur)) timeid.put(cur, new ArrayList<>());
			timeid.get(cur).add(i);
		}
		System.out.println(timeid);
		int a = 0, b = 1000000;
		while(a != b){
			int mid = (a + b) / 2;
			if(check(mid)) b = mid;
			else a = mid + 1;
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		System.out.println(a);
		pw.println(a);
		for(int i = 1;i <= n;i++){
			while(!jobs.isEmpty() && jobs.peek() == i) {
				pq.add(i + d);
				jobs.poll();
			}
			for(int j = 0;j < a;j++) {
				if(!pq.isEmpty()) {
					int cur = pq.poll() - d;
					System.out.print((timeid.get(cur).get(0) + 1) + " ");
					timeid.get(cur).remove(0);
				}
			}
			System.out.println(0);
		}

		pw.close();
	}
	public static boolean check(int test){
		PriorityQueue<Integer> pq = new PriorityQueue<>(), job2 = new PriorityQueue<>(jobs);
		for(int i = 0;i <= n;i++){
			if(job2.isEmpty() && pq.isEmpty()) return true;
			if(!pq.isEmpty() && pq.peek() < i) return false;
			while(!job2.isEmpty() && job2.peek() == i) {
				pq.add(i + d);
				job2.poll();
			}
			for(int j = 0;j < test;j++) if(!pq.isEmpty()) pq.poll();
		}
		return true;
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1070 ms	32824 KB	Time limit exceeded
2	Execution timed out	1096 ms	32464 KB	Time limit exceeded
3	Execution timed out	1054 ms	32580 KB	Time limit exceeded
4	Execution timed out	1060 ms	32596 KB	Time limit exceeded
5	Execution timed out	1027 ms	32500 KB	Time limit exceeded
6	Execution timed out	1075 ms	32552 KB	Time limit exceeded
7	Execution timed out	1016 ms	32496 KB	Time limit exceeded
8	Execution timed out	1036 ms	32644 KB	Time limit exceeded
9	Execution timed out	1010 ms	28208 KB	Time limit exceeded
10	Execution timed out	1074 ms	30452 KB	Time limit exceeded
11	Execution timed out	1068 ms	31748 KB	Time limit exceeded
12	Execution timed out	1054 ms	44976 KB	Time limit exceeded
13	Execution timed out	1098 ms	63760 KB	Time limit exceeded
14	Runtime error	615 ms	65536 KB	Execution killed with signal 9
15	Runtime error	452 ms	65536 KB	Execution killed with signal 9
16	Runtime error	423 ms	65536 KB	Execution killed with signal 9
17	Runtime error	578 ms	65540 KB	Execution killed with signal 9
18	Runtime error	461 ms	65540 KB	Execution killed with signal 9
19	Runtime error	363 ms	65540 KB	Execution killed with signal 9
20	Runtime error	578 ms	65540 KB	Execution killed with signal 9