Submission #887967

#	Time	Username	Problem	Language	Result	Execution time	Memory
887967		fanwen	Binaria (CCO23_day1problem1)	C++17	25 / 25	69 ms	19280 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);

const int Mod = 1e6 + 3;
const int MAX = 1e6 + 5;

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

int n, k, a[MAX];

namespace sub1 {
    bool check() {
        return n <= 10;
    }

    void solve() {
        int ans = 0;
        for (int mask = 0; mask < (1 << n); ++mask) {
            bool oke = true;
            int sum = 0;
            for (int i = 0; i < n; ++i) {
                sum += (mask >> i & 1);
                if(i >= k) sum -= (mask >> (i - k) & 1);
                if(i + 1 >= k) oke &= a[i + 1 - k] == sum;
            }
            ans += oke;
        }
        cout << ans; exit(0);
    }
}

namespace sub2 {
    bool check() {
        return n <= 1000 && k <= 10;
    }

    int dp[1005][1 << 10];

    void solve() {
        for (int mask = 0; mask < (1 << k); ++mask) {
            if(__builtin_popcount(mask) == a[0]) dp[0][mask] = 1;
        }

        for (int i = 0; i < n - k; ++i) {
            for (int mask = 0; mask < (1 << k); ++mask) {
                int m0 = (mask << 1) & ((1 << k) - 1);
                int m1 = (mask << 1 | 1) & ((1 << k) - 1);
                if(__builtin_popcount(m0) == a[i + 1]) add(dp[i + 1][m0], dp[i][mask]);
                if(__builtin_popcount(m1) == a[i + 1]) add(dp[i + 1][m1], dp[i][mask]);
            }
        }

        cout << accumulate(dp[n - k], dp[n - k] + (1 << k), 0LL) % Mod;
    }
}

namespace sub3 {

    int binpow(int n, int exp) {
        int ans = 1, mul = n;
        for (; exp; exp >>= 1) {
            if(exp & 1) ans = 1LL * ans * mul  % Mod;
            mul = 1LL * mul * mul % Mod;
        }
        return ans;
    }

    int color[MAX], lab[MAX];

    int find(int u) {
        return lab[u] < 0 ? u : lab[u] = find(lab[u]);
    }

    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        if(color[v] == -1) color[v] = color[u];
        return true;
    }

    int C(int k, int n) {
        int a = 1, b = 1;
        for (int i = n - k + 1; i <= n; ++i) {
             b = 1LL * b * (i - n + k) % Mod;
             a = 1LL * a * i % Mod;
        }
        return 1LL * a * binpow(b, Mod - 2) % Mod;
    }

    void solve() {
        fill(color, color + n + 1, -1);
        fill(lab, lab + n + 1, -1);

        for (int i = 0; i < n - k; ++i) {
            if(a[i] == a[i + 1]) {
                merge(i, i + k);
            } else if(a[i] > a[i + 1]) {
                color[find(i)] = 1, color[find(i + k)] = 0;
            } else {
                color[find(i)] = 0, color[find(i + k)] = 1;
            }
        }
        int m = a[0], cnt = 0;
        for (int i = 0; i < k; ++i) {
            int c = color[find(i)];
            if(c != -1) m -= c;
            else cnt++;
        }
        cout << C(m, cnt); exit(0);
    }
}

void you_make_it(void) {
    cin >> n >> k;
    for (int i = 0; i < n - k + 1; ++i) cin >> a[i];
    reverse(a, a + n - k + 1);
    sub3::solve();
    if(sub1::check()) sub1::solve();
    if(sub2::check()) sub2::solve();
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
  	file("CCO23_day1problem1");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:143:4: note: in expansion of macro 'file'
  143 |    file("CCO23_day1problem1");
      |    ^~~~
Main.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:143:4: note: in expansion of macro 'file'
  143 |    file("CCO23_day1problem1");
      |    ^~~~

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