Submission #932861

#	Time	Username	Problem	Language	Result	Execution time	Memory
932861		Wuskevo	Binaria (CCO23_day1problem1)	C++14	0 / 25	114 ms	19408 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], b[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();
	cin >> n >> k;
	for (int i=1; i<=n; i++) b[i] = -1;
	int m = n - k + 1;
	for (int i=1; i<=m; i++) cin >> a[i];
	int slots = 0, ones = a[1];
	bool posi = 1;
	for (int i=2; i<=m; i++) {
		int l = i-1, r = l+k;
		if (debug) cout << "index: " << i << " -> l: " << l << " r: " << r << "\n"; 
		if (abs(a[i] - a[i-1]) > 1) {
			if (debug) cout << "Impossible difference!" << "\n";
			posi = 0;
			break;
		}
		if (a[i-1] > a[i]) {
			// negative change
			// check if this doesn't contradict the array b
			if ((b[l] != -1 && b[l] != 1) || (b[r] != -1 && b[r] != 0)) {
				if (debug) cout << "negative contradiction!" << "\n";
				posi = 0;
				break;
			}
			b[l] = 1, b[r] = 0;
		}
		else if (a[i-1] < a[i]) {
			// positive change
			if ((b[l] != -1 && b[l] != 0) || (b[r] != -1 && b[r] != 1)) {
				if (debug) cout << "positive contradiction!" << "\n";
				posi = 0;
				break;
			}
			b[l] = 0, b[r] = 1;
		}
		else {
			// no change
			if ((b[l] != -1 && b[r] != -1) && b[l] != b[r]) {
				if (debug) cout << "neutral contradiction!" << "\n";
				posi = 0;
				break;  
			}
			if (b[r] == -1) b[r] = b[l];
			if (b[l] == -1) b[l] = b[r];
		}
	}
	
	if (debug) {
		cout << "B: ";
		for (int i=1; i<=n; i++) cout << b[i] << " ";
		cout << "\n";
	}
	
	if (!posi) {
		if (debug) cout << "impossible!\n";
		cout << 0 << "\n";
		return;
	} 
	
	for (int i=1; i<=k; i++) {
		if (b[i] == 1) ones--;
		if (b[i] == -1) slots++; 
	}
	
	if (debug) cout << "Empty slots: " << slots << " ones: " << ones << "\n";
	int ans = C(slots, 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