#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int main()
{
int n, d, m;
cin >> n >> d >> m;
int day[100000] = {};
vector<int> arr[n];
for (int i = 0; i < m; i++)
{
int a;
cin >> a;
day[a - 1]++;
arr[a - 1].push_back(i + 1);
}
int l = 0, r = m, mid = (l + r + 1) / 2;
while (l < r)
{
set<pair<int, int>> q;
bool f = true;
for (int i = 0; i < n; i++)
{
if (day[i] != 0)
{
q.insert({i, day[i]});
}
int a = mid;
while (a > 0 && q.begin() != q.end())
{
int b = min(a, (*q.begin()).second);
q.insert({(*q.begin()).first, (*q.begin()).second - b});
q.erase(++q.begin());
a -= b;
if ((*q.begin()).second == 0)
{
q.erase(q.begin());
}
}
if (q.begin() != q.end() && i - (*q.begin()).first == d)
{
f = false;
break;
}
}
if (f)
{
r = mid - 1;
mid = (l + r + 1) / 2;
}
else
{
l = mid;
mid = (l + r + 1) / 2;
}
}
mid++;
cout << mid << "\n";
set<pair<int, int>> q;
for (int i = 0; i < n; i++)
{
for (auto a : arr[i])
{
q.insert({i, a});
}
for (int a = 0; (a < mid && q.begin() != q.end()); a++)
{
cout << (*q.begin()).second << " ";
q.erase(q.begin());
}
cout << 0 << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
6860 KB |
Output is correct |
2 |
Correct |
31 ms |
6860 KB |
Output is correct |
3 |
Correct |
32 ms |
6824 KB |
Output is correct |
4 |
Correct |
31 ms |
6856 KB |
Output is correct |
5 |
Correct |
32 ms |
7040 KB |
Output is correct |
6 |
Correct |
32 ms |
6856 KB |
Output is correct |
7 |
Correct |
33 ms |
6976 KB |
Output is correct |
8 |
Correct |
31 ms |
6868 KB |
Output is correct |
9 |
Correct |
32 ms |
5204 KB |
Output is correct |
10 |
Correct |
38 ms |
5200 KB |
Output is correct |
11 |
Correct |
26 ms |
2384 KB |
Output is correct |
12 |
Correct |
55 ms |
4688 KB |
Output is correct |
13 |
Correct |
77 ms |
5972 KB |
Output is correct |
14 |
Correct |
143 ms |
9908 KB |
Output is correct |
15 |
Correct |
121 ms |
9044 KB |
Output is correct |
16 |
Correct |
169 ms |
11860 KB |
Output is correct |
17 |
Correct |
216 ms |
14156 KB |
Output is correct |
18 |
Correct |
204 ms |
14164 KB |
Output is correct |
19 |
Correct |
240 ms |
17492 KB |
Output is correct |
20 |
Correct |
207 ms |
14160 KB |
Output is correct |