Submission #1225647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225647		ashraful_alam	Binaria (CCO23_day1problem1)	C++20	25 / 25	106 ms	15944 KiB

Main

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

typedef long long ll;

const ll M = 1e6 + 3;

ll binpow(ll a, ll b) {
	if (b == 0) return 1;
	ll x = binpow(a, b/2);
	x = (x * x) % M;
	if (b & 1) x = (x * a) % M;
	return x;
}

ll nCr(ll n, ll r) {
	if (r > n || n < 0 || r < 0) return 0;
	ll ans = 1;
	for (int i = r + 1; i <= n; i++) ans = ans * i % M;
	for (int i = 1; i <= n - r; i++) ans = ans * binpow(i, M - 2) % M;
	return ans;
}

void solve() {
	//write your code here...
	ll n, k; cin >> n >> k;
	vector<ll> a(n - k + 2), x(n + 1, -1);
	for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
	for (int i = 2; i <= n - k + 1; i++) {
		if (abs(a[i] - a[i - 1]) > 1) {
			cout << "0\n";
			return;
		}
	}
	for (int i = 2; i <= n - k + 1; i++) {
		if (a[i] - a[i - 1] == 1) x[i - 1 + k] = 1, x[i - 1] = 0;
		else if (a[i] - a[i - 1] == -1) x[i - 1 + k] = 0, x[i - 1] = 1;
		else x[i - 1 + k] = x[i - 1];
	}
	for (int i = n - k; i >= 1; i--) {
		if (a[i] == a[i + 1]) x[i] = x[i + k];
	}
	int free = 0;
	for (int i = 1; i <= k; i++) {
		free += (x[i] == -1);
		a[1] -= (x[i] == 1);
	}
	cout << nCr(free, a[1]) << '\n';
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	ll T = 1;
	//cin >> T;
	while (T--) {
		solve ();
	}
	return 0;
}

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