Submission #875567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
875567	2023-11-20T04:15:10 Z	rajat	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	107 ms	31852 KB

jobs

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Val[] arr = new Val[m];
        HashMap<Integer, Integer> switchArr = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            arr[i] = new Val(num, i + 1);
        }
        Arrays.sort(arr, Comparator.comparingInt(s -> s.num));
        int curValue = 1;
        for (int i = 1; i < m; i++) {
            if (arr[i] != arr[i - 1]) {
                switchArr.put(curValue, i);
                curValue = arr[i].num;
            }
        }
        switchArr.put(arr[m - 1].num, m);
        int low = 1;
        int high = m;
        while (low <= high) {
            int mid = (low + high + 1)/2;
            if (works(mid, n, arr, d, switchArr)) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        StringBuilder str = new StringBuilder();
        str.append(low);
        str.append("\n");
        int arrInd = 0;
        for (int i = 1; i <= n; i++) {
            if (arrInd >= arr.length || arr[arrInd].num > i ) {
                str.append(0);
                str.append("\n");
                continue;
            }
            int prevStart = arrInd;
            int posCurJob = arrInd + low;
            arrInd = posCurJob;
            if (switchArr.containsKey(i)) {
                arrInd = Math.min(posCurJob, switchArr.get(i));
            }
            int end = Math.min(m, arrInd);
            for (int j = prevStart; j < end; j++) {
                str.append(arr[j].ind + " ");
            }
            str.append(0);
            str.append("\n");
        }
        System.out.println(str);
        br.close();
    }

    public static boolean works(int mid, int n, Val[] arr, int d, HashMap<Integer, Integer> switchArr) {
        int arrInd = 0;
        for (int i = 1; i <= n; i++) {
            int curJob = arr[arrInd].num;
            if (curJob > i) {
                continue;
            }
            if (curJob > i + d) {
                return false;
            }
            int posCurJob = arrInd + mid;
            arrInd = posCurJob;
            if (switchArr.containsKey(i)) {
                arrInd = Math.min(posCurJob, switchArr.get(i));
            }
            if (arrInd >= arr.length) {
                return true;
            }
        }
        return arrInd >= arr.length;
    }

    static class Val {
        int num, ind;
        public Val(int num, int ind) {
            this.num = num;
            this.ind = ind;
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	100 ms	26400 KB	Execution failed because the return code was nonzero
2	Runtime error	106 ms	25416 KB	Execution failed because the return code was nonzero
3	Runtime error	102 ms	27900 KB	Execution failed because the return code was nonzero
4	Runtime error	101 ms	25880 KB	Execution failed because the return code was nonzero
5	Runtime error	106 ms	25228 KB	Execution failed because the return code was nonzero
6	Runtime error	101 ms	29276 KB	Execution failed because the return code was nonzero
7	Runtime error	101 ms	25252 KB	Execution failed because the return code was nonzero
8	Runtime error	100 ms	25740 KB	Execution failed because the return code was nonzero
9	Runtime error	102 ms	25440 KB	Execution failed because the return code was nonzero
10	Runtime error	104 ms	25232 KB	Execution failed because the return code was nonzero
11	Runtime error	103 ms	31852 KB	Execution failed because the return code was nonzero
12	Runtime error	101 ms	29932 KB	Execution failed because the return code was nonzero
13	Runtime error	100 ms	25664 KB	Execution failed because the return code was nonzero
14	Runtime error	106 ms	25376 KB	Execution failed because the return code was nonzero
15	Runtime error	101 ms	29908 KB	Execution failed because the return code was nonzero
16	Runtime error	100 ms	25664 KB	Execution failed because the return code was nonzero
17	Runtime error	102 ms	29412 KB	Execution failed because the return code was nonzero
18	Runtime error	101 ms	25560 KB	Execution failed because the return code was nonzero
19	Runtime error	107 ms	26016 KB	Execution failed because the return code was nonzero
20	Runtime error	102 ms	25656 KB	Execution failed because the return code was nonzero