Submission #583874

#	Time	Username	Problem	Language	Result	Execution time	Memory
583874		jhwest2	L-triominoes (CEOI21_ltriominoes)	C++17	0 / 100	31 ms	968 KiB

ltrominoes

#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];

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++) {
            if ((n - __builtin_popcount(i) + __builtin_popcount(j)) % 3 != 0) {
                continue;
            }
            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];
                } */
            }
            G[i][j] = dp[n - 1][3];
            for (int i = 0; i < n; i++) for (int j = 0; j < 4; j++) {
                dp[i][j] = 0;
            }
        }
    }

    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");
}

Compilation message (stderr)

ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:37:21: warning: unused variable 'm' [-Wunused-variable]
   37 |                 int m = (i >> k & 1) + (~j >> k & 1) * 2;
      |                     ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20