Submission #401927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401927	2021-05-11T02:29:51 Z	rainliofficial	Job Scheduling (CEOI12_jobs)	Java 11	40 / 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));
        PrintWriter outfile = new PrintWriter (System.out);
        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;
            }
        }
        outfile.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]){
                    outfile.print(j + " ");
                }
            }
            outfile.print("0");
            outfile.println();
        }
        outfile.close();
    }
    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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	668 ms	22064 KB	Output is correct
2	Correct	670 ms	22108 KB	Output is correct
3	Correct	661 ms	22212 KB	Output is correct
4	Correct	661 ms	22040 KB	Output is correct
5	Correct	664 ms	21944 KB	Output is correct
6	Correct	670 ms	22016 KB	Output is correct
7	Correct	666 ms	22140 KB	Output is correct
8	Correct	655 ms	21864 KB	Output is correct
9	Execution timed out	1090 ms	21624 KB	Time limit exceeded
10	Execution timed out	1095 ms	21608 KB	Time limit exceeded
11	Execution timed out	1089 ms	21648 KB	Time limit exceeded
12	Execution timed out	1102 ms	29156 KB	Time limit exceeded
13	Execution timed out	1087 ms	40232 KB	Time limit exceeded
14	Execution timed out	1047 ms	47204 KB	Time limit exceeded
15	Execution timed out	1090 ms	51408 KB	Time limit exceeded
16	Execution timed out	1091 ms	57384 KB	Time limit exceeded
17	Runtime error	644 ms	65540 KB	Execution killed with signal 9
18	Runtime error	535 ms	65540 KB	Execution killed with signal 9
19	Runtime error	542 ms	65540 KB	Execution killed with signal 9
20	Runtime error	652 ms	65540 KB	Execution killed with signal 9