oj.uz

답안 #1105200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1105200 2024-10-25T17:31:55 Z APerson Job Scheduling (CEOI12_jobs) Java 11
15 / 100
 1000 ms 65536 KB 
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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 992 ms 27460 KB Output is correct
2 Correct 987 ms 27436 KB Output is correct
3 Execution timed out 1057 ms 26976 KB Time limit exceeded
4 Execution timed out 1046 ms 26908 KB Time limit exceeded
5 Execution timed out 1073 ms 27072 KB Time limit exceeded
6 Execution timed out 1042 ms 27292 KB Time limit exceeded
7 Execution timed out 1022 ms 27204 KB Time limit exceeded
8 Execution timed out 1016 ms 27252 KB Time limit exceeded
9 Execution timed out 1058 ms 30192 KB Time limit exceeded
10 Execution timed out 1036 ms 30660 KB Time limit exceeded
11 Correct 965 ms 29488 KB Output is correct
12 Execution timed out 1053 ms 37384 KB Time limit exceeded
13 Execution timed out 1071 ms 45732 KB Time limit exceeded
14 Execution timed out 1073 ms 50404 KB Time limit exceeded
15 Execution timed out 1055 ms 51408 KB Time limit exceeded
16 Execution timed out 1052 ms 63728 KB Time limit exceeded
17 Execution timed out 1060 ms 51932 KB Time limit exceeded
18 Execution timed out 1043 ms 65536 KB Time limit exceeded
19 Execution timed out 1074 ms 65536 KB Time limit exceeded
20 Execution timed out 1046 ms 65536 KB Time limit exceeded