#include <bits/stdc++.h>
using namespace std;
// clang-format off
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define endl "\n"
#define pb push_back
#define sz(v) int(v.size())
#define mems(x,y) memset(x,y,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define forn(i,s,e) for(int i = s; i < (e); ++i)
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
for ( \
auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
blockTime.second; \
debug("%s : %lld ms\n ", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false)
const int M = 1e9 + 7;
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
#ifdef LOCAL
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
#else
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { for (auto v : vec) os << v << ' '; return os; }
#endif
template <class T> T ABS(const T &x) {return x>0? x:-x;}
ll gcd(ll n1, ll n2) {return n2==0? ABS(n1) : gcd(n2,n1%n2);}
ll lcm(ll n1, ll n2) {return n1==0 && n2==0? 0 : ABS(n1*n2)/gcd(n1,n2);}
ll ceil2(ll a, ll b) {return (a + b - 1) / b;}
template <typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template <typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template <typename T> vector<T> sorttrunq(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
// clang-format on
// int dx[4] = {1,-1,0,0};
// int dy[4] = {0,0,1,-1};
/*
1. When multiplying always consider the possiblity of overflow.
*/
void solve() {
int n, d, m;
cin >> n >> d >> m;
vi t(m);
cin >> t;
vi pos(m);
iota(all(pos), 0);
sort(all(pos), [&](int a, int b) { return t[a] < t[b]; });
vector<vi> tmp(n + 1);
auto ok = [&](int x) {
tmp.clear();
tmp.resize(n + 1);
deque<int> dq(x, 0);
for (int idx : pos) {
int st = max(t[idx], dq.front());
if (st > t[idx] + d) {
return false;
}
tmp[st].push_back(idx);
dq.pop_front();
dq.push_back(st + 1);
}
return true;
};
int l = 0, r = m + 1;
vector<vi> ans;
while (r - l > 1) {
ll mid = l + (r - l) / 2;
if (ok(mid)) {
ans = tmp;
r = mid;
} else
l = mid;
}
cout << r << endl;
for (int i = 1; i <= n; ++i) {
for (int &el : ans[i]) {
cout << el + 1 << " ";
}
cout << 0 << endl;
}
}
int main() {
FASTIO
int t = 1;
while (t--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
3360 KB |
Output is correct |
| 2 |
Correct |
39 ms |
3496 KB |
Output is correct |
| 3 |
Correct |
38 ms |
3360 KB |
Output is correct |
| 4 |
Correct |
36 ms |
3368 KB |
Output is correct |
| 5 |
Correct |
38 ms |
3480 KB |
Output is correct |
| 6 |
Correct |
37 ms |
3432 KB |
Output is correct |
| 7 |
Correct |
37 ms |
3348 KB |
Output is correct |
| 8 |
Correct |
46 ms |
3504 KB |
Output is correct |
| 9 |
Correct |
57 ms |
7716 KB |
Output is correct |
| 10 |
Correct |
56 ms |
7732 KB |
Output is correct |
| 11 |
Correct |
50 ms |
2716 KB |
Output is correct |
| 12 |
Correct |
116 ms |
5252 KB |
Output is correct |
| 13 |
Correct |
182 ms |
8196 KB |
Output is correct |
| 14 |
Correct |
269 ms |
11356 KB |
Output is correct |
| 15 |
Correct |
304 ms |
12536 KB |
Output is correct |
| 16 |
Correct |
406 ms |
15596 KB |
Output is correct |
| 17 |
Correct |
526 ms |
19992 KB |
Output is correct |
| 18 |
Correct |
579 ms |
20652 KB |
Output is correct |
| 19 |
Correct |
673 ms |
26988 KB |
Output is correct |
| 20 |
Correct |
540 ms |
19976 KB |
Output is correct |
