Submission #401896

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401896	2021-05-11T00:51:08 Z	rainliofficial	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65536 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;
            }
        }
        check(low, arr);
        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	1083 ms	26992 KB	Time limit exceeded
2	Execution timed out	1095 ms	27364 KB	Time limit exceeded
3	Execution timed out	1093 ms	28320 KB	Time limit exceeded
4	Execution timed out	1087 ms	28136 KB	Time limit exceeded
5	Execution timed out	1091 ms	29296 KB	Time limit exceeded
6	Execution timed out	1090 ms	28944 KB	Time limit exceeded
7	Execution timed out	1081 ms	27840 KB	Time limit exceeded
8	Execution timed out	1093 ms	28228 KB	Time limit exceeded
9	Execution timed out	1077 ms	21808 KB	Time limit exceeded
10	Execution timed out	1087 ms	22164 KB	Time limit exceeded
11	Execution timed out	1093 ms	21988 KB	Time limit exceeded
12	Execution timed out	1085 ms	30280 KB	Time limit exceeded
13	Execution timed out	1020 ms	41272 KB	Time limit exceeded
14	Execution timed out	1097 ms	49660 KB	Time limit exceeded
15	Execution timed out	1078 ms	53280 KB	Time limit exceeded
16	Execution timed out	1071 ms	59848 KB	Time limit exceeded
17	Runtime error	672 ms	65536 KB	Execution killed with signal 9
18	Runtime error	535 ms	65536 KB	Execution killed with signal 9
19	Runtime error	556 ms	65536 KB	Execution killed with signal 9
20	Runtime error	669 ms	65536 KB	Execution killed with signal 9