Submission #381570

#TimeUsernameProblemLanguageResultExecution timeMemory
381570NONAMESemafor (COI20_semafor)C++17
18 / 100
165 ms66284 KiB
#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) { 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 { 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...