Submission #698694

#	Time	Username	Problem	Language	Result	Execution time	Memory
698694		Cyanmond	L-triominoes (CEOI21_ltriominoes)	C++17	100 / 100	805 ms	2000 KiB

ltrominoes

#include <bits/stdc++.h>

using i64 = long long;

struct Point {
    i64 x;
    i64 y;
};

constexpr int N = 1 << 13;

bool calc(i64 H, i64 W, int K, std::map<i64, int> mEx) {
    std::array<std::vector<int>, N> g;
    std::vector<int> seen(N);
    auto searchNext = [&](int s) {
        if (seen[s]) {
            return g[s];
        }
        seen[s] = true;

        auto dfs = [&](auto &&self, int t, int b) -> void {
            if (b >= W) {
                g[s].push_back(t);
                return;
            }
            if (s & (1 << b)) {
                self(self, t, b + 1);
                return;
            }
            if (b != 0) {
                if (not (t & (1 << (b - 1)))) {
                    int newT = t;
                    newT |= 1 << (b - 1);
                    newT |= 1 << b;
                    self(self, newT, b + 1);
                }
            }
            if (b != W - 1) {
                if (s & (1 << (b + 1))) {
                    int newT = t;
                    newT |= 1 << b;
                    newT |= 1 << (b + 1);
                    self(self, newT, b + 2);
                } else {
                    int newT = t;
                    newT |= 1 << b;
                    self(self, newT, b + 2);
                    newT = t;
                    newT |= 1 << (b + 1);
                    self(self, newT, b + 2);
                }
            }
        };
        dfs(dfs, 0, 0);
        return g[s];
    };

    std::vector dp(1 << W, false);
    dp[(1 << W) - 1] = true;
    mEx[0] = (1 << W) - 1;
    if (mEx.find(H) == mEx.end()) {
        mEx[H] = 0;
    }
    i64 last = 0;
    for (const auto &[k, b] : mEx) {
        if (k - last < 20) {
            for (int i = last + 1; i <= k; ++i) {
                std::vector ndp(1 << W, false);
                for (int s = 0; s < (1 << W); ++s) {
                    if (not dp[s]) {
                        continue;
                    }
                    const int b = mEx[i];
                    const auto g = searchNext(s);
                    for (const auto t : g) {
                        if ((t & b) != 0) {
                            continue;
                        }
                        ndp[t | b] = true;
                    }
                }
                dp = std::move(ndp);
            }
        } else {
            std::vector<std::vector<bool>> dList;
            dList.push_back(dp);
            for (int i = last + 1;; ++i) {
                std::vector ndp(1 << W, false);
                for (int s = 0; s < (1 << W); ++s) {
                    if (not dp[s]) {
                        continue;
                    }
                    const int b = mEx[i];
                    const auto g = searchNext(s);
                    for (const auto t : g) {
                        if ((t & b) != 0) {
                            continue;
                        }
                        ndp[t | b] = true;
                    }
                }
                dp = std::move(ndp);

                if (std::find(dList.begin(), dList.end(), dp) == dList.end()) {
                    dList.push_back(dp);
                } else {
                    auto itr = std::find(dList.begin(), dList.end(), dp);
                    dList.erase(dList.begin(), itr);
                    const int w = dList.size();
                    const i64 p = (k - 1 - i) % w;
                    dp = dList[p % w];
                    break;
                }
            }
            std::vector ndp(1 << W, false);
            for (int s = 0; s < (1 << W); ++s) {
                if (not dp[s]) {
                    continue;
                }
                const int b = mEx[k];
                const auto g = searchNext(s);
                for (const auto t : g) {
                    if ((t & b) != 0) {
                        continue;
                    }
                    ndp[t | b] = true;
                }
            }
            dp = std::move(ndp);
        }
        last = k;
    }
    return dp[(1 << W) - 1];
}

void solve() {
    i64 W, H;
    int K;
    std::cin >> W >> H >> K;
    std::vector<Point> points(K);
    std::map<i64, int> mEx;
    for (auto &[x, y] : points) {
        std::cin >> x >> y;
        --x;
        mEx[y] |= 1 << x;
    }
    std::cout << (calc(H, W, K, mEx) ? "YES" : "NO") << std::endl;
}

int main() {
    solve();
}

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