Submission #1115011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115011		MisterReaper	L-triominoes (CEOI21_ltriominoes)	C++17	28 / 100	1834 ms	592 KiB

ltrominoes

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

bool has(int m, int k) {
    return m >> k & 1;
}

struct matrix {
    constexpr static int n = 1 << 6;
    int mat[n][n];
    matrix() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] = 0;
            }
        }
    }
    matrix operator* (const matrix rhs) {
        matrix res;
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < n; ++k) {
                for (int j = 0; j < n; ++j) {
                    res.mat[i][j] |= mat[i][k] && rhs.mat[k][j];
                }
            }
        }
        return res;
    }
};

matrix init;

void work(int n) {
    auto dfs = [&](auto&& self, int s, int mask, int now, int nmask) -> void {
        if (s == n) {
            if (now == (1 << n) - 1 && nmask < (1 << n)) {
                #ifdef DEBUG
                    debug(s, std::bitset<5>(now));
                    std::cerr << std::bitset<5>(nmask) << '\n';
                    std::cerr << std::bitset<5>(mask) << '\n';
                    std::cerr << '\n';
                #endif
                init.mat[mask][nmask] = true;
            }
            return;
        }
        if (now >> s & 1) {
            self(self, s + 1, mask, now, nmask);
            return;
        }
        // X.
        // ..
        {
            if (!has(nmask, s) && !has(now, s + 1)) {
                self(self, s + 1, mask, now | (3 << s), nmask | (1 << s));
            }
        }
        // .X
        // ..
        {
            if (!has(nmask, s + 1) && !has(now, s + 1)) {
                self(self, s + 1, mask, now | (3 << s), nmask | (2 << s));
            }
        }
        // ..
        // .X
        {
            if (s != 0 && !has(nmask, s) && !has(nmask, s - 1)) {
                self(self, s + 1, mask, now | (1 << s), nmask | (3 << (s - 1)));
            }
        }
        // ..
        // X.
        {
            if (!has(nmask, s) && !has(nmask, s + 1)) {
                self(self, s + 1, mask, now | (1 << s), nmask | (3 << s));
            }
        }
    };
    // dfs(dfs, 0, 1, 1, 0);
    // exit(0);
    for (int m = 0; m < (1 << n); ++m) {
        dfs(dfs, 0, m, m, 0);
    }
}

matrix power(matrix a, int b) {
    matrix res;
    for (int i = 0; i < matrix::n; ++i) {
        res.mat[i][i] = true;
    }
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int W, H, K;
    std::cin >> W >> H >> K;

    std::vector<int> A(K), B(K);
    for (int i = 0; i < K; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
    }

    std::vector<int> ord(K);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        return B[lhs] < B[rhs];
    });

    work(W);
    
    std::vector<std::pair<int, int>> ss;
    ss.emplace_back(0, 0);
    for (int i = 0, j = 0; i < K; i = j) {
        int mask = 0;
        while (j < K && B[ord[i]] == B[ord[j]]) {
            mask |= 1 << A[ord[j]];
            ++j;
        }
        ss.emplace_back(B[ord[i]], mask);
    }
    ss.emplace_back(H, (1 << W) - 1);

    debug(ss);

    std::vector<bool> dp(1 << W);
    dp[0] = true;

    for (int iss = 0; iss + 1 < ss.size(); ++iss) {
        int len = ss[iss + 1].first - ss[iss].first;
        int row_mask = ss[iss].second;
        std::vector<bool> new_dp(1 << W);

        debug("wtf power", len);
        matrix matx = power(init, len);
        debug("oh ok bro");
        #ifdef DEBUG
            std::cerr << "debug:\n";
            for (int i = 0; i < (1 << W); ++i) {
                if (dp[i]) {
                    if (i & row_mask) {
                        continue;
                    }
                    for (int j = 0; j < (1 << W); ++j) {
                        if (matx.mat[i | row_mask][j]) {
                            std::cerr << std::bitset<5>(i) << '\n';
                            std::cerr << std::bitset<5>(j) << '\n';
                            std::cerr << '\n';
                        }
                    }
                }
            }
            std::cerr << "i am here\n";
            for (int i = 0; i < (1 << W); ++i) {
                if (dp[i]) {
                    if (i & row_mask) {
                        continue;
                    } 
                    std::cerr << std::bitset<5>(i) << '\n';
                }
            }
        #endif

        for (int i = 0; i < (1 << W); ++i) {
            if (i & row_mask || !dp[i]) {
                continue;
            }
            for (int j = 0; j < (1 << W); ++j) {
                if (matx.mat[i | row_mask][j]) {
                    debug(std::bitset<5>(i), std::bitset<5>(j));
                }
                new_dp[j] = new_dp[j] | (dp[i] & matx.mat[i | row_mask][j]);
            }
        }

        dp.swap(new_dp);
        debug(dp);
    }

    std::cout << (dp[0] ? "YES" : "NO") << '\n';

    return 0;
}

Compilation message (stderr)

ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:147:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int iss = 0; iss + 1 < ss.size(); ++iss) {
      |                       ~~~~~~~~^~~~~~~~~~~

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