Submission #265455

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
265455	2020-08-14T21:14:44 Z	R3KT	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65548 KB

jobs

import java.util.*;
import java.io.*;

public class jobs {

	// https://oj.uz/problem/view/CEOI12_jobs
	
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader in = new BufferedReader(new FileReader("jobs"));

		StringTokenizer st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] arr = new int[m];
		HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
		st = new StringTokenizer(in.readLine());
		for (int i=0; i<m; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
			if (map.containsKey(arr[i])) {
				map.get(arr[i]).add(i+1);
			}
			else {
				ArrayList<Integer> c = new ArrayList<>();
				c.add(i+1);
				map.put(arr[i], c);
			}
		}
		Arrays.parallelSort(arr);
		
		int min=0;
		int max=m;
		while (min < max) {
			int middle = (min + max)/2;
			if (check(middle, n, d, map)) {
				max = middle;
			}
			else min = middle+1;
		}
		
		System.out.println(min);
		// construct
		int count=1;
		for (int i=0; i<m; i+=min) {
			for (int j=i; j<i+min; j++) {
				System.out.print(map.get(arr[j]).get(map.get(arr[j]).size()-1) + " ");
				map.get(arr[j]).remove(map.get(arr[j]).size()-1);
			}
			System.out.println(0);
			count++;
		}
		for (int i=count; i<=n; i++) System.out.println(0);
	}
	
	public static boolean check(int num, int n, int d, HashMap<Integer, ArrayList<Integer>> map) {
		
		ArrayDeque<int[]> de = new ArrayDeque<>();
		int pointer=1;
		while (pointer <= n) {
			if (map.containsKey(pointer)) {
				de.add(new int[] {pointer, map.get(pointer).size()});
			}
			else {
				
			}
			
			int curleft = num;
			while (de.size() > 0 && curleft >0) {
				int[] k = de.peek();
				if (pointer - k[0] > d) return false;
				if (k[1] <= curleft) {
					curleft -= k[1];
					de.poll();
				}
				else {
					k[1] = k[1]-curleft;
					curleft=0;
				}
			}
			pointer++;
		}
		
		if (de.size() > 0) return false;
		return true;
	}
}

/*

public static boolean check(int num, int n, int d, HashMap<Integer, ArrayList<Integer>> map) {

TreeMap<Integer, Integer> cur = new TreeMap<>();
int pointer=1;
while (pointer <= n) {
	if (map.containsKey(pointer)) {
		cur.put(pointer, map.get(pointer).size());
	}
	else {
		
	}
	
	int curleft = num;
	while (cur.size() > 0 && curleft >0) {
		int k = cur.firstKey();
		if (pointer - k > d) return false;
		if (cur.get(k) <= curleft) {
			curleft -= cur.get(k);
			cur.remove(k);
		}
		else {
			cur.put(k, cur.get(k)-curleft);
			curleft=0;
		}
	}
	pointer++;
}

if (cur.size() > 0) return false;
return true;
}

*/

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1037 ms	49956 KB	Time limit exceeded
2	Execution timed out	1067 ms	50628 KB	Time limit exceeded
3	Execution timed out	1014 ms	50284 KB	Time limit exceeded
4	Execution timed out	1113 ms	50696 KB	Time limit exceeded
5	Execution timed out	1072 ms	50980 KB	Time limit exceeded
6	Execution timed out	1012 ms	50404 KB	Time limit exceeded
7	Execution timed out	1078 ms	50964 KB	Time limit exceeded
8	Execution timed out	1072 ms	52236 KB	Time limit exceeded
9	Execution timed out	1072 ms	49636 KB	Time limit exceeded
10	Execution timed out	1099 ms	52584 KB	Time limit exceeded
11	Execution timed out	1331 ms	47028 KB	Time limit exceeded
12	Execution timed out	1320 ms	55408 KB	Time limit exceeded
13	Execution timed out	1516 ms	59856 KB	Time limit exceeded
14	Execution timed out	1111 ms	59052 KB	Time limit exceeded
15	Runtime error	473 ms	65540 KB	Execution killed with signal 9
16	Runtime error	553 ms	65540 KB	Execution killed with signal 9
17	Runtime error	540 ms	65540 KB	Execution killed with signal 9
18	Runtime error	472 ms	65536 KB	Execution killed with signal 9
19	Runtime error	493 ms	65548 KB	Execution killed with signal 9
20	Runtime error	581 ms	65548 KB	Execution killed with signal 9