Submission #968067

#	Time	Username	Problem	Language	Result	Execution time	Memory
968067		becaido	Binaria (CCO23_day1problem1)	C++17	25 / 25	87 ms	20192 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int MOD = 1e6 + 3;
const int SIZE = 1e6 + 5;

int n, k;
int a[SIZE];

int pro[SIZE], inv[SIZE];
int power(int d, int up) {
    int re = 1;
    while (up) {
        if (up & 1) re = 1ll * re * d % MOD;
        d = 1ll * d * d % MOD;
        up >>= 1;
    }
    return re;
}
int C(int x, int y) {
    return 1ll * pro[x] * inv[y] % MOD * inv[x - y] % MOD;
}

int to[SIZE], ty[SIZE];
int dsu(int x) {
    return x == to[x] ? x : (to[x] = dsu(to[x]));
}
void merge(int a, int b) {
    a = dsu(a), b = dsu(b);
    if (a == b) return;
    to[b] = a;
    ty[a] |= ty[b];
}

void solve() {
    cin >> n >> k;
    FOR (i, k, n) cin >> a[i];
    iota(to + 1, to + n + 1, 1);

    pro[0] = 1;
    FOR (i, 1, n) pro[i] = 1ll * pro[i - 1] * i % MOD;
    inv[n] = power(pro[n], MOD - 2);
    for (int i = n; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % MOD;

    FOR (i, k, n - 1) {
        if (a[i] == a[i + 1]) merge(i - k + 1, i + 1);
        if (a[i] + 1 == a[i + 1]) {
            ty[dsu(i - k + 1)] = 1;
            ty[dsu(i + 1)] = 2;
        }
        if (a[i] - 1 == a[i + 1]) {
            ty[dsu(i - k + 1)] = 2;
            ty[dsu(i + 1)] = 1;
        }
    }

    int c[3] = {};
    FOR (i, 1, k) c[ty[dsu(i)]]++;
    cout << C(c[0], a[k] - c[2]) << '\n';
}

int main() {
    Waimai;
    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