Submission #1119450

# Submission time Handle Problem Language Result Execution time Memory
1119450 2024-11-27T04:30:50 Z johu Job Scheduling (CEOI12_jobs) Java 11
0 / 100
463 ms 65536 KB
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;
        }

        while (m-- > 0) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            int a = Integer.parseInt(st.nextToken()) + d;
            Req[a].add(m + 1);
            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 {
                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);

        StringBuilder output = new StringBuilder();
        int dc = 1, dd = 1, x = 1;

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

            if (dd < x - d) {
                output.append("0\n");
                dd++;
                dc = 1;
            } else {
                output.append(Req[x].pollFirst()).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.
# Verdict Execution time Memory Grader output
1 Runtime error 214 ms 18368 KB Execution failed because the return code was nonzero
2 Runtime error 218 ms 18420 KB Execution failed because the return code was nonzero
3 Runtime error 223 ms 18412 KB Execution failed because the return code was nonzero
4 Runtime error 214 ms 18032 KB Execution failed because the return code was nonzero
5 Runtime error 217 ms 18176 KB Execution failed because the return code was nonzero
6 Runtime error 228 ms 18332 KB Execution failed because the return code was nonzero
7 Runtime error 222 ms 18372 KB Execution failed because the return code was nonzero
8 Runtime error 223 ms 18300 KB Execution failed because the return code was nonzero
9 Runtime error 277 ms 29172 KB Execution failed because the return code was nonzero
10 Runtime error 265 ms 29060 KB Execution failed because the return code was nonzero
11 Runtime error 224 ms 17472 KB Execution failed because the return code was nonzero
12 Runtime error 253 ms 21436 KB Execution failed because the return code was nonzero
13 Runtime error 282 ms 25324 KB Execution failed because the return code was nonzero
14 Runtime error 327 ms 28480 KB Execution failed because the return code was nonzero
15 Runtime error 302 ms 31128 KB Execution failed because the return code was nonzero
16 Runtime error 396 ms 37588 KB Execution failed because the return code was nonzero
17 Runtime error 409 ms 41964 KB Execution failed because the return code was nonzero
18 Runtime error 385 ms 45096 KB Execution failed because the return code was nonzero
19 Runtime error 463 ms 65536 KB Execution killed with signal 9
20 Runtime error 447 ms 41092 KB Execution failed because the return code was nonzero