oj.uz

답안 #508893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
508893 2022-01-14T01:01:17 Z williamli Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 1000 ms 65540 KB 
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

# 결과 실행 시간 메모리 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