Submission #401910

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401910	2021-05-11T01:20:53 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 = 0;
        int high = n;
        while (low < high){
            int mid = (low + high)/2;
            if (check(mid, arr)){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        ArrayList<Integer>[] eachDay = new ArrayList[n];
        for (int i=0; i<n; i++){
            eachDay[i] = new ArrayList<>();
        }
        int[] daycount = new int[low];
        for (int i=0; i<m; i++){
            eachDay[daycount[i%low]].add(arr[i][1]);
            daycount[i%low]++;
        }
        System.out.println(low);
        for (int i=0; i<n; i++){
            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;
        for (int i=0; i<m; i++){
            if (index == mid){
                index = 0;
            }
            if (end[index]-arr[i][0]+1 > d){
                return false;
            }
            end[index]++;
            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	1089 ms	22072 KB	Time limit exceeded
2	Execution timed out	1085 ms	21792 KB	Time limit exceeded
3	Execution timed out	1091 ms	21876 KB	Time limit exceeded
4	Execution timed out	1091 ms	21704 KB	Time limit exceeded
5	Execution timed out	1094 ms	21788 KB	Time limit exceeded
6	Execution timed out	1079 ms	21760 KB	Time limit exceeded
7	Execution timed out	1085 ms	21608 KB	Time limit exceeded
8	Execution timed out	1092 ms	21948 KB	Time limit exceeded
9	Execution timed out	1094 ms	21468 KB	Time limit exceeded
10	Execution timed out	1086 ms	21680 KB	Time limit exceeded
11	Execution timed out	1072 ms	21528 KB	Time limit exceeded
12	Execution timed out	1084 ms	29348 KB	Time limit exceeded
13	Execution timed out	1094 ms	40076 KB	Time limit exceeded
14	Execution timed out	1093 ms	47508 KB	Time limit exceeded
15	Execution timed out	1092 ms	50936 KB	Time limit exceeded
16	Execution timed out	1075 ms	56548 KB	Time limit exceeded
17	Runtime error	687 ms	65536 KB	Execution killed with signal 9
18	Runtime error	525 ms	65540 KB	Execution killed with signal 9
19	Runtime error	554 ms	65540 KB	Execution killed with signal 9
20	Runtime error	657 ms	65536 KB	Execution killed with signal 9