#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n, d, w;
vector<pii> v;
vector<vector<int>> dia;
bool f(int m){
queue<int> q;
for(int i = 0; i < n+1; i++){
dia[i].clear();
}
for(int i = 0; i < m; i++){
q.push(0);
}
for(int i = 0; i < w; i++){
if(q.empty())return false;
if(q.front() > v[i].first){
if(q.front()-v[i].first > d)return false;
dia[q.front()].push_back(v[i].second);
if(q.front()+1 > n){
q.pop();
continue;
}
q.push(q.front()+1);
q.pop();
}
else{
dia[v[i].first].push_back(v[i].second);
q.pop();
if(v[i].first+1 > n)continue;
q.push(v[i].first+1);
}
}
return true;
}
void buscab(){
int ini = 1, fim = w, resp = 1;
while(ini <= fim){
int m = (ini+fim)/2;
if(f(m)){
fim = m-1;
resp = m;
}
else{
ini = m+1;
}
}
f(resp);
cout << resp << '\n';
for(int i = 1; i < n+1; i++){
for(auto& x : dia[i])cout << x << " ";
cout << "0\n";
}
}
int main(){
cin >> n >> d >> w;
v.reserve(w);
dia.reserve(n+1);
for(int i = 0; i < w; i++){
int x;
cin >> x;
v.push_back(make_pair(x, i+1));
}
for(int i = 0; i < n+1; i++)dia.push_back({});
sort(v.begin(), v.end());
buscab();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |