oj.uz

Submission #797400

# Submission time Handle Problem Language Result Execution time Memory
797400 2023-07-29T10:25:40 Z Johann L-triominoes (CEOI21_ltriominoes) C++14
10 / 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)
{
    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)
    {
    }

    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 3 ms 720 KB Output is correct
7 Correct 1 ms 1224 KB Output is correct
8 Correct 31 ms 37296 KB Output is correct
9 Correct 10 ms 18764 KB Output is correct
10 Correct 6 ms 4948 KB Output is correct
11 Correct 46 ms 41348 KB Output is correct
12 Correct 5 ms 10580 KB Output is correct
13 Correct 1 ms 456 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 16 ms 33136 KB Output is correct
16 Correct 278 ms 98824 KB Output is correct
17 Correct 38 ms 12620 KB Output is correct
18 Correct 149 ms 49548 KB Output is correct
19 Correct 8 ms 1828 KB Output is correct
20 Correct 278 ms 98788 KB Output is correct
21 Correct 136 ms 49576 KB Output is correct
22 Correct 3 ms 720 KB Output is correct
23 Correct 7 ms 1908 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 316 ms 98796 KB Output is correct
26 Correct 317 ms 98764 KB Output is correct
27 Correct 2 ms 724 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 5134 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 8102 ms 477340 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 8018 ms 90064 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 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 3 ms 720 KB Output is correct
7 Correct 1 ms 1224 KB Output is correct
8 Correct 31 ms 37296 KB Output is correct
9 Correct 10 ms 18764 KB Output is correct
10 Correct 6 ms 4948 KB Output is correct
11 Correct 46 ms 41348 KB Output is correct
12 Correct 5 ms 10580 KB Output is correct
13 Correct 1 ms 456 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 16 ms 33136 KB Output is correct
16 Correct 278 ms 98824 KB Output is correct
17 Correct 38 ms 12620 KB Output is correct
18 Correct 149 ms 49548 KB Output is correct
19 Correct 8 ms 1828 KB Output is correct
20 Correct 278 ms 98788 KB Output is correct
21 Correct 136 ms 49576 KB Output is correct
22 Correct 3 ms 720 KB Output is correct
23 Correct 7 ms 1908 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 316 ms 98796 KB Output is correct
26 Correct 317 ms 98764 KB Output is correct
27 Correct 2 ms 724 KB Output is correct
28 Execution timed out 8050 ms 76056 KB Time limit exceeded
29 Halted 0 ms 0 KB -