//======================================================================================================================
// Name : job_scheduling.cpp
// Author : Jinchen Li
// Date Created: 5/22/2022
// Description : oj.uz, CEOI 2012 Day 1 Problem 1, Job Scheduling in C++, Ansi-style
//======================================================================================================================
// Directives
#include <algorithm>
#include <iostream>
#include <vector>
// Request Structure
struct request {
int id = 0;
int time = 0;
bool operator < (const request& rhs) const {
return time < rhs.time;
}
};
// Function Declarations
bool is_num_able(const int& D, const int& M, const int& machine_num, const std::vector<request>& requests);
// Main
int main() {
// Accepting Inputs
int N;
int D;
int M;
std::cin >> N >> D >> M;
std::vector<request> requests (M);
for (int x = 1; x <= M; x++) {
std::cin >> requests[x - 1].time;
requests[x - 1].id = x;
}
// Processing Inputs
std::sort(requests.begin(), requests.end());
int low = 1;
int high = M;
while (low < high) {
int cur = low + (high - low) / 2;
if (is_num_able(D, M, cur, requests)) {
high = cur;
}
else {
low = cur + 1;
}
}
// Printing Outputs
int print_ind {};
std::cout << low << ' ' << '\n';
for (int x = 0; x < N; x++) {
int prev_print_ind = print_ind;
for (; print_ind < prev_print_ind + low && print_ind < M && requests[print_ind].time <= x + 1; print_ind++) {
std::cout << requests[print_ind].id << ' ';
}
std::cout << "0 \n";
}
}
// Is Amount of Machines Able Function
bool is_num_able(const int& D, const int& M, const int& machine_num, const std::vector<request>& requests) {
int x = 0;
int cur_day = 1;
while (x < M) {
cur_day = std::max(cur_day, requests[x].time);
request upper_bound_request = {.id = 0, .time = cur_day};
auto next_ind = static_cast<int>(std::upper_bound(requests.begin() + x, requests.end(), upper_bound_request) - requests.begin());
if (cur_day > requests[x].time + D) {
return false;
}
if (next_ind - x > machine_num) {
next_ind = x + machine_num;
}
cur_day++;
x = next_ind;
}
return true;
}
