Submission #1119451

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119451	2024-11-27T04:35:58 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	55 / 100	664 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;
        }

        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]++;
        }

        // Compute lower and upper bounds for binary search
        int left = 1, sol = 1, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) {
                if (r <= d) r++;
            } else {
                int bound = (Cn[x] + d) / (d + 1);
                if (bound > left) {
                    left = bound;
                }
                int reduced = (Cn[x] + sol - 1) / sol;
                if (r * sol >= Cn[x]) {
                    r -= reduced;
                    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);

        // Output the schedule
        StringBuilder output = new StringBuilder();
        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) {
                output.append("0\n");
                dd++;
                dc = 1;
            } else {
                output.append(p.next()).append(" ");
                if (++dc > sol) {
                    dc = 1;
                    dd++;
                    output.append("0\n");
                }
            }
        }

        if (dc > 1) {
            dd++;
            output.append("0\n");
        }
        while (dd++ <= n) {
            output.append("0\n");
        }

        System.out.print(output);
    }
}

Compilation message

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

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	354 ms	23816 KB	Output is correct
2	Correct	356 ms	20168 KB	Output is correct
3	Correct	362 ms	20668 KB	Output is correct
4	Correct	354 ms	20620 KB	Output is correct
5	Correct	351 ms	20324 KB	Output is correct
6	Correct	364 ms	20328 KB	Output is correct
7	Correct	366 ms	20728 KB	Output is correct
8	Correct	336 ms	22056 KB	Output is correct
9	Runtime error	372 ms	37256 KB	Memory limit exceeded
10	Runtime error	356 ms	37440 KB	Memory limit exceeded
11	Correct	308 ms	23328 KB	Output is correct
12	Correct	336 ms	30392 KB	Output is correct
13	Correct	380 ms	32444 KB	Output is correct
14	Runtime error	487 ms	44596 KB	Memory limit exceeded
15	Runtime error	479 ms	42624 KB	Memory limit exceeded
16	Runtime error	559 ms	48036 KB	Memory limit exceeded
17	Runtime error	642 ms	62820 KB	Memory limit exceeded
18	Runtime error	592 ms	65536 KB	Execution killed with signal 9
19	Runtime error	528 ms	65536 KB	Execution killed with signal 9
20	Runtime error	664 ms	61368 KB	Memory limit exceeded