Submission #1105200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105200		APerson	Job Scheduling (CEOI12_jobs)	Java	15 / 100	1074 ms	65536 KiB

jobs

import java.util.*;
public class jobs {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<ArrayList<Integer>> days = new ArrayList<>();
        for(int i = 0; i < n; i++) days.add(new ArrayList<>());
        for(int i = 1; i <= m; i++) {
            days.get(sc.nextInt()).add(i);
        }

        // turn input into a list where they are all just the days of the jobs
        ArrayList<Integer> jobs = new ArrayList<>();
        ArrayList<Integer> forPrinting = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            forPrinting.addAll(days.get(i));
            for(int j = 0; j < days.get(i).size(); j++) {
                jobs.add(i);
            }
        }
        Collections.reverse(forPrinting);

        // binary search on answer
        int min = 1;
        int max = m;
        while(min != max) {
            int mid = (min + max)/2;
            if(works(mid, d, jobs)) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }

        // output answer
        System.out.println(min);
        for(int i = 0; i < n; i++) {
            int index = min;
            while(index > 0 && !forPrinting.isEmpty()) {
                System.out.print(forPrinting.remove(forPrinting.size() - 1) + " ");
                index--;
            }
            System.out.println(0);
        }
        sc.close();
    }
    public static boolean works(int mid, int d, ArrayList<Integer> days) {
        int[] lastUsed = new int[mid];
        int index = 0;
        int curDay = 0;
        for (int day : days) {
            index %= mid;
            if(index == 0) curDay++;
            if(day > curDay) {
                curDay = day;
                index = 0;
            }
            lastUsed[index] = day;
            if(curDay - day > d) return false;
            index++;
        }
        return true;
    }
}

• Subtask 1: 15 / 100