oj.uz

Submission #461358

# Submission time Handle Problem Language Result Execution time Memory
461358 2021-08-10T00:16:01 Z ryankim0709 Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 1000 ms 65540 KB 
import java.util.*;
import java.io.*;

/* Test case simulation:
 * 8 2 12
 * 1 2 4 2 1 3 5 6 2 3 6 4
 * ----------------------- Sort Array
 * 1 1 2 2 2 3 3 4 4 5 6 6
 * ----------------------- Binary through possible min machines
 * 
 */
public class jobs {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int days = Integer.parseInt(st.nextToken());
		int maxDelay = Integer.parseInt(st.nextToken());
		int reqs = Integer.parseInt(st.nextToken());
		
		int[] requests = new int[reqs];
		int[] sortReqs = new int[reqs];
		HashMap<Integer,Integer> pos = new HashMap<>();
		
		st = new StringTokenizer(br.readLine());
		for(int x = 0; x < reqs; x++) {
			requests[x] = Integer.parseInt(st.nextToken());
			sortReqs[x] = requests[x];
			pos.put(x + 1, requests[x]);
		}
		Arrays.sort(sortReqs);
		
		int min = 1;
		int max = reqs;
		int mid;
		
		while(min < max) {
			mid = min + (max - min)/2;
			
			if(doesWork(sortReqs, maxDelay, mid, days)) {
				max = mid;
			}
			else {
				min = mid + 1;
			}
		}
		System.out.println(min);
	}
	
	public static boolean doesWork(int[] sortReqs, int maxDelay, int machines, int days) {
		int left = 0;
		int count = 0;
		for(int x = 0; x < days; x++) {
			for(int y = 0;  y < machines; y++) {
				if(sortReqs[left + y] - maxDelay > 0) {
					left = left + y - 1;
					break;
				}
				else {
					count ++;
				}
			}
		}
		if(count < sortReqs.length - 1) {
			return false;
		}
		return true;
	}
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 333 ms 21500 KB Execution failed because the return code was nonzero
2 Runtime error 334 ms 21420 KB Execution failed because the return code was nonzero
3 Runtime error 344 ms 21136 KB Execution failed because the return code was nonzero
4 Runtime error 342 ms 21196 KB Execution failed because the return code was nonzero
5 Runtime error 339 ms 21140 KB Execution failed because the return code was nonzero
6 Runtime error 337 ms 21196 KB Execution failed because the return code was nonzero
7 Runtime error 338 ms 21428 KB Execution failed because the return code was nonzero
8 Runtime error 325 ms 21348 KB Execution failed because the return code was nonzero
9 Execution timed out 1077 ms 27508 KB Time limit exceeded
10 Execution timed out 1087 ms 29816 KB Time limit exceeded
11 Runtime error 626 ms 33004 KB Memory limit exceeded
12 Runtime error 676 ms 44520 KB Memory limit exceeded
13 Runtime error 768 ms 53136 KB Memory limit exceeded
14 Runtime error 818 ms 62216 KB Memory limit exceeded
15 Runtime error 628 ms 65540 KB Execution killed with signal 9
16 Runtime error 517 ms 65540 KB Execution killed with signal 9
17 Runtime error 518 ms 65540 KB Execution killed with signal 9
18 Runtime error 527 ms 65540 KB Execution killed with signal 9
19 Runtime error 541 ms 65540 KB Execution killed with signal 9
20 Runtime error 531 ms 65536 KB Execution killed with signal 9