Submission #1119480

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119480	2024-11-27T05:11:27 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	65 / 100	1000 ms	65536 KB

jobs

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

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

        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // Use ArrayList for dynamic storage
        List<Pair> a = new ArrayList<>(m + 2);
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            a.add(new Pair(Integer.parseInt(st.nextToken()), i));
        }
        a.add(new Pair(1000000000, 0)); // Dummy pair for boundary

        // Use built-in sort with custom comparator
        a.sort(Comparator.naturalOrder());

        int l = 0, r = m;

        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 0; // Adjusted for zero-based indexing in ArrayList

            for (int i = 1; i <= n; i++) {
                if (a.get(p).fr + d < i) {
                    break;
                }
                int cnt = 0;
                while (cnt < mid && p < m && a.get(p).fr <= i) {
                    cnt++;
                    p++;
                }
            }

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

        System.out.println(r);
        int p = 0;

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (cnt < r && p < m && a.get(p).fr <= i) {
                sb.append(a.get(p).sc).append(" ");
                cnt++;
                p++;
            }
            sb.append("0\n");
        }

        System.out.print(sb);
    }

    static class Pair implements Comparable<Pair> {
        int fr, sc;

        Pair(int fr, int sc) {
            this.fr = fr;
            this.sc = sc;
        }

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

Subtask #1

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	357 ms	18748 KB	Output is correct
2	Correct	342 ms	19120 KB	Output is correct
3	Correct	325 ms	18952 KB	Output is correct
4	Correct	329 ms	19092 KB	Output is correct
5	Correct	323 ms	18832 KB	Output is correct
6	Correct	335 ms	19076 KB	Output is correct
7	Correct	339 ms	18868 KB	Output is correct
8	Correct	327 ms	18988 KB	Output is correct
9	Correct	546 ms	19272 KB	Output is correct
10	Correct	458 ms	19156 KB	Output is correct
11	Correct	545 ms	21020 KB	Output is correct
12	Correct	476 ms	25680 KB	Output is correct
13	Correct	625 ms	30616 KB	Output is correct
14	Runtime error	760 ms	36616 KB	Memory limit exceeded
15	Runtime error	759 ms	43516 KB	Memory limit exceeded
16	Runtime error	786 ms	49132 KB	Memory limit exceeded
17	Runtime error	967 ms	58776 KB	Memory limit exceeded
18	Execution timed out	1028 ms	53056 KB	Time limit exceeded
19	Execution timed out	1048 ms	65536 KB	Time limit exceeded
20	Runtime error	889 ms	58784 KB	Memory limit exceeded