oj.uz

답안 #401924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401924 2021-05-11T02:24:05 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 = 1;
        int high = m;
        while (low < high){
            int mid = (low + high)/2;
            if (check(mid, arr)){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        System.out.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]){
                    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;
        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;
    }
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 327 ms 19640 KB Unexpected end of file - int32 expected
2 Incorrect 360 ms 19912 KB Unexpected end of file - int32 expected
3 Incorrect 340 ms 19844 KB Unexpected end of file - int32 expected
4 Incorrect 337 ms 19856 KB Unexpected end of file - int32 expected
5 Incorrect 337 ms 19868 KB Unexpected end of file - int32 expected
6 Incorrect 339 ms 19460 KB Unexpected end of file - int32 expected
7 Incorrect 351 ms 19808 KB Unexpected end of file - int32 expected
8 Incorrect 327 ms 19836 KB Unexpected end of file - int32 expected
9 Execution timed out 1090 ms 21632 KB Time limit exceeded
10 Execution timed out 1088 ms 21864 KB Time limit exceeded
11 Execution timed out 1098 ms 21140 KB Time limit exceeded
12 Execution timed out 1088 ms 29080 KB Time limit exceeded
13 Execution timed out 1085 ms 40304 KB Time limit exceeded
14 Execution timed out 1095 ms 47636 KB Time limit exceeded
15 Execution timed out 1102 ms 51456 KB Time limit exceeded
16 Execution timed out 1089 ms 57048 KB Time limit exceeded
17 Runtime error 654 ms 65540 KB Execution killed with signal 9
18 Runtime error 523 ms 65540 KB Execution killed with signal 9
19 Runtime error 546 ms 65540 KB Execution killed with signal 9
20 Runtime error 654 ms 65536 KB Execution killed with signal 9