Submission #698684

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698684	2023-02-14T07:39:59 Z	Cyanmond	L-triominoes (CEOI21_ltriominoes)	C++17	7 / 100	1 ms	300 KB

ltrominoes

#include <bits/stdc++.h>

using i64 = long long;

struct Point {
    i64 x;
    i64 y;
};

constexpr int N = 1 << 16;

bool judge(int H, int W) {
     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;
    for (int i = 0; i < H; ++i) {
        std::vector ndp(1 << W, false);
        for (int s = 0; s < (1 << W); ++s) {
            if (not dp[s]) {
                continue;
            }
            const auto g = searchNext(s);
            for (const auto t : g) {
                ndp[t] = true;
            }
        }
        dp = std::move(ndp);
    }
    return dp[(1 << W) - 1];
}

void exp() {
    int N = 16;
    for (int i = 2; i < N; ++i) {
        for (int j = 2; j < N; ++j) {
            if (judge(i, j)) {
                std::cout << i << ' ' << j << std::endl;
            }
        }
    }
}

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;
        --y;
        mEx[y] |= 1 << x;
    }

    if (H * W % 6 == 0 or (std::min(H, W) >= 5 and H * W % 3 == 0)) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }
}

int main() {
    solve();
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	300 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	300 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	300 KB	Output is correct
13	Correct	0 ms	296 KB	Output is correct
14	Correct	0 ms	296 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	300 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	296 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Incorrect	1 ms	212 KB	Output isn't correct
5	Halted	0 ms	0 KB	-