Submission #1119448

#TimeUsernameProblemLanguageResultExecution timeMemory
1119448johuJob Scheduling (CEOI12_jobs)Java
0 / 100
267 ms55100 KiB
import java.io.*; import java.util.*; public class jobs { static final int MAXN = 100001; static int[] Cn = new int[MAXN]; static Deque<Integer>[] Req = new ArrayDeque[MAXN]; static int n, m, d; public static boolean test(int k) { int dd = 1, r = 0; for (int x = 1; x <= n; x++) { if (Cn[x] == 0) continue; if (dd < x - d) { dd = x - d; r = 0; } dd += (Cn[x] + r) / k; r = (Cn[x] + r) % k; if (dd > x + 1 || (dd == x + 1 && r > 0)) { return false; } } return true; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); d = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); for (int x = 0; x <= n; x++) { Req[x] = new ArrayDeque<>(); Cn[x] = 0; } for (int i = 1; i <= m; i++) { int a = Integer.parseInt(br.readLine()) + d; Req[a].add(i); Cn[a]++; } int left = 1, sol = 0, r = 0; for (int x = 1; x <= n; x++) { if (Cn[x] == 0) { if (r <= d) r++; } else { if ((Cn[x] + d) / (d + 1) > left) { left = (Cn[x] + d) / (d + 1); } if (r * sol >= Cn[x]) { r -= (Cn[x] + sol - 1) / sol; r++; } else { sol += (Cn[x] - r * sol + d) / (d + 1); r = 1; } } } while (left < sol) { int mid = (left + sol) / 2; if (test(mid)) { sol = mid; } else { left = mid + 1; } } System.out.println(sol); int dc = 1, dd = 1, x = 1; Iterator<Integer> p = Req[1].iterator(); while (dd <= n) { if (!p.hasNext()) { x++; while (x <= n && Req[x].isEmpty()) x++; if (x > n) break; p = Req[x].iterator(); } if (dd < x - d) { System.out.println("0"); dd++; dc = 1; } else { System.out.print(p.next() + " "); if (++dc > sol) { dc = 1; dd++; System.out.println("0"); } } } if (dc > 1) { dd++; System.out.println("0"); } while (dd++ <= n) { System.out.println("0"); } } }

Compilation message (stderr)

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
#Verdict Execution timeMemoryGrader output
Fetching results...