Submission #1293092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293092		mingga	Binaria (CCO23_day1problem1)	C++20	25 / 25	125 ms	66976 KiB

Main

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e6 + 3;
const int inf = 2e9;
const int N = 1e6 + 7;

int n, k;
int a[N], val[N];

vector<int> grp[N];

int mul(int x, int y) {
    return (1ll * x * y) % mod;
}

int power(int x, int y) {
    int ans = 1;
    while(y > 0) {
        if(y & 1) ans = mul(ans, x);
        y >>= 1;
        x = mul(x, x);
    }
    return ans;
}

int nCk(int n, int k) {
    if(n < k) return 0;
    int ans = 1, ext = 1;
    for(int i = k + 1; i <= n; i++) {
        ans = mul(ans, i);
        ext = mul(ext, n - i + 1);
    }
    return mul(ans, power(ext, mod - 2));
}
struct DSU {
    vector<int> par, sz;
    DSU(int n) {
        par.resize(n + 1, 0);
        sz.resize(n + 1, 1);
        for(int i = 1; i <= n; i++) par[i] = i;
    }
    int find(int u) {
        return u == par[u] ? u : 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);
        par[v] = u;
        sz[u] += sz[v];
    }
};

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    #define task ""
    if(fopen(task ".INP", "r")) {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    cin >> n >> k;
    for(int i = 1; i <= n - k + 1; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n - k + 1; i++) {
        if(a[i] > k) {
            cout << 0 << ln;
            return 0;
        }
    }
    DSU d(n);
    memset(val, -1, sizeof val);
    for(int i = k + 1, j = 2; i <= n; i++, j++) {
        if(abs(a[j] - a[j - 1]) > 1) {
            cout << 0 << ln;
            return 0;
        }
        if(a[j] == a[j - 1]) {
            d.join(i, i - k);
        } else if(a[j] > a[j - 1]) {
            val[i] = 1;
            if(val[i - k] == 1) {
                cout << 0 << ln;
                return 0;
            }
            val[i - k] = 0;
        } else {
            val[i] = 0;
            if(val[i - k] == 0) {
                cout << 0 << ln;
                return 0;
            }
            val[i - k] = 1;
        }
    }
    for(int i = 1; i <= n; i++) {
        grp[d.find(i)].pb(i);
    }
    for(int i = 1; i <= n; i++) {
        if(sz(grp[i]) == 0) continue;
        int comm = -1;
        for(int x : grp[i]) {
            if(val[x] != -1) {
                if(comm != -1 and comm != val[x]) {
                    cout << 0 << ln;
                    return 0;
                }
                if(comm == -1) comm = val[x];               
            }
        }
        for(int x : grp[i]) val[x] = comm;
    }
    int cur = k;
    int cnt1 = a[1];
    for(int i = 1; i <= k; i++) {
        if(val[i] != -1) cur--;
        if(val[i] == 1) cnt1--;
    }
    cout << nCk(cur, cnt1) << ln;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(task ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(task ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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