Submission #1119448

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119448	2024-11-27T04:25:33 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	267 ms	55100 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++) {
            int a = Integer.parseInt(br.readLine()) + 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	159 ms	16960 KB	Execution failed because the return code was nonzero
2	Runtime error	151 ms	16540 KB	Execution failed because the return code was nonzero
3	Runtime error	155 ms	16492 KB	Execution failed because the return code was nonzero
4	Runtime error	143 ms	16224 KB	Execution failed because the return code was nonzero
5	Runtime error	158 ms	16588 KB	Execution failed because the return code was nonzero
6	Runtime error	158 ms	16392 KB	Execution failed because the return code was nonzero
7	Runtime error	147 ms	16248 KB	Execution failed because the return code was nonzero
8	Runtime error	141 ms	16468 KB	Execution failed because the return code was nonzero
9	Runtime error	189 ms	25364 KB	Execution failed because the return code was nonzero
10	Runtime error	192 ms	25696 KB	Execution failed because the return code was nonzero
11	Runtime error	160 ms	16704 KB	Execution failed because the return code was nonzero
12	Runtime error	150 ms	19924 KB	Execution failed because the return code was nonzero
13	Runtime error	171 ms	21544 KB	Execution failed because the return code was nonzero
14	Runtime error	191 ms	28672 KB	Execution failed because the return code was nonzero
15	Runtime error	192 ms	29384 KB	Execution failed because the return code was nonzero
16	Runtime error	200 ms	38160 KB	Execution failed because the return code was nonzero
17	Runtime error	224 ms	41852 KB	Execution failed because the return code was nonzero
18	Runtime error	209 ms	39272 KB	Execution failed because the return code was nonzero
19	Runtime error	267 ms	55100 KB	Execution failed because the return code was nonzero
20	Runtime error	207 ms	39892 KB	Execution failed because the return code was nonzero