Submission #967973

#	Time	Username	Problem	Language	Result	Execution time	Memory
967973		pcc	Binaria (CCO23_day1problem1)	C++17	25 / 25	77 ms	24000 KiB

Main

#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+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;
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7