Submission #401899

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401899	2021-05-11T00:54:24 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;
    static ArrayList<Integer>[] out;
    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 = 0;
        int high = n;
        while (low < high){
            int mid = (low + high)/2;
            if (check(mid, arr)){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        System.out.println(low);
        for (int i=0; i<n; i++){
            for (int j : out[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;
        out = new ArrayList[n];
        for (int i=0; i<n; i++){
            out[i] = new ArrayList<>();
        }
        for (int i=0; i<m; i++){
            if (index == mid){
                index = 0;
            }
            if (end[index]-arr[i][0]+1 > d){
                return false;
            }
            end[index]++;
            out[end[index]].add(arr[i][1]);
            index++;
        }
        return true;
    }
}

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	1096 ms	26000 KB	Time limit exceeded
2	Execution timed out	1067 ms	26044 KB	Time limit exceeded
3	Execution timed out	1082 ms	27664 KB	Time limit exceeded
4	Execution timed out	1089 ms	27548 KB	Time limit exceeded
5	Execution timed out	1092 ms	28652 KB	Time limit exceeded
6	Execution timed out	1087 ms	28628 KB	Time limit exceeded
7	Execution timed out	1091 ms	27472 KB	Time limit exceeded
8	Execution timed out	1080 ms	27524 KB	Time limit exceeded
9	Execution timed out	1098 ms	21408 KB	Time limit exceeded
10	Execution timed out	1086 ms	21596 KB	Time limit exceeded
11	Execution timed out	1088 ms	21624 KB	Time limit exceeded
12	Execution timed out	1095 ms	28716 KB	Time limit exceeded
13	Execution timed out	1098 ms	40180 KB	Time limit exceeded
14	Execution timed out	1091 ms	46800 KB	Time limit exceeded
15	Execution timed out	1099 ms	51472 KB	Time limit exceeded
16	Execution timed out	1091 ms	57000 KB	Time limit exceeded
17	Runtime error	705 ms	65536 KB	Execution killed with signal 9
18	Runtime error	514 ms	65540 KB	Execution killed with signal 9
19	Runtime error	541 ms	65540 KB	Execution killed with signal 9
20	Runtime error	678 ms	65536 KB	Execution killed with signal 9