Submission #875568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
875568	2023-11-20T04:17:19 Z	rajat	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	112 ms	30272 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);
        int arrInd = 0;
        for (int i = 1; i <= n; i++) {
            if (arrInd >= arr.length || arr[arrInd].num > i ) {
                str.append("\n");
                str.append(0);
                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);
            str.append("\n");
            for (int j = prevStart; j < end; j++) {
                str.append(arr[j].ind + " ");
            }
            str.append(0);
        }
        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	29784 KB	Execution failed because the return code was nonzero
2	Runtime error	101 ms	25668 KB	Execution failed because the return code was nonzero
3	Runtime error	99 ms	25980 KB	Execution failed because the return code was nonzero
4	Runtime error	102 ms	26064 KB	Execution failed because the return code was nonzero
5	Runtime error	105 ms	25488 KB	Execution failed because the return code was nonzero
6	Runtime error	102 ms	29608 KB	Execution failed because the return code was nonzero
7	Runtime error	102 ms	30272 KB	Execution failed because the return code was nonzero
8	Runtime error	101 ms	25416 KB	Execution failed because the return code was nonzero
9	Runtime error	103 ms	25772 KB	Execution failed because the return code was nonzero
10	Runtime error	102 ms	25788 KB	Execution failed because the return code was nonzero
11	Runtime error	102 ms	26092 KB	Execution failed because the return code was nonzero
12	Runtime error	102 ms	25888 KB	Execution failed because the return code was nonzero
13	Runtime error	102 ms	25992 KB	Execution failed because the return code was nonzero
14	Runtime error	112 ms	25380 KB	Execution failed because the return code was nonzero
15	Runtime error	102 ms	29380 KB	Execution failed because the return code was nonzero
16	Runtime error	100 ms	25428 KB	Execution failed because the return code was nonzero
17	Runtime error	104 ms	29600 KB	Execution failed because the return code was nonzero
18	Runtime error	102 ms	25672 KB	Execution failed because the return code was nonzero
19	Runtime error	105 ms	27792 KB	Execution failed because the return code was nonzero
20	Runtime error	101 ms	25676 KB	Execution failed because the return code was nonzero