Submission #1287725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287725		muhammad-ahmad	Binaria (CCO23_day1problem1)	C++20	25 / 25	58 ms	15940 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

const int M = 1e6 + 3;

int bexp(int a, int b, int mod = M){
	int res = 1;
	a %= mod;
	while (b > 0){
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int mmi(int a, int mod = M){
	return bexp(a, mod - 2, mod);
}

void solve(){
	int n, k; cin >> n >> k;
	int T = 1, a[n - k + 2] = {};
	for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
	vector<int> ans(n + 1, -1);
	
	for (int i = 2; i <= n - k + 1; i++){
		if (a[i] - 1 > a[i - 1]){
			cout << 0 << endl;
			return;
		}
		if (a[i - 1] - 1 > a[i]){
			cout << 0 << endl;
			return;
		}
	}
	
	for (int i = 2; i <= n - k + 1; i++){
		if (a[i] > a[i - 1]) {
			ans[i - 1] = 0;
			ans[i + k - 1] = 1;
		}
		else if (a[i] < a[i - 1]){
			ans[i - 1] = 1;
			ans[i + k - 1] = 0;
		}
	}
	
	for (int i = n - k; i >= 1; i--){
		if (a[i] == a[i + 1]) ans[i] = ans[i + k];
	}
	
	for (int i = 2; i <= n - k + 1; i++){
		if (a[i] == a[i - 1]) ans[i + k - 1] = ans[i - 1];
	}
	
	// for (auto i : ans) cout << i << ' ';
	// cout << endl; 
	int N = 0, R = a[1];
	for (int i = 1; i <= k; i++){
		if (ans[i] == -1) N++;
		if (ans[i] == 1) R--;
	}
	
	int Nf = 1, nmrf = 1, rf = 1;
	
	for (int i = 1; i <= N; i++){
		Nf *= i;
		Nf %= M;
		if (i <= N - R){
			nmrf *= i;
			nmrf %= M;
		}
		if (i <= R){
			rf *= i;
			rf %= M;
		}
	}
	
	
	int x = Nf * mmi(nmrf);
	x %= M;
	x *= mmi(rf);
	x %= M;
	
	cout << x << endl;

}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tc = 1;
	// cin >> tc;
	while (tc--){
		solve();
	}
}

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