oj.uz

Submission #932844

# Submission time Handle Problem Language Result Execution time Memory
932844 2024-02-24T10:06:25 Z Wuskevo Binaria (CCO23_day1problem1) C++14
0 / 25
 120 ms 19156 KB 
// 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();
	if (debug) for (int i=1; i<=20; i++) {
		cout << i  << "! -> " << fact[i] << " inv: " << inv[i] << endl;
	}
	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 ones = 0, slots = k;
	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;
			}
			if (i < k) {
				slots--;
				ones++;
			}
			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;
			}
			if (i < k) {
				slots--;
			}
			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 (!posi) {
		if (debug) cout << "impossible!\n";
		cout << 0 << "\n";
		return;
	} 
	
	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.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 15972 KB Output is correct
2 Correct 116 ms 17100 KB Output is correct
3 Correct 120 ms 15992 KB Output is correct
4 Incorrect 113 ms 19156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 15972 KB Output is correct
2 Correct 116 ms 17100 KB Output is correct
3 Correct 120 ms 15992 KB Output is correct
4 Incorrect 113 ms 19156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 15972 KB Output is correct
2 Correct 116 ms 17100 KB Output is correct
3 Correct 120 ms 15992 KB Output is correct
4 Incorrect 113 ms 19156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 15972 KB Output is correct
2 Correct 116 ms 17100 KB Output is correct
3 Correct 120 ms 15992 KB Output is correct
4 Incorrect 113 ms 19156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 15972 KB Output is correct
2 Correct 116 ms 17100 KB Output is correct
3 Correct 120 ms 15992 KB Output is correct
4 Incorrect 113 ms 19156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 15972 KB Output is correct
2 Correct 116 ms 17100 KB Output is correct
3 Correct 120 ms 15992 KB Output is correct
4 Incorrect 113 ms 19156 KB Output isn't correct
5 Halted 0 ms 0 KB -