#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define mii map<int, int>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define all(a, len) (a) + 1, (a) + len + 1
#define vall(a) (a).begin(), a.end()
#define _READ(name) freopen(name, "r", stdin)
#define _WRITE(name) freopen(name, "w", stdout)
const int INF = 4e18;
const int MOD = 1e9 + 7;
int n, m, d; const int mx = 1e5 + 3;
int a[mx];
int cnt[mx];
vi pos[mx];
int id[mx];
vi ans[mx];
void TheEminemShow() {
cin >> n >> d >> m;
rep(i, 1, m) {
int t; cin >> t;
cnt[t]++;
pos[t].pb(i);
}
}
bool check(int mid) {
deque<ii> dq;
rep(i, 1, n) {
if (cnt[i]) dq.pb({i+d, cnt[i]});
int cur = 0;
while (dq.size() && cur + dq.front().ss <= mid) {
cur += dq.front().ss;
dq.pop_front();
}
int rem = mid - cur;
if (dq.size()) {
dq.front().ss -= rem;
if (dq.front().ff <= i) return 0;
}
}
return 1;
}
void Recovery() {
int l = 1, r = m, res = 1;
while (l <= r) {
int mid = (l+r)>>1;
if (check(mid)) {
res = mid; r = mid-1;
} else {
l = mid+1;
}
}
cout << res << endl;
deque<ii> dq;
rep(i, 1, n) {
if (cnt[i]) dq.pb({i+d, cnt[i]});
int cur = 0;
while (dq.size() && cur + dq.front().ss <= res) {
cur += dq.front().ss;
while (dq.front().ss) {
ans[i].pb(pos[dq.front().ff-d][id[dq.front().ff-d]++]);
dq.front().ss--;
}
dq.pop_front();
}
int rem = res - cur;
if (dq.size()) {
dq.front().ss -= rem;
for (int _ = 0; _ < rem; _++) {
ans[i].pb(pos[dq.front().ff-d][id[dq.front().ff-d]++]);
}
}
}
rep(i, 1, n) {
for (auto it: ans[i]) cout << it << ' ';
cout << "0\n";
}
}
void Kamikaze() {
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int TEST = 1;
// cin >> TEST;
while (TEST--) {
TheEminemShow();
Recovery();
Kamikaze();
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
