Submission #381566

#	Time	Username	Problem	Language	Result	Execution time	Memory
381566		NONAME	Semafor (COI20_semafor)	C++17	6 / 100	4 ms	2540 KiB

semafor

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, const T b) {a = min(a, b); return (a == b);}
template <typename T> inline bool chmax(T& a, const T b) {a = max(a, b); return (a == b);}

const int base = (int)(1e9 + 7);
const int toMsk[10] = {10, 8, 18, 28, 9, 21, 6, 24, 23, 29};

int n, m, k, x;
int dp[2000][100];

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

inline void cls() {
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < 32; ++j) {
            dp[i][j] = 0;
        }
    }
}

int getNum(int msk) {
    int p = -1;
    for (int i = 0; i < 10; ++i) {
        if (toMsk[i] == msk) {
            assert(p == -1);
            p = i;
        }
    }
    return p;
}

int getMsk(int x) {
    return toMsk[x];
}

void solve() {
    cls();

    cin >> m >> n >> k >> x;
    if (m == 1) {
        dp[0][getMsk(x)] = 1;
        for (int i = 0; i < n; ++i) {
            if (((i + 1) % k) == 0) {
                for (int msk = 0; msk < 32; ++msk) {
                    for (int j = 0; j < 5; ++j) {
                        int nmsk = msk ^ (1 << j);
                        int p = getNum(nmsk);
                        if (p == -1) {
                            continue;
                        }
                        add(dp[i + 1][nmsk], dp[i][msk]);
                    }
                }
            } else {
                for (int msk = 0; msk < 32; ++msk) {
                    for (int j = 0; j < 5; ++j) {
                        int nmsk = msk ^ (1 << j);
                        add(dp[i + 1][nmsk], dp[i][msk]);
                    }
                }
            }
        }

        for (int j = 0; j < 10; ++j) {
            cout << dp[n][getMsk(j)] << "\n";
        }
    } else {
        assert(0);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    #ifdef _LOCAL
        system("color a");
        freopen("in.txt", "r", stdin);
        cin >> t;
    #endif

    for (int i = 1; i <= t; ++i) {
        cerr << "Case #" << i << ": \n";
        solve();
        cerr << "\n";
    }

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 15
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40