#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e6+2;
const ll mod = 1e6+3;
ll fac[mxn],ifac[mxn];
int arr[mxn];
int val[mxn];
ll N,K;
ll pw(ll a,ll b){
ll re = 1;
while(b){
if(b&1)re = re*a%mod;
b>>=1;
a = a*a%mod;
}
return re;
}
ll inv(ll k){
return pw(k,mod-2);
}
ll C(ll a,ll b){
if(b>a)return 0;
return fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
void check(int p,int v){
int pp = p;
p = pp-K;
while(p>=0&&val[p] == -1)val[p] = v,p -= K;
p = pp+K;
while(p<N&&val[p] == -1)val[p] = v,p += K;
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
fac[0] = ifac[0] = 1;
for(int i = 1;i<mxn;i++)fac[i] = fac[i-1]*i%mod;
ifac[mxn-1] = inv(fac[mxn-1]);
for(int i = mxn-2;i>=0;i--)ifac[i] = ifac[i+1]*(i+1)%mod;
cin>>N>>K;
for(int i = 0;i<N-K+1;i++){
cin>>arr[i];
}
for(int i = 0;i<N-K+1;i++){
if(arr[i]>K){
cout<<"0\n";
return 0;
}
}
memset(val,-1,sizeof(val));
for(int i = 0;i+1<N-K+1;i++){
if(abs(arr[i]-arr[i+1]) > 1){
cout<<"0\n";
return 0;
}
if(arr[i]>arr[i+1]){
val[i] = 1,val[i+K] = 0;
}
else if(arr[i]<arr[i+1]){
val[i] = 0,val[i+K] = 1;
}
}
for(int i = 0;i<N;i++){
if(val[i] != -1)check(i,val[i]);
}
for(int i = 0;i<N;i++)cout<<val[i]<<' ';cout<<endl;
for(int i = 0;i+1<N-K+1;i++){
if(arr[i]>arr[i+1]){
if(val[i] != 1||val[i+K] != 0){
cout<<"0\n";
return 0;
}
}
else if(arr[i]<arr[i+1]){
if(val[i] != 0||val[i+K] != 1){
cout<<"0\n";
return 0;
}
}
else{
if(val[i] != val[i+K]){
cout<<"0\n";
return 0;
}
}
}
int sum = 0,cnt = 0;
for(int i = 0;i<K;i++){
if(val[i] != -1)sum += val[i];
else cnt++;
}
if(sum>arr[0]||sum+cnt<arr[0]){
cout<<"0\n";
return 0;
}
cout<<C(cnt,arr[0]-sum)<<'\n';
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:79:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
79 | for(int i = 0;i<N;i++)cout<<val[i]<<' ';cout<<endl;
| ^~~
Main.cpp:79:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
79 | for(int i = 0;i<N;i++)cout<<val[i]<<' ';cout<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
