Submission #1119510

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119510	2024-11-27T05:50:31 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	75 / 100	1000 ms	38836 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, use the optimized quicksort-based implementation
            handleLargeCases(n, d, m, br);
        }
    }

    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(int n, int d, int m, BufferedReader br) throws IOException {
        int[] fr = new int[m + 1];
        int[] sc = new int[m + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            fr[i] = Integer.parseInt(st.nextToken());
            sc[i] = i;
        }

        quickSort(fr, sc, 1, m);

        int l = 0, r = m + 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 1;
            for (int i = 1; i <= n; i++) {
                int cnt = 0;
                while (cnt < mid && p <= m && fr[p] <= i) {
                    cnt++;
                    p++;
                }
            }
            if (p > m) {
                r = mid;
            } else {
                l = mid;
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(r + "\n");

        int p = 1;
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (cnt < r && p <= m && fr[p] <= i) {
                bw.write(sc[p] + " ");
                cnt++;
                p++;
            }
            bw.write("0\n");
        }
        bw.flush();
    }

    private static void quickSort(int[] fr, int[] sc, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(fr, sc, low, high);
            quickSort(fr, sc, low, pivotIndex - 1);
            quickSort(fr, sc, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] fr, int[] sc, int low, int high) {
        int pivot = fr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (fr[j] <= pivot) {
                i++;
                swap(fr, sc, i, j);
            }
        }
        swap(fr, sc, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] fr, int[] sc, int i, int j) {
        int tempFr = fr[i];
        fr[i] = fr[j];
        fr[j] = tempFr;

        int tempSc = sc[i];
        sc[i] = sc[j];
        sc[j] = tempSc;
    }

    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

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	351 ms	19240 KB	Output is correct
2	Correct	349 ms	19256 KB	Output is correct
3	Correct	390 ms	19124 KB	Output is correct
4	Correct	346 ms	19076 KB	Output is correct
5	Correct	354 ms	18924 KB	Output is correct
6	Correct	340 ms	19140 KB	Output is correct
7	Correct	328 ms	18964 KB	Output is correct
8	Correct	340 ms	18948 KB	Output is correct
9	Correct	607 ms	19448 KB	Output is correct
10	Correct	491 ms	19548 KB	Output is correct
11	Correct	566 ms	20844 KB	Output is correct
12	Correct	505 ms	25196 KB	Output is correct
13	Correct	659 ms	30604 KB	Output is correct
14	Correct	405 ms	26308 KB	Output is correct
15	Correct	802 ms	28924 KB	Output is correct
16	Runtime error	535 ms	35460 KB	Memory limit exceeded
17	Runtime error	554 ms	38200 KB	Memory limit exceeded
18	Execution timed out	1059 ms	34720 KB	Time limit exceeded
19	Execution timed out	1045 ms	36808 KB	Time limit exceeded
20	Runtime error	597 ms	38836 KB	Memory limit exceeded