Submission #882933

#	Time	Username	Problem	Language	Result	Execution time	Memory
882933		tsumondai	Binaria (CCO23_day1problem1)	C++14	3 / 25	1 ms	6748 KiB

Main

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e6 + 5;

const int oo = 1e9, mod = 1e6 + 3;

int n, m, k, fact[N], inv[N], a[N], color[N];
string s;
vector<int> arr;

long long binpow(long long a, long long b) {
	a %= mod;
	long long res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int comb(int k, int n) {
	if (k > n || k < 0) return 0;
	return (fact[n] * ((inv[k] * inv[n - k]) % mod)) % mod;
}

void process() {
	cin >> n >> k;
	foru(i, 1, n - k + 1) cin >> a[i];
	fact[0] = inv[0] = 1;
	foru(i, 1, n) fact[i] = (fact[i - 1] * i) % mod;
	inv[n] = binpow(fact[n], mod - 2);
	ford(i, n - 1, 1) inv[i] = (inv[i + 1] * (i + 1)) % mod;
	foru(i, 1, n) color[i] = 2;
	ford(i, n - k, 1) {
		if (abs(a[i] - a[i + 1]) > 1) {
			cout << 0 << '\n'; return;
		}
		if (a[i] == a[i + 1]) color[i] = color[i + k];
		else if (a[i] > a[i + 1]) {
			if (color[i + k] == 1) {
				cout << 0 << '\n'; return;
			}
			color[i] = 1;
		} else {
			if (color[i + k] == 0) {
				cout << 0 << '\n'; return;
			}
			color[i] = 0;
		}

	}

	int ans = 0;
	foru(i, 1, k) a[1] -= (color[i] == 1), ans += color[i] == 2;
	cout << comb(a[1], ans);
	return;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	//freopen(".inp", "r", stdin);
	//freopen(".out", "w", stdout);
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

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