oj.uz

Submission #960991

# Submission time Handle Problem Language Result Execution time Memory
960991 2024-04-11T10:45:14 Z LucaIlie L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 8000 ms 5324 KB 
#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[MAX_W][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 < w; 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 = min( n - 1, p.first - lst );
        lst = p.first;

        for ( int l = w - 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.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1392 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Execution timed out 8048 ms 5324 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1280 KB Output is correct
2 Correct 20 ms 1368 KB Output is correct
3 Incorrect 177 ms 4640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

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