Submission #1119462

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119462	2024-11-27T04:57:07 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	55 / 100	1000 ms	55468 KB

jobs

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

public class jobs {
    static final int MAXN = 1000005;
    static int n, m, d;
    static Pair[] a = new Pair[MAXN];

    static class Pair implements Comparable<Pair> {
        int first, second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int compareTo(Pair other) {
            return Integer.compare(this.first, other.first);
        }
    }

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

        // Read n, d, m
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // Read the pairs
        for (int i = 1; i <= m; i++) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            int first = Integer.parseInt(st.nextToken());
            a[i] = new Pair(first, i);
        }
        a[m + 1] = new Pair(Integer.MAX_VALUE, 0);

        // Sort the pairs
        Arrays.sort(a, 1, m + 1);

        // Binary search for the minimum `r`
        int l = 0, r = m;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 1;
            boolean valid = true;

            for (int i = 1; i <= n && valid; i++) {
                if (a[p].first + d < i) {
                    valid = false;
                    break;
                }
                int cnt = 0;
                while (cnt < mid && a[p].first <= i) {
                    cnt++;
                    p++;
                }
            }

            if (p > m) {
                r = mid;
            } else {
                l = mid;
            }
        }

        // Print the result
        System.out.println(r);

        // Generate the schedule
        int p = 1;
        StringBuilder output = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (cnt < r && a[p].first <= i) {
                cnt++;
                output.append(a[p].second).append(" ");
                p++;
            }
            output.append("0\n");
        }

        System.out.print(output);
    }
}

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	314 ms	23780 KB	Output is correct
2	Correct	330 ms	23984 KB	Output is correct
3	Correct	316 ms	23384 KB	Output is correct
4	Correct	306 ms	23632 KB	Output is correct
5	Correct	316 ms	23912 KB	Output is correct
6	Correct	338 ms	24124 KB	Output is correct
7	Correct	341 ms	23656 KB	Output is correct
8	Correct	334 ms	23800 KB	Output is correct
9	Correct	855 ms	23764 KB	Output is correct
10	Correct	888 ms	23472 KB	Output is correct
11	Correct	879 ms	24660 KB	Output is correct
12	Execution timed out	1024 ms	32276 KB	Time limit exceeded
13	Execution timed out	1039 ms	29488 KB	Time limit exceeded
14	Execution timed out	1058 ms	40704 KB	Time limit exceeded
15	Execution timed out	1040 ms	36636 KB	Time limit exceeded
16	Execution timed out	1051 ms	46192 KB	Time limit exceeded
17	Execution timed out	1038 ms	46408 KB	Time limit exceeded
18	Execution timed out	1044 ms	51060 KB	Time limit exceeded
19	Execution timed out	1040 ms	55468 KB	Time limit exceeded
20	Execution timed out	1048 ms	47852 KB	Time limit exceeded