oj.uz

Submission #583871

# Submission time Handle Problem Language Result Execution time Memory
583871 2022-06-26T11:47:59 Z jhwest2 L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;

const int M = 1 << 13;
int n, m, k;
bool dp[13][4];
vector<pair<int, int>> A, V;
bitset<M> G[M];

bool solve(int i, int j) {
    j ^= ((1 << n) - 1);
    if ((2 * n - __builtin_popcount(i) - __builtin_popcount(j)) % 3 != 0) {
        return false;
    }
    int m = (i & 1) + (j & 1) * 2; dp[0][m] = 1;
    for (int k = 1; k < n; k++) {
        int m = (i >> k & 1) + (j >> k & 1) * 2;
        if (m == 0) {
            dp[k][0] = dp[k - 1][3];
            dp[k][1] = dp[k][2] = dp[k - 1][0];
            dp[k][3] = (dp[k - 1][1] | dp[k - 1][2]);
        }
        if (m == 1) {
            dp[k][1] = dp[k - 1][3];
            dp[k][3] = dp[k - 1][0];
        }
        if (m == 2) {
            dp[k][2] = dp[k - 1][3];
            dp[k][3] = dp[k - 1][0];
        }
        if (m == 3) {
            dp[k][3] = dp[k - 1][3];
        }
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < 4; j++) {
        dp[i][j] = 0;
    }
    return dp[n - 1][3];
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> m >> n >> k;
    for (int i = 0; i < k; i++) {
        int x, y; cin >> y >> x;
        A.emplace_back(x, y);
    }
    sort(A.begin(), A.end(), [&](auto i, auto j) {
        return i.second < j.second;
        });
    for (int i = 0; i < k; i++) {
        auto [f, s] = A[i]; --f;
        if (V.empty() || V.back().second != s) {
            V.emplace_back(1 << f, s);
        }
        else V.back().first |= (1 << f);
    }
    if (V.empty() || V.back().second != m) {
        V.emplace_back(0, m);
    }
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < (1 << n); j++) {
            G[i][j] = solve(i, j);
        }
    }

    int p = 0; bitset<M> B = 0, dp = 0, ep = 0;
    dp[(1 << n) - 1] = 1;
    for (auto [f, s] : V) {
        int ff = f ^ ((1 << n) - 1);
        for (int i = ff; ; i = (i - 1) & ff) {
            B[i] = 1;
            if (i == 0) break;            
        }
        int it = min((s - p) % 6 + 6, s - p);
        while (it--) {
            for (int i = 0; i < (1 << n); i++) if (dp[i]) {
                ep |= G[i];
            }
            dp = ep; ep = 0;
        }
        dp &= B;
        for (int i = 0; i < (1 << n); i++) if (dp[i]) {
            ep[i | f] = 1;
        }
        dp = ep; ep = 0; B = 0;
        p = s;
    }
    cout << (dp[(1 << n) - 1] ? "YES" : "NO");
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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