Submission #1309123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309123		nanaseyuzuki	Binaria (CCO23_day1problem1)	C++20	25 / 25	96 ms	31744 KiB

Main

#include <bits/stdc++.h>
// Kazusa_Megumi
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
using namespace std;

const int mn = 1e6 + 5, lg2 = 20, mbit = (1 << 20) + 1, mm = 5e3 + 5, mod = 1e6 + 3;
const double inf = 1e9;

int n, k, a[mn], par[mn], sz[mn], c[mn];

void init(){
	for(int i = 1; i <= n; i++){
		c[i] = -1;
		par[i] = i, sz[i] = 1;
	}
}

int find(int u){
	if(u == par[u]) return u;
	return par[u] = find(par[u]);
}

void join(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return;
	if(sz[u] < sz[v]) swap(u, v);
	sz[u] += sz[v], par[v] = u;
	c[u] = max(c[v], c[u]);
}

int mu(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}

void solve(){
	cin >> n >> k;
	for(int i = 1; i <= n - k + 1; i ++) cin >> a[i];
	init();
	for(int i = n - k; i >= 1; i--){
		if(a[i] == a[i + 1]) join(i, i + k);
		else{
			if(a[i] > a[i + 1]){
				c[find(i)] = 1;
				c[find(i + k)] = 0;
			}
			else{
				c[find(i)] = 0;
				c[find(i + k)] = 1;
			}
		}
	}
	int sum = a[1], num = 0;
	for(int i = 1; i <= k; i ++){
		if(c[find(i)] != -1) sum -= c[find(i)];
		else num ++;
	}
	int res = 1;
	for(int i = 1; i <= num; i++) res = (res * i) % mod;
	for(int i = 1; i <= sum; i++) res = (res * mu(i, mod - 2)) % mod;
	for(int i = 1; i <= num - sum; i++) res = (res * mu(i, mod - 2)) % mod;
	cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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