Submission #401924

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401924	2021-05-11T02:24:05 Z	rainliofficial	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65540 KB

jobs

import java.io.*;
import java.util.*;

public class jobs { 
    static int n, d, m;
    public static void main(String[] args) throws IOException{
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(file.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[m][2];
        st = new StringTokenizer(file.readLine());
        for (int i=0; i<m; i++){
            arr[i] = new int[] {Integer.parseInt(st.nextToken()), i+1};
        }
        Arrays.sort(arr, (a, b) -> a[0]-b[0]);
        int low = 1;
        int high = m;
        while (low < high){
            int mid = (low + high)/2;
            if (check(mid, arr)){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        System.out.println(low);
        /*
        ArrayList<Integer>[] eachDay = new ArrayList[n+1];
        for (int i=0; i<=n; i++){
            eachDay[i] = new ArrayList<>();
        }
        int[] end = new int[low];
        for (int i=0, id = 0; i<m; i++, id++){
            if (id == low){
                id = 0;
            }
            int requestDay = arr[i][0];
            int canDo = end[id]+1;
            end[id] = Math.max(requestDay, canDo); // Only does work when the request comes
            eachDay[end[id]].add(arr[i][1]);
        }
        for (int i=1; i<=n; i++){
            if (eachDay[i] != null){
                for (int j : eachDay[i]){
                    System.out.print(j + " ");
                }
            }
            System.out.print("0");
            System.out.println();
        }*/
    }
    public static boolean check(int mid, int[][] arr){
        int[] end = new int[mid]; // Tracks when a machine ends its job
        int index = 0;
        int maxD = 0;
        for (int i=0; i<m; i++){
            if (index == mid){
                index = 0;
            }
            if (end[index]+1 > arr[i][0]){
                maxD = Math.max(maxD, end[index]+1-arr[i][0]);
                end[index]++;
            }else{
                end[index] = arr[i][0]; // No delay
            }
            index++;
        }
        return maxD <= d;
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	327 ms	19640 KB	Unexpected end of file - int32 expected
2	Incorrect	360 ms	19912 KB	Unexpected end of file - int32 expected
3	Incorrect	340 ms	19844 KB	Unexpected end of file - int32 expected
4	Incorrect	337 ms	19856 KB	Unexpected end of file - int32 expected
5	Incorrect	337 ms	19868 KB	Unexpected end of file - int32 expected
6	Incorrect	339 ms	19460 KB	Unexpected end of file - int32 expected
7	Incorrect	351 ms	19808 KB	Unexpected end of file - int32 expected
8	Incorrect	327 ms	19836 KB	Unexpected end of file - int32 expected
9	Execution timed out	1090 ms	21632 KB	Time limit exceeded
10	Execution timed out	1088 ms	21864 KB	Time limit exceeded
11	Execution timed out	1098 ms	21140 KB	Time limit exceeded
12	Execution timed out	1088 ms	29080 KB	Time limit exceeded
13	Execution timed out	1085 ms	40304 KB	Time limit exceeded
14	Execution timed out	1095 ms	47636 KB	Time limit exceeded
15	Execution timed out	1102 ms	51456 KB	Time limit exceeded
16	Execution timed out	1089 ms	57048 KB	Time limit exceeded
17	Runtime error	654 ms	65540 KB	Execution killed with signal 9
18	Runtime error	523 ms	65540 KB	Execution killed with signal 9
19	Runtime error	546 ms	65540 KB	Execution killed with signal 9
20	Runtime error	654 ms	65536 KB	Execution killed with signal 9