Submission #1285123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285123		stefanneagu	L-triominoes (CEOI21_ltriominoes)	C++20	100 / 100	133 ms	2436 KiB

ltrominoes

#include <bits/stdc++.h>

using namespace std;

const int nmax = 13;

vector<int> adj[1 << nmax];
int n;

void dfs(int i, int mask, int nxt) {
    if (i == n) {
        adj[mask].push_back(nxt);
        return;
    }
    if ((mask & (1 << i)) != 0) {
        dfs(i + 1, mask, nxt);
        return;
    }
    if (i < n - 1 && (nxt & (1 << i)) == 0 && (nxt & (1 << (i + 1))) == 0) {
        dfs(i + 1, mask, nxt + (1 << i) + (1 << (i + 1)));
    }
    if (i < n - 1 && (nxt & (1 << (i + 1))) == 0 && (mask & (1 << (i + 1))) == 0) {
        dfs(i + 2, mask, nxt + (1 << (i + 1)));
    }
    if (i < n - 1 && (nxt & (1 << i)) == 0 && (mask & (1 << (i + 1))) == 0) {
        dfs(i + 2, mask, nxt + (1 << i));
    }
    if (i > 0 && (nxt & (1 << i)) == 0 && (nxt & (1 << (i - 1))) == 0) {
        dfs(i + 1, mask, nxt + (1 << i) + (1 << (i - 1)));
    }
}

void decomp(int i) {
    for (int bit = 0; bit < n; bit++) {
        if ((1 << bit) & i) {
            cout << 1;
        }  else {
            cout << 0;
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < (1 << n); i++) {
        dfs(0, i, 0);
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }
    map<int, int> mp;
    mp[1] = 0, mp[m] = 0;
    while (q--) {
        int a, b;
        cin >> a >> b;
        swap(a, b);
        b--;
        mp[a] |= (1 << b);
    }
    vector<pair<int, int>> v;
    for (auto it : mp) {
        v.push_back(it);
    }
    vector<int> f((1 << n), 0), nxt_f((1 << n), 0);
    f[v[0].second] = 1;
    for (int i = 0; i < v.size() - 1; i++) {
        int dist = v[i + 1].first - v[i].first;
        if (dist > 12) {
            dist %= 6;
            dist += 6;
        }
        while (dist--) {
            nxt_f.clear();
            nxt_f.resize((1 << n), 0);
            for (int msk = 0; msk < (1 << n); msk++) {
                if (f[msk]) {
                    for (auto it : adj[msk]) {
                        nxt_f[it] = 1;
                    }
                }
            }
            f = nxt_f;
        }
        nxt_f.clear();
        nxt_f.resize((1 << n), 0);
        for (int msk = 0; msk < (1 << n); msk++) {
            if ((v[i + 1].second & msk) != 0) {
                f[msk] = 0;
            } else {
                nxt_f[v[i + 1].second + msk] = f[msk];
            }
        }
        f = nxt_f;
    }
    cout << (f[(1 << n) - 1] ? "YES" : "NO");
    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