Submission #265454

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
265454	2020-08-14T21:10:16 Z	R3KT	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65552 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("JobScheduling"));

		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) {
		
		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	1029 ms	52952 KB	Time limit exceeded
2	Execution timed out	1071 ms	51924 KB	Time limit exceeded
3	Execution timed out	1034 ms	52172 KB	Time limit exceeded
4	Execution timed out	1061 ms	51984 KB	Time limit exceeded
5	Execution timed out	1025 ms	51400 KB	Time limit exceeded
6	Execution timed out	1037 ms	50004 KB	Time limit exceeded
7	Execution timed out	1069 ms	51964 KB	Time limit exceeded
8	Runtime error	965 ms	48116 KB	Memory limit exceeded
9	Execution timed out	1074 ms	48892 KB	Time limit exceeded
10	Execution timed out	1250 ms	54940 KB	Time limit exceeded
11	Execution timed out	1280 ms	47216 KB	Time limit exceeded
12	Execution timed out	1178 ms	55172 KB	Time limit exceeded
13	Execution timed out	1020 ms	58548 KB	Time limit exceeded
14	Execution timed out	1330 ms	60088 KB	Time limit exceeded
15	Runtime error	484 ms	65544 KB	Execution killed with signal 9
16	Runtime error	620 ms	65540 KB	Execution killed with signal 9
17	Runtime error	572 ms	65552 KB	Execution killed with signal 9
18	Runtime error	569 ms	65544 KB	Execution killed with signal 9
19	Runtime error	526 ms	65552 KB	Execution killed with signal 9
20	Runtime error	556 ms	65552 KB	Execution killed with signal 9