Submission #448360

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448360	2021-07-29T20:16:32 Z	Vishnu	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	186 ms	12352 KB

jobs

import java.io.IOException;
import java.io.File;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
 
 
class Main {
 
	public static void main(String[] args) throws IOException {
		Scanner myObj = new Scanner(System.in);
		int n = myObj.nextInt();
		int d = myObj.nextInt();
		int m = myObj.nextInt();
 
		int [][] arr = new int [m][2];
		for (int index = 0; index < m; index++) {
			arr[index][0] = myObj.nextInt();
			arr[index][1] = index + 1;
		}
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				Integer pos1 = o1[0];
				Integer pos2 = o2[0];
						
				if (pos1 > pos2) return 1;
				else if (pos1 == pos2) return 0;
				else return -1;
			}
		});
		
//		for (int index = 0; index < m; index++) {
//			System.out.println("Request: " + arr[index][0]);
//			System.out.println("Index: " + arr[index][1]);
//		}
		
		int a = 1;
		int b = m;
		int mid;
		while (a != b) {
			mid = (a+b)/2;
			if (works(mid, m, arr, d)) {
				b = mid;
			}
			else {
				a = mid + 1;
			}
		}
		System.out.println(a);
		
		
		String output = "";
		int [] mach = new int [a];
		int machine = 0;
		for (int index = 0; index < m; index++) {
			mach[machine] += 1;
			output = output + String.valueOf(arr[index][1]);
			machine++;
			output = output + " ";
			if (machine == a) {
				Arrays.sort(mach);
				machine = 0;
				output = output + "0\n";
			}
		}
		
		int needFinish = n - (m/a);
		for (int index = 0; index < needFinish; index++) {
			output = output + "0\n";
		}
		System.out.println(output);
	}
 
	public static boolean works (int mid, int m, int [][] request_arr, int allowDelay) {		
		int [] mach = new int [mid];
		int delay = 0;
		int machine = 0;
		for (int index = 0; index < m; index++) {
			mach[machine] += 1;
			delay = mach[machine] - request_arr[index][0];
			if (delay > allowDelay) {
				return false;
			}
			machine++;
			if (machine == mid) {
				Arrays.sort(mach);
				machine = 0;
			}
		}
		return true;
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	159 ms	12300 KB	Execution failed because the return code was nonzero
2	Runtime error	159 ms	12108 KB	Execution failed because the return code was nonzero
3	Runtime error	163 ms	12324 KB	Execution failed because the return code was nonzero
4	Runtime error	156 ms	12108 KB	Execution failed because the return code was nonzero
5	Runtime error	159 ms	12352 KB	Execution failed because the return code was nonzero
6	Runtime error	155 ms	12312 KB	Execution failed because the return code was nonzero
7	Runtime error	159 ms	12092 KB	Execution failed because the return code was nonzero
8	Runtime error	155 ms	11932 KB	Execution failed because the return code was nonzero
9	Runtime error	186 ms	12180 KB	Execution failed because the return code was nonzero
10	Runtime error	157 ms	12060 KB	Execution failed because the return code was nonzero
11	Runtime error	160 ms	12192 KB	Execution failed because the return code was nonzero
12	Runtime error	159 ms	11988 KB	Execution failed because the return code was nonzero
13	Runtime error	155 ms	12192 KB	Execution failed because the return code was nonzero
14	Runtime error	156 ms	12248 KB	Execution failed because the return code was nonzero
15	Runtime error	159 ms	11820 KB	Execution failed because the return code was nonzero
16	Runtime error	157 ms	12036 KB	Execution failed because the return code was nonzero
17	Runtime error	156 ms	12236 KB	Execution failed because the return code was nonzero
18	Runtime error	157 ms	12188 KB	Execution failed because the return code was nonzero
19	Runtime error	158 ms	12328 KB	Execution failed because the return code was nonzero
20	Runtime error	160 ms	12120 KB	Execution failed because the return code was nonzero