Submission #1119452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119452	2024-11-27T04:48:20 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	65 / 100	702 ms	65536 KB

jobs

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

public class jobs {
    static final int MAXN = 100001; // Upper bound for efficient limits
    static int[] Cn; // Store job counts per day
    static List<Integer>[] Req; // Compact storage for job requests
    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;
    }

    @SuppressWarnings("unchecked")
    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());

        Cn = new int[n + 1]; // Only allocate for required days
        Req = new ArrayList[n + 1]; // Compact list of job indices

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

        for (int i = 1; i <= m; i++) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            int a = Integer.parseInt(st.nextToken()) + d;
            if (a <= n) { // Only store valid job requests within bounds
                Req[a].add(i);
                Cn[a]++;
            }
        }

        // Compute lower and upper bounds for binary search
        int left = 1, sol = m, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) continue;
            int bound = (Cn[x] + d) / (d + 1);
            left = Math.max(left, bound);
        }

        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);
    }
}

Subtask #1

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	334 ms	20360 KB	Output is correct
2	Correct	334 ms	20716 KB	Output is correct
3	Correct	356 ms	20324 KB	Output is correct
4	Correct	357 ms	20344 KB	Output is correct
5	Correct	341 ms	20392 KB	Output is correct
6	Correct	368 ms	20604 KB	Output is correct
7	Correct	358 ms	20488 KB	Output is correct
8	Correct	348 ms	20444 KB	Output is correct
9	Correct	367 ms	22944 KB	Output is correct
10	Correct	328 ms	22636 KB	Output is correct
11	Correct	312 ms	20600 KB	Output is correct
12	Correct	338 ms	27408 KB	Output is correct
13	Correct	361 ms	32188 KB	Output is correct
14	Runtime error	494 ms	38496 KB	Memory limit exceeded
15	Runtime error	464 ms	43252 KB	Memory limit exceeded
16	Runtime error	595 ms	55352 KB	Memory limit exceeded
17	Runtime error	702 ms	63052 KB	Memory limit exceeded
18	Runtime error	571 ms	65312 KB	Memory limit exceeded
19	Runtime error	545 ms	65536 KB	Execution killed with signal 9
20	Runtime error	677 ms	62740 KB	Memory limit exceeded