Submission #381572

#	Time	Username	Problem	Language	Result	Execution time	Memory
381572		NONAME	Semafor (COI20_semafor)	C++17	18 / 100	48 ms	24812 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 dp1[2000][100], dp2[2000][100][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) {
            dp1[i][j] = 0;
        }
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < 32; ++j) {
            for (int l = 0; l < 32; ++l) {
                dp2[i][j][l] = 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) {
        assert(n <= 12);
        dp1[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(dp1[i + 1][nmsk], dp1[i][msk]);
                    }
                }
            } else {
                for (int msk = 0; msk < 32; ++msk) {
                    for (int j = 0; j < 5; ++j) {
                        int nmsk = msk ^ (1 << j);
                        add(dp1[i + 1][nmsk], dp1[i][msk]);
                    }
                }
            }
        }

        for (int j = 0; j < 10; ++j) {
            cout << dp1[n][getMsk(j)] << "\n";
        }
    } else {
        assert(n <= 1500);
        dp2[0][getMsk(x / 10)][getMsk(x % 10)] = 1;
        for (int i = 0; i < n; ++i) {
            if (((i + 1) % k) == 0) {
                for (int msk1 = 0; msk1 < 32; ++msk1) {
                    for (int msk2 = 0; msk2 < 32; ++msk2) {
                        for (int j = 0; j < 5; ++j) {
                            int nmsk, p1, p2;
                            nmsk = msk1 ^ (1 << j);
                            p1 = getNum(nmsk), p2 = getNum(msk2);
                            if ((p1 != -1) && (p2 != -1)) {
                                add(dp2[i + 1][nmsk][msk2], dp2[i][msk1][msk2]);
                            }
                            nmsk = msk2 ^ (1 << j);
                            p1 = getNum(msk1), p2 = getNum(nmsk);
                            if ((p1 != -1) && (p2 != -1)) {
                                add(dp2[i + 1][msk1][nmsk], dp2[i][msk1][msk2]);
                            }
                        }
                    }
                }
            } else {
                for (int msk1 = 0; msk1 < 32; ++msk1) {
                    for (int msk2 = 0; msk2 < 32; ++msk2) {
                        for (int j = 0; j < 5; ++j) {
                            int nmsk;
                            nmsk = msk1 ^ (1 << j);
                            add(dp2[i + 1][nmsk][msk2], dp2[i][msk1][msk2]);
                            nmsk = msk2 ^ (1 << j);
                            add(dp2[i + 1][msk1][nmsk], dp2[i][msk1][msk2]);
                        }
                    }
                }
            }
        }
        for (int j = 0; j < 100; ++j) {
            cout << dp2[n][getMsk(j / 10)][getMsk(j % 10)] << "\n";
        }
    }
}

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: 12 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40