oj.uz

Submission #967963

# Submission time Handle Problem Language Result Execution time Memory
967963 2024-04-23T06:08:00 Z pcc Binaria (CCO23_day1problem1) C++17
0 / 25
 13 ms 21852 KB 
#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+10;
const ll mod = 1e9+7;
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 -= K;
	while(p>=0&&val[p] == -1)val[p] = v;
	p = pp+K;
	while(p<N&&val[p] == -1)val[p] = v;
	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]){
			if(val[i] == 0){
				cout<<"0\n";
				return 0;
			}
			else val[i] = 1,val[i+K] = 0;
		}
		else if(arr[i]<arr[i+1]){
			if(val[i] == 1){
				cout<<"0\n";
				return 0;
			}
			else 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21848 KB Output is correct
2 Correct 11 ms 21852 KB Output is correct
3 Correct 13 ms 21852 KB Output is correct
4 Correct 11 ms 21852 KB Output is correct
5 Correct 12 ms 21852 KB Output is correct
6 Correct 12 ms 21704 KB Output is correct
7 Correct 12 ms 21688 KB Output is correct
8 Correct 12 ms 21852 KB Output is correct
9 Correct 12 ms 21852 KB Output is correct
10 Incorrect 12 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21848 KB Output is correct
2 Correct 11 ms 21852 KB Output is correct
3 Correct 13 ms 21852 KB Output is correct
4 Correct 11 ms 21852 KB Output is correct
5 Correct 12 ms 21852 KB Output is correct
6 Correct 12 ms 21704 KB Output is correct
7 Correct 12 ms 21688 KB Output is correct
8 Correct 12 ms 21852 KB Output is correct
9 Correct 12 ms 21852 KB Output is correct
10 Incorrect 12 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21848 KB Output is correct
2 Correct 11 ms 21852 KB Output is correct
3 Correct 13 ms 21852 KB Output is correct
4 Correct 11 ms 21852 KB Output is correct
5 Correct 12 ms 21852 KB Output is correct
6 Correct 12 ms 21704 KB Output is correct
7 Correct 12 ms 21688 KB Output is correct
8 Correct 12 ms 21852 KB Output is correct
9 Correct 12 ms 21852 KB Output is correct
10 Incorrect 12 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21848 KB Output is correct
2 Correct 11 ms 21852 KB Output is correct
3 Correct 13 ms 21852 KB Output is correct
4 Correct 11 ms 21852 KB Output is correct
5 Correct 12 ms 21852 KB Output is correct
6 Correct 12 ms 21704 KB Output is correct
7 Correct 12 ms 21688 KB Output is correct
8 Correct 12 ms 21852 KB Output is correct
9 Correct 12 ms 21852 KB Output is correct
10 Incorrect 12 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21848 KB Output is correct
2 Correct 11 ms 21852 KB Output is correct
3 Correct 13 ms 21852 KB Output is correct
4 Correct 11 ms 21852 KB Output is correct
5 Correct 12 ms 21852 KB Output is correct
6 Correct 12 ms 21704 KB Output is correct
7 Correct 12 ms 21688 KB Output is correct
8 Correct 12 ms 21852 KB Output is correct
9 Correct 12 ms 21852 KB Output is correct
10 Incorrect 12 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21848 KB Output is correct
2 Correct 11 ms 21852 KB Output is correct
3 Correct 13 ms 21852 KB Output is correct
4 Correct 11 ms 21852 KB Output is correct
5 Correct 12 ms 21852 KB Output is correct
6 Correct 12 ms 21704 KB Output is correct
7 Correct 12 ms 21688 KB Output is correct
8 Correct 12 ms 21852 KB Output is correct
9 Correct 12 ms 21852 KB Output is correct
10 Incorrect 12 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -