Submission #1119481

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119481	2024-11-27T05:12:50 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	60 / 100	1000 ms	54040 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 a custom array for efficient memory usage
        Pair[] a = new Pair[m + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            a[i] = new Pair(Integer.parseInt(st.nextToken()), i);
        }

        // Sort array using Arrays.sort with a custom comparator
        Arrays.sort(a, 1, m + 1);

        int l = 0, r = m;

        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 1;

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

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

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

        // Use BufferedWriter for efficient output
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (cnt < r && p <= m && a[p].fr <= i) {
                bw.write(a[p].sc + " ");
                cnt++;
                p++;
            }
            bw.write("0\n");
        }
        bw.flush();
    }

    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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	360 ms	19452 KB	Output is correct
2	Correct	362 ms	19280 KB	Output is correct
3	Correct	356 ms	19232 KB	Output is correct
4	Correct	398 ms	19132 KB	Output is correct
5	Correct	363 ms	19700 KB	Output is correct
6	Correct	406 ms	19464 KB	Output is correct
7	Correct	407 ms	19488 KB	Output is correct
8	Correct	384 ms	19252 KB	Output is correct
9	Correct	884 ms	19320 KB	Output is correct
10	Correct	942 ms	19320 KB	Output is correct
11	Correct	887 ms	20928 KB	Output is correct
12	Correct	997 ms	25452 KB	Output is correct
13	Execution timed out	1089 ms	28172 KB	Time limit exceeded
14	Execution timed out	1049 ms	32636 KB	Time limit exceeded
15	Execution timed out	1063 ms	36008 KB	Time limit exceeded
16	Execution timed out	1060 ms	41712 KB	Time limit exceeded
17	Execution timed out	1053 ms	44072 KB	Time limit exceeded
18	Execution timed out	1043 ms	47176 KB	Time limit exceeded
19	Execution timed out	1018 ms	54040 KB	Time limit exceeded
20	Execution timed out	1042 ms	44968 KB	Time limit exceeded