Submission #1119528

#TimeUsernameProblemLanguageResultExecution timeMemory
1119528johuJob Scheduling (CEOI12_jobs)Java
90 / 100
1058 ms29668 KiB
import java.io.*; import java.util.*; public class jobs { public static void main(String[] args) throws IOException { FastInputReader reader = new FastInputReader(System.in); // Unified input handling int n = reader.nextInt(); // Number of days int d = reader.nextInt(); // Delay allowed int m = reader.nextInt(); // Number of events if (m <= 300000) { // Use the ArrayList-based implementation for smaller cases handleSmallCases(reader, n, d, m); } else { // Use the provided large case handler with slight optimization handleLargeCases(reader, n, d, m); } } private static void handleSmallCases(FastInputReader reader, int n, int d, int m) throws IOException { List<Pair> a = new ArrayList<>(m + 2); for (int i = 1; i <= m; i++) { a.add(new Pair(reader.nextInt(), 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(FastInputReader reader, int n, int d, int m) throws IOException { // Using the provided code for large cases with slight optimization int[] fr = new int[m + 1]; int[] sc = new int[m + 1]; for (int i = 1; i <= m; i++) { fr[i] = reader.nextInt(); sc[i] = i; } quickSort(fr, sc, 1, m); int l = 0, r = m; while (r - l > 1) { int mid = (l + r) / 2; int p = 1; for (int i = 1; i <= n; i++) { // Efficiently skip days where jobs cannot start if (p > m || fr[p] + d < i) break; int cnt = 0; // Reduce redundant checks in the inner loop while (cnt < mid && p <= m && fr[p] <= i) { cnt++; p++; } } if (p > m) { r = mid; } else { l = mid; } } // Output results (aligned with small case behavior) 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); } } static class FastInputReader { private final DataInputStream din; private final byte[] buffer; private int bufferPointer, bytesRead; public FastInputReader(InputStream in) { din = new DataInputStream(in); buffer = new byte[1 << 20]; // 64 KB buffer bufferPointer = bytesRead = 0; } private byte read() throws IOException { if (bufferPointer == bytesRead) { bytesRead = din.read(buffer, 0, buffer.length); bufferPointer = 0; if (bytesRead == -1) return -1; // End of stream } return buffer[bufferPointer++]; } public int nextInt() throws IOException { int ret = 0; byte c = read(); while (c <= ' ') c = read(); // Skip whitespace boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...