Submission #968044

#	Time	Username	Problem	Language	Result	Execution time	Memory
968044		weakweakweak	Binaria (CCO23_day1problem1)	C++17	25 / 25	211 ms	35428 KiB

Main

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

const int M = 1000000 + 3, N = 1e6 + 10;
int a[N], ch[N], fa[N], dp[N] = {0}, fac[N], invfac[N];

int find (int x) {
    return fa[x] == x ? x : fa[x] = find (fa[x]);
}

void add (int &x, int y) {
    x += y;
    if (x >= M) x -= M;
    if (x < 0) x += M;
}

void merge (int i, int j) {
    i = find(i), j = find(j);
    if (i == j) return;
    fa[i] = j;
    if (ch[i] == 3 or ch[j] == 3) ch[j] = min(ch[i], ch[j]);
    else if (ch[i] != ch[j]) {
        cout << "0\n";
        exit(0);
    }
}

void f(int i, int val) {
    i = find(i);
    if (ch[i] == 3) ch[i] = val;
    else if (ch[i] != val) {
        cout << "0\n";
        exit(0);
    }
}

int fmul (int x, int t) {
    if (t == 0) return 1;
    long long y = fmul(x, t / 2);
    y = y * y % M;
    if (t & 1) y = y * x % M;
return y;}

int nCr (int x, int y) {
    return fac[x] * 1LL * invfac[y] % M * invfac[x - y] % M;
}

signed main () {

    fac[0] = 1;
    for (int i = 1; i <= 1000000; i++) fac[i] = fac[i - 1] * 1LL  * i % M;
    invfac[1000000] = fmul(fac[1000000], M - 2);
    for (int i = 999999; i >= 0; i--) invfac[i] = invfac[i + 1] * (i + 1LL) % M; 

    // cout << invfac[999999] * 1LL * fac[999999] % M<< '\n';
    // cout << fac[5] << ' ' << nCr(5, 3) << '\n';return 0;

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) fa[i] = i, ch[i] = 3;
    for (int i = 1; i + k - 1 <= n; i++) cin >> a[i];
    for (int i = 2; i + k - 1 <= n; i++) {
        int dif = a[i] - a[i - 1];
        if (dif == 0) merge(i - 1, i + k - 1);
        else if (dif == 1) f(i + k - 1, 1), f(i - 1, 0);
        else f(i + k - 1, 0), f(i - 1, 1);
    }

    int left = a[1], wow = 0;
    for (int i = 1; i <= k; i++) {
        if (ch[find(i)] == 3) wow++;
        else if (ch[find(i)] == 1) {
            left--;
        }
    }

    cout << nCr (wow, left) << '\n';
}

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