oj.uz

Submission #797405

# Submission time Handle Problem Language Result Execution time Memory
797405 2023-07-29T10:32:41 Z Johann L-triominoes (CEOI21_ltriominoes) C++14
0 / 100
 8000 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int maxW = 13;
int W, H, K;
map<int, int> blocked;
typedef bitset<1 << maxW> bs;
typedef vector<bs> matrix;
typedef vector<matrix> vvbs;
bs dp[2];
bs mat[1 << maxW];
vvbs lift;

void dfs(int idx, int base, int next, bs &nextdp)
{
    if (idx == W)
    {
        nextdp[next] = true;
        return;
    }
    if (base & (1 << idx))
        dfs(idx + 1, base, next, nextdp);
    else
    {
        // _X my pos: 1 << idx

        // TT
        // _T
        if (idx < W - 1 && ((3 << idx) & next) == 0)
            dfs(idx + 1, base | (1 << idx), next | (3 << idx), nextdp);

        // _TT
        // _T_
        if (idx > 0 && ((3 << (idx - 1)) & next) == 0)
            dfs(idx + 1, base | (1 << idx), next | (3 << (idx - 1)), nextdp);

        // T_
        // TT
        if (idx < W - 1 && (base & (3 << idx)) == 0 && (next & (2 << idx)) == 0)
            dfs(idx + 2, base | (3 << idx), next | (2 << idx), nextdp);

        // _T
        // TT
        if (idx < W - 1 && (base & (3 << idx)) == 0 && (next & (1 << idx)) == 0)
            dfs(idx + 2, base | (3 << idx), next | (1 << idx), nextdp);
    }
}

void mul(bs &base, int liftidx, bs &re, int block = 0)
{
    re = 0;
    for (int j = 0; j < 1 << W; ++j)
    {
        if (!base[j])
            continue;
        if (j & block)
            continue;

        re |= lift[liftidx][j | block];
    }
}

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

    cin >> W >> H >> K;
    for (int k = 0, x, y; k < K; ++k)
    {
        cin >> x >> y;
        --x, --y;
        blocked[y] = blocked[y] | (1 << x);
    }

    lift.assign(ceil(log2(H) + 1), matrix(1 << W));
    for (int i = 0; i < 1 << W; ++i)
        dfs(0, i, 0, lift[0][i]);

    for (int j = 1; j < sz(lift); ++j)
        for (int i = 0; i < 1 << W; ++i)
            mul(lift[j - 1][i], j - 1, lift[j][i]);

    if (K == 0)
    {
        bs start = 0, tmp;
        start[0] = 1;
        for (int j = sz(lift) - 1; j >= 0; --j)
        {
            if (H >= (1 << j))
            {
                H -= (1 << j);
                mul(start, j, tmp);
                swap(start, tmp);
            }
        }
        if (start[0])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    else
    {
        dp[0] = 0;
        dp[0][0] = true;
        for (int i = 0; i < H; ++i)
        {
            int ii = i & 1;
            int ni = ii ^ 1;
            dp[ni] = 0;

            mul(dp[ii], 0, dp[ni], blocked[i]);
        }

        if (dp[H & 1][0])
            cout << "YES\n";
        else
            cout << "NO\n";
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 2756 ms 37204 KB Output is correct
9 Correct 678 ms 18768 KB Output is correct
10 Correct 48 ms 4948 KB Output is correct
11 Correct 3326 ms 41324 KB Output is correct
12 Correct 213 ms 10580 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2288 ms 33092 KB Output is correct
16 Execution timed out 8071 ms 98828 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4564 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Execution timed out 8048 ms 131668 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 5441 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8060 ms 430404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8093 ms 89448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 2756 ms 37204 KB Output is correct
9 Correct 678 ms 18768 KB Output is correct
10 Correct 48 ms 4948 KB Output is correct
11 Correct 3326 ms 41324 KB Output is correct
12 Correct 213 ms 10580 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2288 ms 33092 KB Output is correct
16 Execution timed out 8071 ms 98828 KB Time limit exceeded
17 Halted 0 ms 0 KB -