Submission #932872

#	Time	Username	Problem	Language	Result	Execution time	Memory
932872		Wuskevo	Binaria (CCO23_day1problem1)	C++14	25 / 25	175 ms	37200 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=m-1; i>=1; i--) {
		int l = i, 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] > a[i+1] ){
			// we need r to be 0 and l = 1 to decrease the sum
            if ( b[r] == 1 ){
                posi = 0;
                break;
            }
            b[l] = 1;
        } 
		else if ( a[i] < a[i+1] ){
			// we need l to be 0 and r = 1 to increase the sum
            if ( b[r] == 0 ){
                posi = 0;
                break;
            }
            b[l] = 0;
        } 
		else {
            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: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7