Submission #508893

#	Time	Username	Problem	Language	Result	Execution time	Memory
508893		williamli	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1098 ms	65540 KiB

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