Submission #265452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
265452	2020-08-14T21:03:04 Z	R3KT	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65556 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-d) {
			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++;
		}
		
		for (int i=0; i<2; i++) {
			int curleft = num;
			while (cur.size() > 0 && curleft >0) {
				int k = cur.firstKey();
				if (pointer - k > d) return false;
				if (k <= curleft) {
					curleft -= k;
					cur.remove(k);
				}
				else {
					cur.put(k, cur.get(k)-curleft);
					curleft=0;
				}
			}
		}
		
		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	47908 KB	Time limit exceeded
2	Execution timed out	1025 ms	48452 KB	Time limit exceeded
3	Execution timed out	1033 ms	54568 KB	Time limit exceeded
4	Execution timed out	1026 ms	51624 KB	Time limit exceeded
5	Execution timed out	1029 ms	49544 KB	Time limit exceeded
6	Execution timed out	1030 ms	48800 KB	Time limit exceeded
7	Execution timed out	1070 ms	54184 KB	Time limit exceeded
8	Execution timed out	1102 ms	52856 KB	Time limit exceeded
9	Execution timed out	1240 ms	53504 KB	Time limit exceeded
10	Execution timed out	1152 ms	54588 KB	Time limit exceeded
11	Execution timed out	1285 ms	48320 KB	Time limit exceeded
12	Execution timed out	1097 ms	52948 KB	Time limit exceeded
13	Execution timed out	1048 ms	60484 KB	Time limit exceeded
14	Execution timed out	1489 ms	63336 KB	Time limit exceeded
15	Runtime error	516 ms	65556 KB	Execution killed with signal 9
16	Runtime error	556 ms	65556 KB	Execution killed with signal 9
17	Runtime error	523 ms	65548 KB	Execution killed with signal 9
18	Runtime error	498 ms	65552 KB	Execution killed with signal 9
19	Runtime error	488 ms	65544 KB	Execution killed with signal 9
20	Runtime error	544 ms	65552 KB	Execution killed with signal 9