oj.uz

Submission #401915

# Submission time Handle Problem Language Result Execution time Memory
401915 2021-05-11T01:29:57 Z rainliofficial Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 1000 ms 65540 KB 
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]+1 > arr[i][0]){
                if (end[index]-arr[i][0]+1 > d){
                    return false;
                }
                end[index]++;
            }else{
                end[index] = arr[i][0]; // No delay
            }
            index++;
        }
        return true;
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 332 ms 19252 KB Unexpected end of file - int32 expected
2 Incorrect 317 ms 18960 KB Unexpected end of file - int32 expected
3 Incorrect 308 ms 19168 KB Unexpected end of file - int32 expected
4 Incorrect 363 ms 19140 KB Unexpected end of file - int32 expected
5 Incorrect 301 ms 19180 KB Unexpected end of file - int32 expected
6 Incorrect 304 ms 19164 KB Unexpected end of file - int32 expected
7 Incorrect 317 ms 19024 KB Unexpected end of file - int32 expected
8 Incorrect 301 ms 19184 KB Unexpected end of file - int32 expected
9 Execution timed out 1098 ms 21360 KB Time limit exceeded
10 Execution timed out 1095 ms 21740 KB Time limit exceeded
11 Execution timed out 1099 ms 21636 KB Time limit exceeded
12 Execution timed out 1086 ms 28836 KB Time limit exceeded
13 Execution timed out 1091 ms 40244 KB Time limit exceeded
14 Execution timed out 1092 ms 47440 KB Time limit exceeded
15 Execution timed out 1097 ms 51504 KB Time limit exceeded
16 Execution timed out 1089 ms 56872 KB Time limit exceeded
17 Runtime error 637 ms 65536 KB Execution killed with signal 9
18 Runtime error 514 ms 65540 KB Execution killed with signal 9
19 Runtime error 523 ms 65540 KB Execution killed with signal 9
20 Runtime error 643 ms 65540 KB Execution killed with signal 9