oj.uz

Submission #960995

# Submission time Handle Problem Language Result Execution time Memory
960995 2024-04-11T10:51:44 Z LucaIlie L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 8000 ms 5304 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[10][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 < 10; 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 = 10 - 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 34 ms 1624 KB Output is correct
8 Execution timed out 8096 ms 5304 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1624 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Execution timed out 8073 ms 4876 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 344 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 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 34 ms 1624 KB Output is correct
8 Execution timed out 8096 ms 5304 KB Time limit exceeded
9 Halted 0 ms 0 KB -