Submission #590802

#	Time	Username	Problem	Language	Result	Execution time	Memory
590802		alextodoran	L-triominoes (CEOI21_ltriominoes)	C++17	100 / 100	1129 ms	133116 KiB

ltrominoes

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int W_MAX = 13;
const int K_MAX = 250;
const int D_MAX = 15;

int W, H, K;
map <int, vector <int>> rows;

bool adj[1 << W_MAX][1 << W_MAX];
vector <int> out[1 << W_MAX];

bool check (int u, int v) {
    int carry = 0;
    for (int y = 0; y < W; y++) {
        int cnt = ((u >> y) & 1) + !((v >> y) & 1) - carry;
        if (cnt < 0) {
            return false;
        } else if (cnt == 0) {
            carry = 0;
        } else if (cnt == 1) {
            carry = 2;
        } else {
            carry = 1;
        }
    }
    return (carry == 0);
}

bitset <(1 << W_MAX)> path[D_MAX + 1][1 << W_MAX];

void build () {
    for (int u = 0; u < (1 << W); u++) {
        path[0][u][u] = true;
    }
    for (int d = 1; d <= D_MAX; d++) {
        for (int u = 0; u < (1 << W); u++) {
            for (int v : out[u]) {
                path[d][u] |= path[d - 1][v];
            }
        }
    }
}

bitset <(1 << W_MAX)> reach;
bitset <(1 << W_MAX)> newReach;

void advance (int k) {
    if (k > D_MAX) {
        k -= (k - D_MAX + 5) / 6 * 6;
    }
    for (int u = 0; u < (1 << W); u++) {
        if (reach[u] == true) {
            newReach |= path[k][u];
        }
    }
    swap(reach, newReach); newReach.reset();
}

bool solve () {
    reach[(1 << W) - 1] = true;
    int x = 0;
    for (pair <int, vector <int>> row : rows) {
        advance(row.first - x); x = row.first;
        int b = 0;
        for (int y : row.second) {
            b |= (1 << y);
        }
        for (int u = b; u < (1 << W); u = ((u + 1) | b)) {
            newReach[u ^ b] = reach[u];
        }
        swap(reach, newReach); newReach.reset();
    }
    advance((H - 1) - x);
    return reach[0];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> W >> H >> K;
    for (int i = 0; i < K; i++) {
        int x, y;
        cin >> y >> x;
        x--; y--;
        rows[x].push_back(y);
    }

    for (int u = 0; u < (1 << W); u++) {
        for (int v = 0; v < (1 << W); v++) {
            if (check(u, v) == true) {
                out[u].push_back(v);
            }
        }
    }
    build();

    cout << (solve() == true ? "YES" : "NO") << "\n";

    return 0;
}

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