Submission #401922

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401922	2021-05-11T02:09:41 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;
    }
}

Compilation message

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1095 ms	21724 KB	Time limit exceeded
2	Execution timed out	1093 ms	21664 KB	Time limit exceeded
3	Execution timed out	1097 ms	21672 KB	Time limit exceeded
4	Execution timed out	1091 ms	21592 KB	Time limit exceeded
5	Execution timed out	1092 ms	21548 KB	Time limit exceeded
6	Execution timed out	1099 ms	21784 KB	Time limit exceeded
7	Execution timed out	1058 ms	21504 KB	Time limit exceeded
8	Execution timed out	1097 ms	21700 KB	Time limit exceeded
9	Execution timed out	1098 ms	22076 KB	Time limit exceeded
10	Execution timed out	1101 ms	21620 KB	Time limit exceeded
11	Execution timed out	1092 ms	21804 KB	Time limit exceeded
12	Execution timed out	1101 ms	29276 KB	Time limit exceeded
13	Execution timed out	1098 ms	40484 KB	Time limit exceeded
14	Execution timed out	1104 ms	47856 KB	Time limit exceeded
15	Execution timed out	1100 ms	51344 KB	Time limit exceeded
16	Execution timed out	1099 ms	56936 KB	Time limit exceeded
17	Runtime error	651 ms	65540 KB	Execution killed with signal 9
18	Runtime error	516 ms	65540 KB	Execution killed with signal 9
19	Runtime error	539 ms	65536 KB	Execution killed with signal 9
20	Runtime error	607 ms	65540 KB	Execution killed with signal 9