oj.uz

Submission #381572

# Submission time Handle Problem Language Result Execution time Memory
381572 2021-03-25T10:10:48 Z NONAME Semafor (COI20_semafor) C++17
18 / 100
 48 ms 24812 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Runtime error 5 ms 620 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 5 ms 2028 KB Output is correct
3 Correct 34 ms 16620 KB Output is correct
4 Correct 40 ms 19052 KB Output is correct
5 Correct 37 ms 19180 KB Output is correct
6 Correct 42 ms 21740 KB Output is correct
7 Correct 48 ms 24812 KB Output is correct
8 Correct 48 ms 24812 KB Output is correct
9 Correct 38 ms 18412 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 620 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 620 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 5 ms 2028 KB Output is correct
3 Correct 34 ms 16620 KB Output is correct
4 Correct 40 ms 19052 KB Output is correct
5 Correct 37 ms 19180 KB Output is correct
6 Correct 42 ms 21740 KB Output is correct
7 Correct 48 ms 24812 KB Output is correct
8 Correct 48 ms 24812 KB Output is correct
9 Correct 38 ms 18412 KB Output is correct
10 Runtime error 6 ms 620 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -