/*
Code by @marlov
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<long long,long long> pi;
#define maxN 100005
long long N,D,M;
vector<long long> arr[maxN];
vector<long long> ans;
bool solve(long long num){
priority_queue< pair<long long,long long> , vector< pair<long long,long long> > , greater< pair<long long,long long> > > pq;
for(long long i=0;i<N;i++){
long long cc=num;
pq.push(make_pair(i,arr[i].size()));
while(!pq.empty()&&cc>0){
if(pq.top().first<i-D) return false;
if(pq.top().second<=cc){
cc-=pq.top().second;
pq.pop();
}else if(pq.top().second>cc){
pair<long long,long long> cur=pq.top();pq.pop();
cur.second-=cc;
pq.push(cur);
cc=0;
}
}
}
if(pq.size()>0) return false;
return true;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>D>>M;
long long num;
for(long long i=0;i<M;i++){
cin>>num;
num--;
arr[num].push_back(i);
}
long long a=0;
long long b=1000000;
while(a!=b){
long long mid=(a+b+1)/2;
if(solve(mid)){
b=mid-1;
}else{
a=mid+1;
}
//cout<<a<<" "<<mid<<" "<<b<<endl;
}
a=b+1;
for(long long i=0;i<N;i++){
for(long long j=0;j<arr[i].size();j++){
ans.push_back(arr[i][j]);
}
}
cout<<a<<'\n';
long long ci=0;
for(long long i=0;i<N;i++){
for(long long j=0;j<a;j++){
if(ci==ans.size()) break;
cout<<ans[ci]+1<<" ";
ci++;
}
cout<<0<<endl;
}
return 0;
}
/* stuff you should look for
* long long overflow, array bounds
* special cases (n=1,n=0?)
* do smth instead of nothing and stay organized
*/
Compilation message
jobs.cpp: In function 'int main()':
jobs.cpp:75:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(long long j=0;j<arr[i].size();j++){
| ~^~~~~~~~~~~~~~
jobs.cpp:83:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if(ci==ans.size()) break;
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
4984 KB |
Output isn't correct |
| 2 |
Incorrect |
42 ms |
4984 KB |
Output isn't correct |
| 3 |
Incorrect |
42 ms |
4984 KB |
Output isn't correct |
| 4 |
Incorrect |
45 ms |
5112 KB |
Output isn't correct |
| 5 |
Incorrect |
42 ms |
4984 KB |
Output isn't correct |
| 6 |
Incorrect |
42 ms |
4984 KB |
Output isn't correct |
| 7 |
Incorrect |
42 ms |
4984 KB |
Output isn't correct |
| 8 |
Incorrect |
43 ms |
4984 KB |
Output isn't correct |
| 9 |
Incorrect |
272 ms |
5756 KB |
Output isn't correct |
| 10 |
Incorrect |
247 ms |
5616 KB |
Output isn't correct |
| 11 |
Incorrect |
27 ms |
5364 KB |
Output isn't correct |
| 12 |
Incorrect |
44 ms |
7656 KB |
Output isn't correct |
| 13 |
Incorrect |
65 ms |
11620 KB |
Output isn't correct |
| 14 |
Incorrect |
124 ms |
13792 KB |
Output isn't correct |
| 15 |
Correct |
106 ms |
16096 KB |
Output is correct |
| 16 |
Execution timed out |
1054 ms |
10488 KB |
Time limit exceeded |
| 17 |
Correct |
229 ms |
23124 KB |
Output is correct |
| 18 |
Incorrect |
182 ms |
23388 KB |
Output isn't correct |
| 19 |
Incorrect |
397 ms |
25060 KB |
Output isn't correct |
| 20 |
Correct |
200 ms |
23252 KB |
Output is correct |
