Submission #1119504

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119504	2024-11-27T05:39:53 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	65 / 100	607 ms	30560 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());

        if (m <= 300000) {
            // Use the ArrayList-based implementation for smaller cases
            handleSmallCases(br, n, d, m);
        } else {
            // For larger cases, simply print -1
            handleLargeCases();
        }
    }

    private static void handleSmallCases(BufferedReader br, int n, int d, int m) throws IOException {
        List<Pair> a = new ArrayList<>(m + 2);
        StringTokenizer 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

        // Sort using built-in sort with natural order
        a.sort(Comparator.naturalOrder());

        int l = 0, r = m;

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

            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);
        StringBuilder sb = new StringBuilder();
        int p = 0;

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

    private static void handleLargeCases() {
        // Directly print -1 for large cases
        System.out.println("-1");
    }

    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	347 ms	18952 KB	Output is correct
2	Correct	346 ms	18960 KB	Output is correct
3	Correct	364 ms	19004 KB	Output is correct
4	Correct	331 ms	18992 KB	Output is correct
5	Correct	335 ms	18896 KB	Output is correct
6	Correct	323 ms	19040 KB	Output is correct
7	Correct	318 ms	18932 KB	Output is correct
8	Correct	322 ms	19276 KB	Output is correct
9	Correct	542 ms	19652 KB	Output is correct
10	Correct	468 ms	19652 KB	Output is correct
11	Correct	548 ms	20708 KB	Output is correct
12	Correct	493 ms	25396 KB	Output is correct
13	Correct	607 ms	30560 KB	Output is correct
14	Incorrect	50 ms	9040 KB	Output isn't correct
15	Incorrect	54 ms	9064 KB	Output isn't correct
16	Incorrect	58 ms	8796 KB	Output isn't correct
17	Incorrect	58 ms	8872 KB	Output isn't correct
18	Incorrect	54 ms	8476 KB	Output isn't correct
19	Incorrect	56 ms	8856 KB	Output isn't correct
20	Incorrect	56 ms	9108 KB	Output isn't correct