import java.io.*;
import java.util.*;
public class jobs {
static class Job {
int day, id;
Job(int d, int i) { day = d; id = i; }
}
static int N, D, M;
static Job[] jobs;
// Simple pass to check feasibility
static boolean works(int K) {
int ptr = 0;
for (int day = 1; day <= N; day++) {
for (int used = 0; used < K; used++) {
if (ptr == M) return true;
if (jobs[ptr].day > day)
break;
if (jobs[ptr].day + D < day)
return false;
ptr++;
}
}
return ptr == M;
}
// Build actual schedule once, after minimal K is known
static List<List<Integer>> buildSchedule(int K) {
List<List<Integer>> schedule = new ArrayList<>(N);
for (int i = 0; i < N; i++) schedule.add(new ArrayList<>());
int ptr = 0;
for (int day = 1; day <= N; day++) {
for (int used = 0; used < K; used++) {
if (ptr == M) return schedule;
if (jobs[ptr].day > day) break;
schedule.get(day - 1).add(jobs[ptr].id);
ptr++;
}
}
return schedule;
}
public static void main(String[] args) throws Exception {
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());
jobs = new Job[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int day = Integer.parseInt(st.nextToken());
jobs[i] = new Job(day, i + 1);
}
Arrays.sort(jobs, Comparator.comparingInt(a -> a.day));
int lo = 1, hi = M;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (works(mid)) hi = mid;
else lo = mid + 1;
}
int K = lo;
List<List<Integer>> schedule = buildSchedule(K);
StringBuilder out = new StringBuilder();
out.append(K).append("\n");
for (int day = 0; day < N; day++) {
for (int id : schedule.get(day))
out.append(id).append(" ");
out.append("0\n");
}
System.out.print(out);
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |