#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define f first
#define s second
const int MX = 1e5+5;
int n, d, m;
vector<pair<int,int>> v;
bool check(int machines){
int currDay = v[0].f;
vector<int> filled(MX, 0);
for(int i=0; i<m; i++){
currDay = max(currDay, v[i].f);
if(filled[currDay]>=machines) currDay++;
if(currDay-d>v[i].f) return false;
filled[currDay]++;
}
return true;
}
int firstTrue(int lo, int hi) {
hi++;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
int main(){
cin>>n>>d>>m;
for(int i=0; i<m; i++){
int x; cin>>x;
v.push_back({x, i});
}
sort(begin(v), end(v));
int req = firstTrue(1, MX);
cout<<req<<endl;
vector<int> ans[MX];
int currDay = 0;
for(int i=0; i<m; i++){
currDay = max(currDay, v[i].f);
int sz = ans[currDay].size();
if(sz>=req){
currDay++;
}
ans[currDay].push_back(v[i].s);
}
for(int i=1; i<=n; i++){
for(int val: ans[i]){
cout<<val+1<<" ";
}
cout<<0<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
4680 KB |
Output is correct |
2 |
Correct |
57 ms |
4600 KB |
Output is correct |
3 |
Correct |
53 ms |
4592 KB |
Output is correct |
4 |
Correct |
54 ms |
4664 KB |
Output is correct |
5 |
Correct |
55 ms |
4568 KB |
Output is correct |
6 |
Correct |
54 ms |
4680 KB |
Output is correct |
7 |
Correct |
57 ms |
4596 KB |
Output is correct |
8 |
Correct |
57 ms |
4620 KB |
Output is correct |
9 |
Correct |
192 ms |
4828 KB |
Output is correct |
10 |
Correct |
175 ms |
4964 KB |
Output is correct |
11 |
Correct |
61 ms |
4436 KB |
Output is correct |
12 |
Correct |
106 ms |
6448 KB |
Output is correct |
13 |
Correct |
160 ms |
9112 KB |
Output is correct |
14 |
Correct |
240 ms |
11272 KB |
Output is correct |
15 |
Correct |
253 ms |
11864 KB |
Output is correct |
16 |
Correct |
368 ms |
14236 KB |
Output is correct |
17 |
Correct |
401 ms |
18100 KB |
Output is correct |
18 |
Correct |
445 ms |
18440 KB |
Output is correct |
19 |
Correct |
603 ms |
20268 KB |
Output is correct |
20 |
Correct |
418 ms |
18120 KB |
Output is correct |