Submission #960994

#	Time	Username	Problem	Language	Result	Execution time	Memory
960994		LucaIlie	L-triominoes (CEOI21_ltriominoes)	C++17	28 / 100	8090 ms	10236 KiB

ltrominoes

#include <bits/stdc++.h>

using namespace std;

const int MAX_W = 13;
const int MAX_N = (1 << MAX_W);
map<int, int> conf;
bitset<MAX_N> adj[30][MAX_N];

bool hasBit( int mask, int i ) {
    return ((mask >> i) & 1);
}

int main() {
    int w, h, k;

    cin >> w >> h >> k;
    conf[0] = conf[h - 1] = 0;
    for ( int i = 0; i < k; i++ ) {
        int l, c;
        cin >> l >> c;
        l--;
        c--;
        conf[c] += (1 << l);
    }

    int n = (1 << w);
    for ( int mask = 0; mask < n; mask++ ) {
        vector<int> prvVec1 = { 0 }, prvVec2 = { 0 };
        for ( int i = 0; i < w; i++ ) {
            vector<int> vec;

            if ( hasBit( mask, i ) ) {
                for ( int m: prvVec1 )
                    vec.push_back( m );
            } else {
                for ( int m: prvVec1 ) {
                    if ( i >= 1 && !hasBit( m, i - 1 ) && !hasBit( m, i ) )
                        vec.push_back( m + (1 << (i - 1)) + (1 << i) );
                    if ( i <= w - 2 && !hasBit( m, i ) && !hasBit( m, i + 1 ) )
                        vec.push_back( m + (1 << i) + (1 << (i + 1)) );
                }

                if ( i >= 1 && !hasBit( mask, i - 1 ) ) {
                    for ( int m: prvVec2 ) {
                        if ( !hasBit( m, i - 1 ) )
                            vec.push_back( m + (1 << (i - 1)) );
                        if ( !hasBit( m, i ) )
                            vec.push_back( m + (1 << i) );
                    }
                }
            }

            prvVec2 = prvVec1;
            prvVec1 = vec;
        }

        for ( int m: prvVec1 )
            adj[0][mask][m] = true;
    }

    for ( int l = 1; l < 30; l++ ) {
        for ( int i = 0; i < n; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                for ( int k = 0; k < n; k++ )
                    adj[l][i][j] = adj[l][i][j] | (adj[l - 1][i][k] & adj[l - 1][k][j]);
            }
        }
    }

    bitset<MAX_N> pos;
    pos[conf[0]] = true;
    int lst = 0;
    for ( auto p: conf ) {
        if ( p.first == 0 )
            continue;

        int x = p.first - lst;
        lst = p.first;

        for ( int l = 30 - 1; l >= 0; l-- ) {
            if ( x >= (1 << l) ) {
                bitset<MAX_N> newPos;
                for ( int m = 0; m < n; m++ ) {
                    if ( pos[m] )
                        newPos |= adj[l][m];
                }
                pos = newPos;
                x -= (1 << l);
            }
        }

        bitset<MAX_N> newPos = pos;
        pos.reset();
        for ( int m = 0; m < n; m++ ) {
            if ( (p.second & m) == 0 )
                pos[p.second | m] = newPos[m];
        }

    }

    cout << (pos[n - 1] ? "YES\n" : "NO\n");

    return 0;
}

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