Submission #583897

#	Time	Username	Problem	Language	Result	Execution time	Memory
583897		jhwest2	L-triominoes (CEOI21_ltriominoes)	C++14	100 / 100	3213 ms	8704 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 >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        int x, y; cin >> x >> y;
        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> dp = 0, ep = 0;
    dp[(1 << n) - 1] = 1;
    for (auto [f, s] : V) {
        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;
        }
        for (int i = 0; i < (1 << n); i++) if (dp[i] && (i & f) == 0) {
            ep[i | f] = 1;
        }
        dp = ep; ep = 0;
        p = s;
    }
    cout << (dp[(1 << n) - 1] ? "YES" : "NO");
}

Compilation message (stderr)

ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |         auto [f, s] = A[i]; --f;
      |              ^
ltrominoes.cpp:63:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto [f, s] : V) {
      |               ^

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