#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cassert>
#include <numeric>
#include <set>
#include <cstring>
#include <map>
#include <iomanip>
#include <string>
#include <queue>
#include <array>
using namespace std;
#define vi vector<int>
#define ll long long
#define pii pair<int, int>
#define mp make_pair
const int mx = 1e5 + 1;
int a[mx], n, m, d;
vi tr[mx];
bool can(int x){
queue<pii> q;
for (int i = 1; i <= n; ++i){
for (int j: tr[i])
q.push(make_pair(j, i));
int cnt = x;
while ((cnt > 0) & (!q.empty())){
pii temp = q.front();
if (i - temp.second > d) return false;
q.pop();
--cnt;
}
}
return true;
}
void solve(){
cin >> n >> d >> m;
for (int i = 1; i <= m; ++i){
int x; cin >> x;
++a[x];
tr[x].push_back(i);
}
int l = 1, r = 1e5;
while (l + 1 < r){
int m = (l + r)/2;
if (can(m)) r = m;
else l = m;
}
cout << r << "\n";
queue<int> q;
for (int i = 1; i <= n; ++i){
for (int j: tr[i]) q.push(j);
int cnt = r;
while((cnt > 0) & !(q.empty())){
cout << q.front() << " ";
q.pop();
--cnt;
}
cout << "0\n";
}
}
int main(){
//int t; cin >> t;
//while(t--)
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
4520 KB |
Output is correct |
2 |
Correct |
25 ms |
4516 KB |
Output is correct |
3 |
Correct |
24 ms |
4308 KB |
Output is correct |
4 |
Correct |
25 ms |
4308 KB |
Output is correct |
5 |
Correct |
25 ms |
4520 KB |
Output is correct |
6 |
Correct |
30 ms |
4516 KB |
Output is correct |
7 |
Correct |
26 ms |
4524 KB |
Output is correct |
8 |
Correct |
30 ms |
4548 KB |
Output is correct |
9 |
Correct |
25 ms |
4436 KB |
Output is correct |
10 |
Correct |
24 ms |
4520 KB |
Output is correct |
11 |
Correct |
24 ms |
4184 KB |
Output is correct |
12 |
Correct |
48 ms |
5864 KB |
Output is correct |
13 |
Correct |
76 ms |
8020 KB |
Output is correct |
14 |
Correct |
104 ms |
10396 KB |
Output is correct |
15 |
Correct |
111 ms |
10900 KB |
Output is correct |
16 |
Correct |
159 ms |
13648 KB |
Output is correct |
17 |
Correct |
173 ms |
16212 KB |
Output is correct |
18 |
Correct |
191 ms |
15696 KB |
Output is correct |
19 |
Correct |
195 ms |
16976 KB |
Output is correct |
20 |
Correct |
182 ms |
16208 KB |
Output is correct |