oj.uz

Submission #797401

# Submission time Handle Problem Language Result Execution time Memory
797401 2023-07-29T10:25:43 Z finn__ L-triominoes (CEOI21_ltriominoes) C++17
28 / 100
 8000 ms 255104 KB 
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,sse4")

#include <bits/stdc++.h>
using namespace std;

constexpr size_t W = 13, K = 250;

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

    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;
    }

    bool operator==(bmatrix const &y) const
    {
        for (size_t i = 0; i < 1 << W; ++i)
            if (mat[i] != y.mat[i])
                return 0;
        return 1;
    }

    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];
        if (pow2[i] == pow2[i - 1])
        {
            for (size_t j = i + 1; j < 31; ++j)
                pow2[j] = pow2[i];
            break;
        }
    }

    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:74:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     for (size_t y = 0; y < 1 << w; ++y)
      |                        ~~^~~~~~~~
ltrominoes.cpp:86:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |             if (i == (1 << w) - 1)
      |                 ~~^~~~~~~~~~~~~~~
ltrominoes.cpp:155:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  155 |         for (size_t i = 0; i < 1 << w; ++i)
      |                            ~~^~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1771 ms 254716 KB Output is correct
2 Correct 231 ms 254772 KB Output is correct
3 Correct 257 ms 254724 KB Output is correct
4 Correct 2052 ms 254796 KB Output is correct
5 Correct 2083 ms 254800 KB Output is correct
6 Correct 2127 ms 254816 KB Output is correct
7 Correct 1735 ms 254916 KB Output is correct
8 Execution timed out 8096 ms 84852 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1777 ms 254860 KB Output is correct
2 Correct 208 ms 254784 KB Output is correct
3 Correct 1737 ms 254740 KB Output is correct
4 Correct 208 ms 254668 KB Output is correct
5 Execution timed out 8077 ms 84756 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1803 ms 254760 KB Output is correct
2 Correct 1802 ms 254760 KB Output is correct
3 Correct 1709 ms 254728 KB Output is correct
4 Correct 1808 ms 254876 KB Output is correct
5 Correct 1774 ms 254780 KB Output is correct
6 Correct 1748 ms 254724 KB Output is correct
7 Correct 241 ms 254768 KB Output is correct
8 Correct 1751 ms 254712 KB Output is correct
9 Correct 2153 ms 254704 KB Output is correct
10 Correct 2146 ms 254748 KB Output is correct
11 Correct 2422 ms 254844 KB Output is correct
12 Correct 1750 ms 254728 KB Output is correct
13 Correct 1853 ms 254764 KB Output is correct
14 Correct 2084 ms 254724 KB Output is correct
15 Correct 1883 ms 254716 KB Output is correct
16 Correct 516 ms 254848 KB Output is correct
17 Correct 2671 ms 254796 KB Output is correct
18 Correct 309 ms 254792 KB Output is correct
19 Correct 218 ms 254788 KB Output is correct
20 Correct 2773 ms 254792 KB Output is correct
21 Correct 269 ms 254744 KB Output is correct
22 Correct 256 ms 254728 KB Output is correct
23 Correct 272 ms 254792 KB Output is correct
24 Correct 241 ms 254732 KB Output is correct
25 Correct 403 ms 254716 KB Output is correct
26 Correct 1755 ms 254720 KB Output is correct
27 Correct 333 ms 254788 KB Output is correct
28 Correct 1763 ms 254684 KB Output is correct
29 Correct 246 ms 254720 KB Output is correct
30 Correct 5062 ms 254720 KB Output is correct
31 Correct 6004 ms 254688 KB Output is correct
32 Correct 403 ms 254792 KB Output is correct
33 Correct 3169 ms 254796 KB Output is correct
34 Correct 4916 ms 254788 KB Output is correct
35 Correct 3340 ms 254792 KB Output is correct
36 Correct 1343 ms 254788 KB Output is correct
37 Correct 5061 ms 254788 KB Output is correct
38 Correct 4016 ms 254792 KB Output is correct
39 Correct 3884 ms 254784 KB Output is correct
40 Correct 2801 ms 254856 KB Output is correct
41 Correct 2287 ms 254796 KB Output is correct
42 Correct 2342 ms 254788 KB Output is correct
43 Correct 1196 ms 254788 KB Output is correct
44 Correct 2181 ms 254792 KB Output is correct
45 Correct 1156 ms 254788 KB Output is correct
46 Correct 2329 ms 254788 KB Output is correct
47 Correct 846 ms 254792 KB Output is correct
48 Correct 655 ms 254792 KB Output is correct
49 Correct 2068 ms 254680 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2130 ms 254756 KB Output is correct
2 Correct 2122 ms 254796 KB Output is correct
3 Correct 4601 ms 254816 KB Output is correct
4 Correct 1770 ms 254808 KB Output is correct
5 Correct 352 ms 254772 KB Output is correct
6 Correct 1853 ms 254804 KB Output is correct
7 Correct 1695 ms 254756 KB Output is correct
8 Correct 1881 ms 254788 KB Output is correct
9 Correct 1794 ms 254728 KB Output is correct
10 Correct 5251 ms 254800 KB Output is correct
11 Correct 5405 ms 254816 KB Output is correct
12 Correct 4335 ms 254852 KB Output is correct
13 Correct 5615 ms 254800 KB Output is correct
14 Correct 5271 ms 254752 KB Output is correct
15 Correct 5094 ms 254828 KB Output is correct
16 Correct 2662 ms 254836 KB Output is correct
17 Correct 4823 ms 254816 KB Output is correct
18 Correct 4769 ms 254820 KB Output is correct
19 Correct 2140 ms 254832 KB Output is correct
20 Correct 993 ms 254852 KB Output is correct
21 Correct 2447 ms 254816 KB Output is correct
22 Correct 1008 ms 254852 KB Output is correct
23 Correct 3571 ms 254716 KB Output is correct
24 Correct 4496 ms 254820 KB Output is correct
25 Correct 2845 ms 254856 KB Output is correct
26 Correct 4590 ms 254800 KB Output is correct
27 Correct 3943 ms 254752 KB Output is correct
28 Correct 2431 ms 254752 KB Output is correct
29 Correct 3729 ms 254936 KB Output is correct
30 Correct 2611 ms 254776 KB Output is correct
31 Correct 4523 ms 254828 KB Output is correct
32 Correct 2520 ms 254924 KB Output is correct
33 Correct 2457 ms 254796 KB Output is correct
34 Correct 564 ms 254856 KB Output is correct
35 Correct 750 ms 254792 KB Output is correct
36 Correct 2311 ms 254824 KB Output is correct
37 Correct 654 ms 254856 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2338 ms 255104 KB Output is correct
2 Correct 2280 ms 255056 KB Output is correct
3 Correct 2349 ms 255096 KB Output is correct
4 Execution timed out 8080 ms 84748 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1771 ms 254716 KB Output is correct
2 Correct 231 ms 254772 KB Output is correct
3 Correct 257 ms 254724 KB Output is correct
4 Correct 2052 ms 254796 KB Output is correct
5 Correct 2083 ms 254800 KB Output is correct
6 Correct 2127 ms 254816 KB Output is correct
7 Correct 1735 ms 254916 KB Output is correct
8 Execution timed out 8096 ms 84852 KB Time limit exceeded
9 Halted 0 ms 0 KB -