#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, d, m;
vector<int> v[maxn + 1];
bool check(int ma){
queue<pair<int, int>> q;
for (int i = 1; i <= n; ++i){
if (!q.empty() && i - q.front().first > d) return false;
if (v[i].size() > 0) q.push({i, v[i].size()});
int cur = ma;
while(cur > 0 && !q.empty()){
int lost = min(q.front().second, cur);
q.front().second -= lost;
cur -= lost;
if (q.front().second == 0) q.pop();
}
}
if (q.empty()) return true;
return false;
}
void print(int ma){
queue<pair<int, int>> q;
for (int i = 1; i <= n; ++i){
if (v[i].size() > 0) q.push({i, 0});
int cur = ma;
while(cur > 0 && !q.empty()){
int j = q.front().second;
for (; j < min((int)v[q.front().first].size(), q.front().second + cur); ++j)
cout << v[q.front().first][j] << ' ';
int lost = min(j - q.front().second, cur);
q.front().second = j;
cur -= lost;
if (q.front().second == v[q.front().first].size()) q.pop();
}
cout << 0 << '\n';
}
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> d >> m;
for (int i = 1; i <= m; ++i){
int x; cin >> x;
v[x].push_back(i);
}
int lo = 1, hi = m, ans = -1;
while(lo <= hi){
int mid = (lo + hi) >> 1;
if (check(mid)) ans = mid, hi = mid - 1;
else lo = mid + 1;
}
cout << ans << '\n';
print(ans);
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |