oj.uz

Submission #381566

# Submission time Handle Problem Language Result Execution time Memory
381566 2021-03-25T10:01:32 Z NONAME Semafor (COI20_semafor) C++17
6 / 100
 4 ms 2540 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 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.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 4 ms 2540 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 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 2 ms 492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

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