oj.uz

Submission #1119473

# Submission time Handle Problem Language Result Execution time Memory
1119473 2024-11-27T05:07:39 Z johu Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 1000 ms 55432 KB 
import java.util.Arrays;
import java.util.Scanner;

public class jobs {
    static final int mxn = 1000005;
    static Pair[] a = new Pair[mxn];

    static class Pair {
        int fr, sc;

        Pair(int fr, int sc) {
            this.fr = fr;
            this.sc = sc;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int d = scanner.nextInt();
        int m = scanner.nextInt();

        for (int i = 1; i <= m; i++) {
            a[i] = new Pair(scanner.nextInt(), i);
        }
        a[m + 1] = new Pair(1000000000, 0);
        Arrays.sort(a, 1, m + 1, (p1, p2) -> Integer.compare(p1.fr, p2.fr));

        int l = 0, r = m;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 1;
            for (int i = 1; i <= n; i++) {
                if (a[p].fr + d < i) {
                    break;
                }
                int cnt = 0;
                while (cnt < mid && a[p].fr <= i) {
                    cnt++;
                    p++;
                }
            }
            if (p > m) {
                r = mid;
            } else {
                l = mid;
            }
        }
        System.out.println(r);
        int p = 1;
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (cnt < r && a[p].fr <= i) {
                cnt++;
                System.out.print(a[p].sc + " ");
                p++;
            }
            System.out.println(0);
        }
        scanner.close();
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1006 ms 27920 KB Time limit exceeded
2 Execution timed out 1008 ms 27628 KB Time limit exceeded
3 Execution timed out 1024 ms 27572 KB Time limit exceeded
4 Execution timed out 1069 ms 27304 KB Time limit exceeded
5 Execution timed out 1060 ms 27632 KB Time limit exceeded
6 Execution timed out 1047 ms 27668 KB Time limit exceeded
7 Execution timed out 1060 ms 27316 KB Time limit exceeded
8 Execution timed out 1055 ms 27420 KB Time limit exceeded
9 Execution timed out 1040 ms 26724 KB Time limit exceeded
10 Execution timed out 1029 ms 26968 KB Time limit exceeded
11 Execution timed out 1050 ms 26868 KB Time limit exceeded
12 Execution timed out 1062 ms 29392 KB Time limit exceeded
13 Execution timed out 1073 ms 34260 KB Time limit exceeded
14 Execution timed out 1041 ms 37584 KB Time limit exceeded
15 Execution timed out 1060 ms 39720 KB Time limit exceeded
16 Execution timed out 1064 ms 46864 KB Time limit exceeded
17 Execution timed out 1105 ms 49484 KB Time limit exceeded
18 Execution timed out 1070 ms 53252 KB Time limit exceeded
19 Execution timed out 1047 ms 55432 KB Time limit exceeded
20 Execution timed out 1033 ms 49316 KB Time limit exceeded