Submission #932810

#	Time	Username	Problem	Language	Result	Execution time	Memory
932810		Wuskevo	Binaria (CCO23_day1problem1)	C++14	0 / 25	121 ms	17492 KiB

Main

// Do easier subtasks for ALL problems in IO when stuck for too long
// Don't do nothing, do something, you can do it! :)
// Try a different approach, check every approach if feasible
// Don't overthink, don't panic, clear your mind

#include<bits/stdc++.h>
#define fastcincout ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define pri priority_queue
#define str string
#define int long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pu push_back
#define po pop_back
#define all(v) v.begin(), v.end()
#define MOD 1000003

using namespace std;
const int N=1e6+5;
bool debug=0;

int n, k;
int fact[N], inv[N], a[N];

int mult(int x, int y) {
	return (x*y)%MOD;
}

int pang(int x, int y) {
	if (y == 0) return 1;
	int t = pang(x, y/2);
	t = mult(t, t);
	if (y&1) return mult(t, x);
	return t;
}

void prec() {
	fact[0] = 1;
	inv[0] = 1;
	for (int i=1; i<=N-5; i++) {
		fact[i] = mult(fact[i-1], i);
		inv[i] = pang(fact[i], MOD-2);
	}
}

int C(int M, int R) {
	if (R < 0) return 0; // impossible
	if (R > M) return 0;
	return mult(fact[M], mult(inv[R], inv[M-R]));
}

void solve() {
	prec();
	if (debug) for (int i=1; i<=20; i++) {
		cout << i  << "! -> " << fact[i] << " inv: " << inv[i] << endl;
	}
	cin >> n >> k;
	int m = n - k + 1;
	for (int i=1; i<=m; i++) cin >> a[i];
	int ones = 0, slots = k;
	for (int i=2; i<=min(m, k); i++) {
		if (abs(a[i] - a[i-1]) > 1) {
			cout << 0 << "\n";
			return;
		}
		if (a[i] > a[i-1]) {
			slots--;
			continue;
		}
		if (a[i] < a[i-1]) {
			slots--;
			ones++;
			continue;
		}
	}
	int ans = 0;
	if (debug) cout << "Empty slots: " << slots << " ones: " << ones << "\n";
	if (m == k) {
		// there is one ambiguous digit
		// so check
		if (debug) cout << "Ambiguous!" << "\n"; 
		slots--;
		int tmp1 = C(slots, a[1]-ones), tmp2 = C(slots, a[1]-ones-1);
		if (debug) cout << "+C(" << slots << ", " << a[1]-ones << ") -> " << tmp1 << "\n";
		if (debug) cout << "+C(" << slots << ", " << a[1]-ones-1 << ") -> " << tmp2 << "\n";
		ans += tmp1 + tmp2;
	}
	else {
		// every digit has a pair
		if (debug) cout << "All clear!" << "\n";
		ans += C(slots, a[1]-ones);
	}
	cout << ans << "\n";
}

signed main() {
	// freopen("Input.in", "r", stdin);
	// freopen("Output.out", "w", stdout);
	// freopen must have the file in the same folder as the code file
	fastcincout;
	int testcases=1;
	// cin >> testcases;
	while(testcases--)
	{
	    solve();
 	}
	return 0;
}

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