#ifdef LOCAL
//#include "librerie locali/debugging.h"
#else
#pragma GCC optimize("Ofast,unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
#define reps(i,j,x) for(int i=(j);i<(x);i++)
#define repp(i,x) for(int i = 1; i <= (x); i++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define maxint numeric_limits<int>::max()
#define minint numeric_limits<int>::min()
#define maxll numeric_limits<ll>::max()
#define minll numeric_limits<ll>::min()
#define nl '\n'
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef array<int, 3> i3;
typedef array<ll, 3> ll3;
typedef array<int, 4> i4;
typedef array<ll, 4> ll4;
typedef vector<i3> vi3;
typedef vector<ll3> vll3;
typedef vector<i4> vi4;
typedef vector<ll4> vll4;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
int nxt() {int x;cin >> x;return x;}
template <class T> void make_unique(T &arr) {sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());}
void print(){cout<<endl;} template <typename T, typename... Types> void print(T var1, Types... var2) {cout<<var1<<" ";print(var2...);}
template <typename T> T maxm(T var) {return var;} template <typename T, typename... Types> T maxm(T var1, Types... var2) {return max(var1,maxm(var2...));}
template <typename T> T minm(T var) {return var;} template <typename T, typename... Types> T minm(T var1, Types... var2) {return min(var1,minm(var2...));}
ll lpow(ll base, ll exp){ll result = 1;for (;;){if (exp & 1)result *= base;exp >>= 1;if (!exp)break;base *= base;}return result;}
int log2_floor(unsigned long long i) {return i ? __builtin_clzll(1) - __builtin_clzll(i) : 0;}
template <typename T> T maxv(vector<T> &var) {T maxi=numeric_limits<T>::min();for(auto x : var)maxi=max(maxi,x);return maxi;}
template <typename T> T minv(vector<T> &var) {T mini=numeric_limits<T>::max();for(auto x : var)mini=min(mini,x);return mini;}
void solve();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("shuffle.in", "r", stdin);
#endif
//freopen("shuffle.out", "w", stdout);
int t=1;
//cin>>t;
rep(i,t)solve();
}
void solve(){
int n,s,m;
cin>>n>>s>>m;
vpi arr(m);
rep(i,m){
cin>>arr[i].f;
arr[i].s=i+1;
}
sort(all(arr));
auto f = [&](int x){
int cur = 1;
bool ok = true;
rep(i,m){
int d = 0;
if(arr[i].f+s<cur){
ok=false;
break;
}
while(d+i<m&&d<x&&arr[i+d].f<=cur)d++;
i+=max(d-1,0);
if(i+1<m)cur=max(cur+1,arr[i+1].f);
}
return ok;
};
int x = 0;
for(int i = 1e9;i>0;i/=2){
while(!f(x+i))x+=i;
}
x++;
cout<<x<<nl;
int cur = 1;
rep(i,m){
int d = 0;
while(d+i<m&&d<x&&arr[i+d].f<=cur){
cout<<arr[i+d].s<<" ";
d++;
}
cout<<"0"<<nl;
i+=max(d-1,0);
if(i+1<m){
cur++;
while(cur<arr[i+1].f){
cout<<0<<nl;
cur++;
}
}
}
while(cur<n){cout<<0<<nl;cur++;}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1624 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1624 KB |
Output is correct |
| 5 |
Correct |
15 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
15 ms |
1628 KB |
Output is correct |
| 7 |
Correct |
15 ms |
1628 KB |
Output is correct |
| 8 |
Correct |
15 ms |
1628 KB |
Output is correct |
| 9 |
Correct |
26 ms |
2012 KB |
Output is correct |
| 10 |
Correct |
26 ms |
1884 KB |
Output is correct |
| 11 |
Correct |
21 ms |
1624 KB |
Output is correct |
| 12 |
Correct |
42 ms |
3152 KB |
Output is correct |
| 13 |
Correct |
67 ms |
4604 KB |
Output is correct |
| 14 |
Correct |
90 ms |
6224 KB |
Output is correct |
| 15 |
Correct |
110 ms |
7764 KB |
Output is correct |
| 16 |
Correct |
134 ms |
9236 KB |
Output is correct |
| 17 |
Correct |
158 ms |
10536 KB |
Output is correct |
| 18 |
Correct |
173 ms |
12100 KB |
Output is correct |
| 19 |
Correct |
201 ms |
13856 KB |
Output is correct |
| 20 |
Correct |
156 ms |
10580 KB |
Output is correct |
