제출 #875573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875573		rajat	Job Scheduling (CEOI12_jobs)	Java	0 / 100	115 ms	30104 KiB

jobs

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("in.txt"));
        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 + d < i) {
                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