Submission #988309

#	Time	Username	Problem	Language	Result	Execution time	Memory
988309		Abdalaziz_Alshami	Binaria (CCO23_day1problem1)	C++17	25 / 25	87 ms	36556 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1,mod=1e6+3;
int fac[N+1],ifac[N+1],a[N+1];
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);
	bool f=false;
	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(a[i]==1){
			if(b[i]==b[i+1]) a[i+k]=a[i];
			else if(b[i]>b[i+1]) a[i+k]=0;
			else f=true;
		}
		else {
			if(b[i]==b[i+1]) a[i+k]=a[i];
			else if(b[i]<b[i+1]) a[i+k]=1;
			else f=true;
		}
	}
	for(int i=n-k-1;i>=0;i--){
		if(a[i+k]==1){
			if(b[i]==b[i+1]) a[i]=1;
			else if(b[i]<b[i+1]) a[i]=0;
		}
		else if(a[i+k]==0){
			if(b[i]==b[i+1]) a[i]=0;
			else if(b[i]<b[i+1]) a[i]=1;
		}
	}
	int s=0;
	for(int i=0;i<k;i++){
		if(a[i]==-1) s++;
		else if(a[i]) b[0]--;
	}
	if(f) { cout<<0<<endl; return 0; }
	if(s==b[0]) { cout<<1<<endl; return 0; } 
	if(s<b[0]) { cout<<0<<endl; return 0; }
	int x=ifac[b[0]]*ifac[s-b[0]];
	x*=fac[s];
	cout<<x%mod<<endl;
}

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