oj.uz

Submission #797391

# Submission time Handle Problem Language Result Execution time Memory
797391 2023-07-29T10:18:08 Z finn__ L-triominoes (CEOI21_ltriominoes) C++17
28 / 100
 8000 ms 255100 KB 
#pragma GCC optimize("Ofast")
#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 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:75:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     for (size_t y = 0; y < 1 << w; ++y)
      |                        ~~^~~~~~~~
ltrominoes.cpp:87:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |             if (i == (1 << w) - 1)
      |                 ~~^~~~~~~~~~~~~~~
ltrominoes.cpp:150:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |         for (size_t i = 0; i < 1 << w; ++i)
      |                            ~~^~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2028 ms 254800 KB Output is correct
2 Correct 2174 ms 254784 KB Output is correct
3 Correct 2152 ms 254764 KB Output is correct
4 Correct 2558 ms 254800 KB Output is correct
5 Correct 2250 ms 254760 KB Output is correct
6 Correct 2419 ms 254816 KB Output is correct
7 Correct 2029 ms 254836 KB Output is correct
8 Execution timed out 8026 ms 84800 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2066 ms 254800 KB Output is correct
2 Correct 2032 ms 254760 KB Output is correct
3 Correct 2171 ms 254728 KB Output is correct
4 Correct 2630 ms 254700 KB Output is correct
5 Execution timed out 8068 ms 84844 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2198 ms 254788 KB Output is correct
2 Correct 2151 ms 254668 KB Output is correct
3 Correct 2170 ms 254776 KB Output is correct
4 Correct 2228 ms 254776 KB Output is correct
5 Correct 2133 ms 254780 KB Output is correct
6 Correct 2344 ms 254684 KB Output is correct
7 Correct 2168 ms 254784 KB Output is correct
8 Correct 2138 ms 254760 KB Output is correct
9 Correct 2486 ms 254748 KB Output is correct
10 Correct 2051 ms 254784 KB Output is correct
11 Correct 2863 ms 254748 KB Output is correct
12 Correct 2128 ms 254668 KB Output is correct
13 Correct 2155 ms 254804 KB Output is correct
14 Correct 2429 ms 254868 KB Output is correct
15 Correct 2302 ms 254668 KB Output is correct
16 Correct 2392 ms 254704 KB Output is correct
17 Correct 4844 ms 254796 KB Output is correct
18 Correct 3544 ms 254788 KB Output is correct
19 Correct 2634 ms 254784 KB Output is correct
20 Correct 6303 ms 254792 KB Output is correct
21 Correct 2662 ms 254732 KB Output is correct
22 Correct 2798 ms 254788 KB Output is correct
23 Correct 2683 ms 254764 KB Output is correct
24 Correct 2736 ms 254780 KB Output is correct
25 Correct 2753 ms 254788 KB Output is correct
26 Correct 3406 ms 254788 KB Output is correct
27 Correct 2012 ms 254732 KB Output is correct
28 Correct 2695 ms 254780 KB Output is correct
29 Correct 2107 ms 254788 KB Output is correct
30 Correct 5283 ms 254792 KB Output is correct
31 Correct 4937 ms 254792 KB Output is correct
32 Correct 2133 ms 254820 KB Output is correct
33 Correct 4832 ms 254792 KB Output is correct
34 Correct 5147 ms 254792 KB Output is correct
35 Correct 5073 ms 254796 KB Output is correct
36 Correct 2937 ms 254828 KB Output is correct
37 Correct 5087 ms 254792 KB Output is correct
38 Correct 4199 ms 254788 KB Output is correct
39 Correct 4159 ms 254792 KB Output is correct
40 Correct 4547 ms 254796 KB Output is correct
41 Correct 4099 ms 254800 KB Output is correct
42 Correct 2598 ms 254788 KB Output is correct
43 Correct 2923 ms 254796 KB Output is correct
44 Correct 2441 ms 254964 KB Output is correct
45 Correct 2886 ms 254720 KB Output is correct
46 Correct 2488 ms 254788 KB Output is correct
47 Correct 2542 ms 254884 KB Output is correct
48 Correct 2384 ms 254736 KB Output is correct
49 Correct 2243 ms 254752 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2288 ms 254792 KB Output is correct
2 Correct 2272 ms 254852 KB Output is correct
3 Correct 4539 ms 254856 KB Output is correct
4 Correct 1946 ms 254752 KB Output is correct
5 Correct 1979 ms 254780 KB Output is correct
6 Correct 1970 ms 254728 KB Output is correct
7 Correct 1977 ms 254792 KB Output is correct
8 Correct 1987 ms 254744 KB Output is correct
9 Correct 1957 ms 254796 KB Output is correct
10 Correct 5130 ms 254912 KB Output is correct
11 Correct 5235 ms 254860 KB Output is correct
12 Correct 5352 ms 254856 KB Output is correct
13 Correct 5299 ms 254924 KB Output is correct
14 Correct 4900 ms 254804 KB Output is correct
15 Correct 4928 ms 254804 KB Output is correct
16 Correct 4114 ms 254752 KB Output is correct
17 Correct 4723 ms 254812 KB Output is correct
18 Correct 5022 ms 254988 KB Output is correct
19 Correct 3663 ms 254824 KB Output is correct
20 Correct 2535 ms 254784 KB Output is correct
21 Correct 2731 ms 254872 KB Output is correct
22 Correct 2609 ms 254852 KB Output is correct
23 Correct 3832 ms 254840 KB Output is correct
24 Correct 4541 ms 254696 KB Output is correct
25 Correct 4122 ms 254840 KB Output is correct
26 Correct 4516 ms 254864 KB Output is correct
27 Correct 4124 ms 254816 KB Output is correct
28 Correct 2700 ms 254860 KB Output is correct
29 Correct 3972 ms 254812 KB Output is correct
30 Correct 2863 ms 254808 KB Output is correct
31 Correct 4783 ms 254820 KB Output is correct
32 Correct 4162 ms 254844 KB Output is correct
33 Correct 4054 ms 254848 KB Output is correct
34 Correct 2202 ms 254932 KB Output is correct
35 Correct 2372 ms 254904 KB Output is correct
36 Correct 2605 ms 254820 KB Output is correct
37 Correct 2277 ms 254828 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2571 ms 254920 KB Output is correct
2 Correct 2509 ms 254916 KB Output is correct
3 Correct 2538 ms 255100 KB Output is correct
4 Execution timed out 8026 ms 84852 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2028 ms 254800 KB Output is correct
2 Correct 2174 ms 254784 KB Output is correct
3 Correct 2152 ms 254764 KB Output is correct
4 Correct 2558 ms 254800 KB Output is correct
5 Correct 2250 ms 254760 KB Output is correct
6 Correct 2419 ms 254816 KB Output is correct
7 Correct 2029 ms 254836 KB Output is correct
8 Execution timed out 8026 ms 84800 KB Time limit exceeded
9 Halted 0 ms 0 KB -