import java.io.*;
import java.util.*;
class jobScheduling {
static int N, D, M;
static ArrayList<Job> jobs;
static int jobIdx;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(new FileReader("job_scheduling.in"));
jobs = new ArrayList<>();
N = sc.nextInt();
D = sc.nextInt();
M = sc.nextInt();
for (int i = 0; i < M; i++) {
int day = sc.nextInt();
Job j = new Job(day, i+1);
jobs.add(j);
}
Collections.sort(jobs, (Job j1, Job j2) -> Integer.compare (j1.day, j2.day));
// ArrayList<ArrayList<Integer>> execSchedule = new ArrayList<>();
// boolean result = schedule(execSchedule, 1);
// System.out.println(result);
ArrayList<ArrayList<Integer>> sched = new ArrayList<>();
int result = search(1, 1000001, sched);
System.out.println(result);
writeSchedule(sched);
}
static int search(int lo, int hi, ArrayList<ArrayList<Integer>> sched) {
// searches for first true
// lo will be one above known false
// hi will be known true
hi++;
while (lo < hi) {
// lo = 3 hi = 4
int mid = lo + (hi-lo)/2;
boolean result = schedule(sched, mid);
if (result) {
hi = mid;
} else {
lo = mid + 1;
}
}
schedule(sched, lo);
return lo;
}
/*
* execSchedule: outer array list is days, inner array list is id numbers to execute
* note that this function must add something to execSchedule even if an empty list
* because there must be an entry for the day
* q: queue (deque) (linked list) of array list of items waiting to be execute
* nMach: max number of machines allowed
*/
static void execute(ArrayList<ArrayList<Integer>> execSchedule, Deque<ArrayList<Integer>> q, int nMach) {
execSchedule.add(new ArrayList<>());
int machLeft = nMach;
Iterator<ArrayList<Integer>> iter = q.descendingIterator();
while (iter.hasNext()) {
if (machLeft == 0) break;
ArrayList<Integer> n = iter.next();
int qEntrySize = n.size();
int m = Math.min(qEntrySize, machLeft);
ArrayList<Integer> es = execSchedule.get(execSchedule.size()-1);
for (int i = 0; i < m; i++) {
// transfer m jobs from n (deque link) to execSchedule[-1]
// here we are getting job from final location in n (deque link)
int id = n.get(n.size()-1);
n.remove(n.size()-1);
es.add(id);
}
// remove from available machines
machLeft -= m;
}
}
static int computeNewJobs(ArrayList<Integer> ret, int day) {
// ret is a list of job ids. That's all we need to know to
// know what we are adding to the queue. they will be associated
// with a certain day. they won't really be less than that
// day because we try every day to call computer new jobs
ret.clear();
while (jobIdx < M && jobs.get(jobIdx).day <= day) {
ret.add(jobs.get(jobIdx).id);
jobIdx++;
}
return ret.size();
}
// this is top level routine.
static boolean schedule(ArrayList<ArrayList<Integer>> execSchedule, int nMach) {
execSchedule.clear();
// so we actually create the deque
Deque<ArrayList<Integer>> deq = new LinkedList<>();
// now we fill the deque with D+1 empty days
for (int i = 0; i <= D; i++ ) {
deq.addLast(new ArrayList<Integer>());
}
jobIdx = 0;
for (int day = 1; day <= N; day++) {
// first compute new jobs that appeared today
ArrayList<Integer> newJobIds = new ArrayList<>();
computeNewJobs(newJobIds, day);
// push them on the deck
deq.addFirst(newJobIds);
// why at this point do we check if last entry is empty
// well first time through known to be empty. after that
// we call execute before we get here
if (deq.getLast().size() > 0) {
return false;
}
deq.removeLast();
execute(execSchedule, deq, nMach);
}
return true;
}
static void writeSchedule(ArrayList<ArrayList<Integer>> sched) {
for (ArrayList<Integer> l: sched) {
for (int i: l) {
System.out.print(i + " ");
}
System.out.println("0");
}
}
static class Job {
public int day;
public int id;
public Job(int day, int id) {
this.day = day;
this.id = id;
}
}
}
