oj.uz

Submission #498622

# Submission time Handle Problem Language Result Execution time Memory
498622 2021-12-25T20:50:02 Z sohomdutta Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 171 ms 12448 KB 
import java.util.*;
class jobschedule {
    static int n, d, m;
    static int [] requests;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        d = sc.nextInt();
        m = sc.nextInt();
        requests = new int[m];
        for(int i = 0; i < m; i++){
            requests[i]=sc.nextInt();
        }
        Arrays.sort(requests);

        //System.out.println(Arrays.toString(requests));
        int left = 1;
        int right = m;
        while(left!=right){
            int mid = left + (right-left)/2;
            if(works(mid)){
                right=mid;
            }else{
                left=mid+1;
            }
        }

        System.out.println(left);
    }
    public static boolean works(int machines){
        int [] timeArray = new int[m];
        int time = 1;
        timeArray[0]=1;
        int currentMachines = machines-1;
        for(int i = 1; i < m; i++){
            if(requests[i]==requests[i-1]){
                if(currentMachines==0){
                    currentMachines=machines-1;
                    time++;
                    timeArray[i]=time;
                }else{
                    currentMachines--;
                    timeArray[i]=time;
                }
            }else{
                time=Math.max(time+1, requests[i]);
                timeArray[i]=time;
                currentMachines=machines-1;
            }
        }
        for(int i = 0; i < m; i++){
            if(timeArray[i]-requests[i]>d){
                return false;
            }
        }
        return true;
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 12448 KB Execution failed because the return code was nonzero
2 Runtime error 160 ms 12064 KB Execution failed because the return code was nonzero
3 Runtime error 168 ms 11940 KB Execution failed because the return code was nonzero
4 Runtime error 138 ms 12056 KB Execution failed because the return code was nonzero
5 Runtime error 141 ms 12036 KB Execution failed because the return code was nonzero
6 Runtime error 171 ms 11904 KB Execution failed because the return code was nonzero
7 Runtime error 145 ms 12048 KB Execution failed because the return code was nonzero
8 Runtime error 135 ms 12088 KB Execution failed because the return code was nonzero
9 Runtime error 136 ms 11896 KB Execution failed because the return code was nonzero
10 Runtime error 158 ms 11972 KB Execution failed because the return code was nonzero
11 Runtime error 138 ms 12012 KB Execution failed because the return code was nonzero
12 Runtime error 132 ms 12104 KB Execution failed because the return code was nonzero
13 Runtime error 158 ms 12168 KB Execution failed because the return code was nonzero
14 Runtime error 168 ms 11976 KB Execution failed because the return code was nonzero
15 Runtime error 144 ms 12044 KB Execution failed because the return code was nonzero
16 Runtime error 133 ms 12100 KB Execution failed because the return code was nonzero
17 Runtime error 138 ms 11924 KB Execution failed because the return code was nonzero
18 Runtime error 163 ms 11936 KB Execution failed because the return code was nonzero
19 Runtime error 139 ms 12256 KB Execution failed because the return code was nonzero
20 Runtime error 133 ms 12248 KB Execution failed because the return code was nonzero