Submission #1119449

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119449	2024-11-27T04:29:34 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	50 / 100	1000 ms	65536 KB

jobs

import java.io.*;
import java.util.*;

public class jobs {
    static final int MAXN = 100001;
    static int[] Cn = new int[MAXN];
    static Deque<Integer>[] Req = new ArrayDeque[MAXN];
    static int n, m, d;

    public static boolean test(int k) {
        int dd = 1, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) continue;
            if (dd < x - d) {
                dd = x - d;
                r = 0;
            }
            dd += (Cn[x] + r) / k;
            r = (Cn[x] + r) % k;
            if (dd > x + 1 || (dd == x + 1 && r > 0)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int x = 0; x <= n; x++) {
            Req[x] = new ArrayDeque<>();
            Cn[x] = 0;
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            int a = Integer.parseInt(st.nextToken()) + d;
            Req[a].add(i);
            Cn[a]++;
        }

        int left = 1, sol = 0, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) {
                if (r <= d) r++;
            } else {
                if ((Cn[x] + d) / (d + 1) > left) {
                    left = (Cn[x] + d) / (d + 1);
                }
                if (r * sol >= Cn[x]) {
                    r -= (Cn[x] + sol - 1) / sol;
                    r++;
                } else {
                    sol += (Cn[x] - r * sol + d) / (d + 1);
                    r = 1;
                }
            }
        }

        while (left < sol) {
            int mid = (left + sol) / 2;
            if (test(mid)) {
                sol = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(sol);

        int dc = 1, dd = 1, x = 1;
        Iterator<Integer> p = Req[1].iterator();

        while (dd <= n) {
            if (!p.hasNext()) {
                x++;
                while (x <= n && Req[x].isEmpty()) x++;
                if (x > n) break;
                p = Req[x].iterator();
            }

            if (dd < x - d) {
                System.out.println("0");
                dd++;
                dc = 1;
            } else {
                System.out.print(p.next() + " ");
                if (++dc > sol) {
                    dc = 1;
                    dd++;
                    System.out.println("0");
                }
            }
        }

        if (dc > 1) {
            dd++;
            System.out.println("0");
        }
        while (dd++ <= n) {
            System.out.println("0");
        }
    }
}

Compilation message

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	821 ms	20408 KB	Output is correct
2	Correct	856 ms	20224 KB	Output is correct
3	Correct	768 ms	20532 KB	Output is correct
4	Correct	779 ms	20192 KB	Output is correct
5	Correct	760 ms	20216 KB	Output is correct
6	Correct	794 ms	20492 KB	Output is correct
7	Correct	800 ms	20232 KB	Output is correct
8	Correct	850 ms	20396 KB	Output is correct
9	Execution timed out	1035 ms	35484 KB	Time limit exceeded
10	Execution timed out	1060 ms	35404 KB	Time limit exceeded
11	Correct	738 ms	20012 KB	Output is correct
12	Correct	924 ms	24592 KB	Output is correct
13	Execution timed out	1058 ms	29208 KB	Time limit exceeded
14	Execution timed out	1067 ms	35692 KB	Time limit exceeded
15	Execution timed out	1059 ms	37724 KB	Time limit exceeded
16	Execution timed out	1058 ms	42760 KB	Time limit exceeded
17	Execution timed out	1040 ms	47284 KB	Time limit exceeded
18	Execution timed out	1029 ms	52384 KB	Time limit exceeded
19	Runtime error	525 ms	65536 KB	Execution killed with signal 9
20	Execution timed out	1099 ms	46300 KB	Time limit exceeded