oj.uz

Submission #988269

# Submission time Handle Problem Language Result Execution time Memory
988269 2024-05-24T11:56:15 Z Abdalaziz_Alshami Binaria (CCO23_day1problem1) C++17
0 / 25
 19 ms 23900 KB 
#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);
	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;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;
	if(f) { cout<<0<<endl; return 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.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23896 KB Output is correct
2 Correct 19 ms 23900 KB Output is correct
3 Incorrect 17 ms 23900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23896 KB Output is correct
2 Correct 19 ms 23900 KB Output is correct
3 Incorrect 17 ms 23900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23896 KB Output is correct
2 Correct 19 ms 23900 KB Output is correct
3 Incorrect 17 ms 23900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23896 KB Output is correct
2 Correct 19 ms 23900 KB Output is correct
3 Incorrect 17 ms 23900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23896 KB Output is correct
2 Correct 19 ms 23900 KB Output is correct
3 Incorrect 17 ms 23900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23896 KB Output is correct
2 Correct 19 ms 23900 KB Output is correct
3 Incorrect 17 ms 23900 KB Output isn't correct
4 Halted 0 ms 0 KB -