Submission #988175

#	Time	Username	Problem	Language	Result	Execution time	Memory
988175		Abdalaziz_Alshami	Binaria (CCO23_day1problem1)	C++17	0 / 25	19 ms	23896 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1,mod=1e6+3;
int fac[N],ifac[N],a[N];
int pxp(int x,int p)
{
	if(!p) return 1;
	if(p&1) return (x*pxp(x,p-1)%mod)%mod;
	int ret=pxp(x,p/2);
	return (ret*ret)%mod;
}
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%mod;
	ifac[N-1]=pxp(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--) ifac[i]=(ifac[i+1]*(i+1))%mod;
	int n,k; cin>>n>>k;
	int b[n-k+1]; for(int i=0;i<n-k+1;i++) cin>>b[i];
	memset(a,-1,sizeof a);
	for(int i=0;i<n-k;i++){
		if(a[i]==-1){
			if(b[i]>b[i+1]) a[i]=1,a[i+k]=0;
			else if(b[i]<b[i+1]) a[i]=0,a[i+k]=1;
		}
		else {
			if(b[i]==b[i+1]) a[i+k]=a[i];
			else if(b[i]>b[i+1]) a[i+k]=0;
			else a[i+k]=1;
		}
	}
	for(int i=n-k;i>0;i--){
		if(a[i+k-1]==1){
			if(b[i]==b[i-1]) a[i]=1;
			else if(b[i]>b[i-1]) a[i]=1;
		}
		else if(a[i+k-1]==0){
			if(b[i]==b[i-1]) a[i-1]=0;
			else if(b[i]<b[i-1]) a[i-1]=1;
		}
	}
	int s=0;
	for(int i=0;i<k;i++){
		if(a[i]==-1) s++;
		else if(a[i]) b[0]--;
	}
	cout<<(((ifac[b[0]]*ifac[s-b[0]])%mod)*fac[s])%mod;
}

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