Submission #265455

#	Time	Username	Problem	Language	Result	Execution time	Memory
265455		R3KT	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1516 ms	65548 KiB

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