Submission #865748

#	Time	Username	Problem	Language	Result	Execution time	Memory
865748		_hbk06	Binaria (CCO23_day1problem1)	C++14	0 / 25	12 ms	12912 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask >> (x)) & 1)
#define TASK "task"

using namespace std;
const int mxN = 1e6 + 7;
const int base = 512;
const int inf = 1e9 + 6969;
const int Mod = 1e6 + 3;
const long long infll = 1e18 + 6969;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
     if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
     if (a < b) {a = b; return true;} return false;
}

struct MST {
	int n;
	vector<int>par;
	MST(int _n) {
		n = _n;
		par.assign(n + 2,-1);
	}

	int get_root(int u) {
		if(par[u] < 0) return u;
		return par[u] = get_root(par[u]);
	}

	void merge(int u,int v) {
		u = get_root(u);
		v = get_root(v);
		if(u == v) return;
		if(par[u] > par[v]) swap(u,v);
		par[u] += par[v];
		par[v] = u;
	}
};

int n;
int k;
int a[mxN];
int bit[mxN];
int adj[mxN];
int frac[mxN];

int Pow(int n,int k) {
    if(k == 1) return n % Mod;
    ll tmp = Pow(n,(k >> 1)) % Mod;
    tmp = (tmp * tmp) % Mod;
    if(k & 1) tmp = (tmp * n) % Mod;
    return tmp;
}

void fractorize() {
    frac[0] = 1;
    for(int i = 1;i < mxN;i++)
        frac[i] = (1LL * frac[i - 1] * i) % Mod;
    adj[mxN - 1] = Pow(frac[mxN - 1],Mod - 2);
    for(int i = mxN - 1;i > 0;i--)
        adj[i - 1] = (1LL * adj[i] * i) % Mod;
}

int Ckn(int k,int n) {
    if(k > n) return 0LL;
    return 1LL * (frac[n] * adj[k] % Mod * adj[n - k] % Mod);
}

void solve() {
	cin >> n >> k;
	fractorize();
	for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
	memset(bit,-1,sizeof bit);
	MST dsu(n + 2);
	for (int i = 1; i <= n - k; i++) {
		if(a[i] < a[i + 1]) {
			int u = dsu.get_root(i);
			int v = dsu.get_root(i + k);
			bit[u] = 0;
			bit[v] = 1;
		}
		if(a[i] > a[i + 1]) {
			int u = dsu.get_root(i);
			int v = dsu.get_root(i + k);
			bit[u] = 1;
			bit[v] = 0;
		}
		else dsu.merge(i,i + k);
	}
	int cnt = 0;
	for (int i = 1; i <= k; i++) {
		int u = dsu.get_root(i);
		if(bit[u] < 0) cnt++;
		else a[1] -= bit[u];
	}
	cout << Ckn(a[1],cnt) << "\n";
}

signed main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	//freopen(TASK".inp","r",stdin);
	//freopen(TASK".out","w",stdout);
	int tc = 1;
	//cin >> tc;
	while(tc--) {
		solve();
	}
}

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