oj.uz

Submission #797389

# Submission time Handle Problem Language Result Execution time Memory
797389 2023-07-29T10:17:01 Z finn__ L-triominoes (CEOI21_ltriominoes) C++17
17 / 100
 8000 ms 255104 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr size_t W = 13, K = 250;

struct bmatrix
{
    bitset<1 << W> mat[1 << W];

    bmatrix transpose() const
    {
        bmatrix res;
        for (size_t i = 0; i < 1U << W; ++i)
            for (size_t j = 0; j < 1U << W; ++j)
                res.mat[i][j] = mat[j][i];
        return res;
    }

    bmatrix operator*(bmatrix const &y) const
    {
        bmatrix res;

        for (size_t i = 0; i < 1U << W; ++i)
            for (size_t j = 0; j < 1U << W; ++j)
                if (mat[i][j])
                    res.mat[i] |= y.mat[j];

        return res;
    }

    static bitset<1 << W> pow(bitset<1 << W> v, bmatrix pow2[31], size_t n)
    {
        size_t i = 1;

        while (n)
        {
            if (n & 1)
            {
                v = pow2[i].mul_vec(v);
            }
            n >>= 1;
            ++i;
        }

        return v;
    }

    bitset<1 << W> mul_vec(bitset<1 << W> const &v) const
    {
        bitset<1 << W> res;
        for (size_t i = 0; i < 1U << W; ++i)
            res[i] = (mat[i] & v).any();
        return res;
    }
};

pair<size_t, size_t> p[K];
bmatrix transitions, pow2[31];
bitset<1 << W> state, state2;

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

    size_t w, h, k;
    cin >> w >> h >> k;

    for (size_t i = 0; i < k; ++i)
        cin >> p[i].first >> p[i].second, --p[i].first, --p[i].second;

    for (size_t y = 0; y < 1 << w; ++y)
    {
        queue<uint32_t> q;
        q.push(y << W);

        while (!q.empty())
        {
            uint32_t u = q.front();
            q.pop();

            size_t i = u >> W, j = u & ((1 << W) - 1);

            if (i == (1 << w) - 1)
            {
                transitions.mat[j][y] = 1;
                continue;
            }

            for (size_t h = 0; h < w; ++h)
                if (!(i & (1 << h)))
                {
                    if (h && !(j & (1 << h)) && !(j & (1 << (h - 1))))
                    {
                        size_t ni = i ^ (1 << h), nj = j ^ (1 << h) ^ (1 << (h - 1));
                        q.push((ni << W) | nj);
                    }
                    if (h + 1 < w && !(j & (1 << h)) && !(j & (1 << (h + 1))))
                    {
                        size_t ni = i ^ (1 << h), nj = j ^ (1 << h) ^ (1 << (h + 1));
                        q.push((ni << W) | nj);
                    }
                    if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << h)))
                    {
                        size_t ni = i ^ (1 << h) ^ (1 << (h + 1)), nj = j ^ (1 << h);
                        q.push((ni << W) | nj);
                    }
                    if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << (h + 1))))
                    {
                        size_t ni = i ^ (1 << h) ^ (1 << (h + 1)), nj = j ^ (1 << (h + 1));
                        q.push((ni << W) | nj);
                    }
                }
        }
    }

    pow2[1] = transitions;
    for (size_t i = 2; i < 31; ++i)
    {
        pow2[i] = pow2[i - 1] * pow2[i - 1];
    }

    sort(p, p + k, [](auto const &a, auto const &b)
         { return a.second < b.second; });
    size_t i = 0, pos = 0;
    if (k && !p[0].second)
    {
        size_t x = 0;
        while (!p[i].second)
            x |= 1 << p[i].first, ++i;
        state[x] = 1;
    }
    else
        state[0] = 1;

    while (i < k)
    {
        state = bmatrix::pow(state, pow2, p[i].second - pos);
        pos = p[i].second;
        size_t x = 0;
        size_t j = i;
        while (j < k && p[j].second == p[i].second)
            x |= 1 << p[j].first, ++j;
        i = j;

        state2.reset();
        for (size_t i = 0; i < 1 << w; ++i)
            if (!(i & x) && state[i])
                state2[i ^ x] = 1;
        state = state2;
    }

    if (pos != h - 1)
    {
        state = bmatrix::pow(state, pow2, h - 1 - pos);
    }

    cout << (state[(1 << w) - 1] ? "YES" : "NO") << '\n';
}

Compilation message

ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:72:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     for (size_t y = 0; y < 1 << w; ++y)
      |                        ~~^~~~~~~~
ltrominoes.cpp:84:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |             if (i == (1 << w) - 1)
      |                 ~~^~~~~~~~~~~~~~~
ltrominoes.cpp:147:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  147 |         for (size_t i = 0; i < 1 << w; ++i)
      |                            ~~^~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1992 ms 254760 KB Output is correct
2 Correct 2009 ms 254888 KB Output is correct
3 Correct 2017 ms 254796 KB Output is correct
4 Correct 2585 ms 254796 KB Output is correct
5 Correct 2746 ms 254756 KB Output is correct
6 Correct 3062 ms 254712 KB Output is correct
7 Correct 2318 ms 254804 KB Output is correct
8 Execution timed out 8039 ms 84856 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2499 ms 254908 KB Output is correct
2 Correct 2391 ms 254768 KB Output is correct
3 Correct 2104 ms 254728 KB Output is correct
4 Correct 1980 ms 254724 KB Output is correct
5 Execution timed out 8071 ms 84960 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2091 ms 254788 KB Output is correct
2 Correct 1974 ms 254776 KB Output is correct
3 Correct 1993 ms 254776 KB Output is correct
4 Correct 2060 ms 254764 KB Output is correct
5 Correct 2037 ms 254736 KB Output is correct
6 Correct 2070 ms 254712 KB Output is correct
7 Correct 1979 ms 254668 KB Output is correct
8 Correct 2025 ms 254736 KB Output is correct
9 Correct 2200 ms 254784 KB Output is correct
10 Correct 2151 ms 254784 KB Output is correct
11 Correct 3019 ms 254788 KB Output is correct
12 Correct 2129 ms 254776 KB Output is correct
13 Correct 2240 ms 254784 KB Output is correct
14 Correct 2540 ms 254776 KB Output is correct
15 Correct 2273 ms 254784 KB Output is correct
16 Correct 2484 ms 254676 KB Output is correct
17 Correct 5454 ms 254744 KB Output is correct
18 Correct 2195 ms 254816 KB Output is correct
19 Correct 2109 ms 254844 KB Output is correct
20 Correct 5865 ms 254800 KB Output is correct
21 Correct 2178 ms 254784 KB Output is correct
22 Correct 2519 ms 254788 KB Output is correct
23 Correct 2866 ms 254700 KB Output is correct
24 Correct 2047 ms 254736 KB Output is correct
25 Correct 2653 ms 254788 KB Output is correct
26 Correct 4261 ms 254788 KB Output is correct
27 Correct 2226 ms 254792 KB Output is correct
28 Correct 2213 ms 254728 KB Output is correct
29 Correct 2097 ms 254784 KB Output is correct
30 Correct 6962 ms 254796 KB Output is correct
31 Correct 6431 ms 254788 KB Output is correct
32 Correct 2205 ms 254792 KB Output is correct
33 Correct 6311 ms 254792 KB Output is correct
34 Correct 6784 ms 254792 KB Output is correct
35 Correct 7634 ms 254792 KB Output is correct
36 Correct 4679 ms 254788 KB Output is correct
37 Execution timed out 8028 ms 254752 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3254 ms 254800 KB Output is correct
2 Correct 3203 ms 254760 KB Output is correct
3 Correct 6243 ms 254816 KB Output is correct
4 Correct 2076 ms 254760 KB Output is correct
5 Correct 1999 ms 254796 KB Output is correct
6 Correct 2201 ms 254788 KB Output is correct
7 Correct 1966 ms 254868 KB Output is correct
8 Correct 1976 ms 254728 KB Output is correct
9 Correct 2067 ms 254768 KB Output is correct
10 Correct 6650 ms 254804 KB Output is correct
11 Correct 6333 ms 254824 KB Output is correct
12 Correct 6840 ms 254852 KB Output is correct
13 Correct 6123 ms 254808 KB Output is correct
14 Correct 5972 ms 254804 KB Output is correct
15 Correct 6534 ms 254820 KB Output is correct
16 Correct 5620 ms 254856 KB Output is correct
17 Correct 5869 ms 254820 KB Output is correct
18 Correct 5808 ms 254816 KB Output is correct
19 Correct 4283 ms 254924 KB Output is correct
20 Correct 2806 ms 254920 KB Output is correct
21 Correct 2895 ms 254816 KB Output is correct
22 Correct 2873 ms 254964 KB Output is correct
23 Correct 4322 ms 254800 KB Output is correct
24 Correct 5616 ms 254820 KB Output is correct
25 Correct 5010 ms 254852 KB Output is correct
26 Correct 5487 ms 254800 KB Output is correct
27 Correct 4932 ms 254820 KB Output is correct
28 Correct 2929 ms 254812 KB Output is correct
29 Correct 4685 ms 254716 KB Output is correct
30 Correct 3360 ms 254812 KB Output is correct
31 Correct 5755 ms 254820 KB Output is correct
32 Correct 5067 ms 254856 KB Output is correct
33 Correct 4931 ms 254956 KB Output is correct
34 Correct 2288 ms 254964 KB Output is correct
35 Correct 2479 ms 254856 KB Output is correct
36 Correct 2807 ms 254920 KB Output is correct
37 Correct 2427 ms 254908 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2842 ms 254820 KB Output is correct
2 Correct 2701 ms 254924 KB Output is correct
3 Correct 2719 ms 255104 KB Output is correct
4 Execution timed out 8048 ms 84856 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1992 ms 254760 KB Output is correct
2 Correct 2009 ms 254888 KB Output is correct
3 Correct 2017 ms 254796 KB Output is correct
4 Correct 2585 ms 254796 KB Output is correct
5 Correct 2746 ms 254756 KB Output is correct
6 Correct 3062 ms 254712 KB Output is correct
7 Correct 2318 ms 254804 KB Output is correct
8 Execution timed out 8039 ms 84856 KB Time limit exceeded
9 Halted 0 ms 0 KB -