oj.uz

Submission #797398

# Submission time Handle Problem Language Result Execution time Memory
797398 2023-07-29T10:24:17 Z finn__ L-triominoes (CEOI21_ltriominoes) C++17
28 / 100
 8000 ms 255112 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 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 1989 ms 254784 KB Output is correct
2 Correct 243 ms 254736 KB Output is correct
3 Correct 235 ms 254712 KB Output is correct
4 Correct 2258 ms 254796 KB Output is correct
5 Correct 2150 ms 254796 KB Output is correct
6 Correct 2237 ms 254808 KB Output is correct
7 Correct 1969 ms 254912 KB Output is correct
8 Execution timed out 8058 ms 84776 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1990 ms 254832 KB Output is correct
2 Correct 244 ms 254760 KB Output is correct
3 Correct 2102 ms 254768 KB Output is correct
4 Correct 249 ms 254788 KB Output is correct
5 Execution timed out 8034 ms 84848 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2090 ms 254784 KB Output is correct
2 Correct 1942 ms 254772 KB Output is correct
3 Correct 1965 ms 254776 KB Output is correct
4 Correct 2017 ms 254788 KB Output is correct
5 Correct 1974 ms 254764 KB Output is correct
6 Correct 1970 ms 254712 KB Output is correct
7 Correct 239 ms 254716 KB Output is correct
8 Correct 1972 ms 254700 KB Output is correct
9 Correct 2076 ms 254780 KB Output is correct
10 Correct 1992 ms 254788 KB Output is correct
11 Correct 2436 ms 254784 KB Output is correct
12 Correct 1985 ms 254764 KB Output is correct
13 Correct 1982 ms 254744 KB Output is correct
14 Correct 2212 ms 254904 KB Output is correct
15 Correct 2028 ms 254816 KB Output is correct
16 Correct 452 ms 254788 KB Output is correct
17 Correct 2106 ms 254792 KB Output is correct
18 Correct 294 ms 254788 KB Output is correct
19 Correct 229 ms 254676 KB Output is correct
20 Correct 2236 ms 254796 KB Output is correct
21 Correct 228 ms 254776 KB Output is correct
22 Correct 243 ms 254740 KB Output is correct
23 Correct 292 ms 254716 KB Output is correct
24 Correct 245 ms 254728 KB Output is correct
25 Correct 388 ms 254816 KB Output is correct
26 Correct 1321 ms 254788 KB Output is correct
27 Correct 267 ms 254728 KB Output is correct
28 Correct 1921 ms 254772 KB Output is correct
29 Correct 237 ms 254720 KB Output is correct
30 Correct 4545 ms 254792 KB Output is correct
31 Correct 4456 ms 254792 KB Output is correct
32 Correct 311 ms 254736 KB Output is correct
33 Correct 2874 ms 254796 KB Output is correct
34 Correct 4552 ms 254788 KB Output is correct
35 Correct 2730 ms 254796 KB Output is correct
36 Correct 1059 ms 254792 KB Output is correct
37 Correct 4558 ms 254788 KB Output is correct
38 Correct 3782 ms 254904 KB Output is correct
39 Correct 3630 ms 254704 KB Output is correct
40 Correct 2140 ms 254788 KB Output is correct
41 Correct 1822 ms 254792 KB Output is correct
42 Correct 2655 ms 254784 KB Output is correct
43 Correct 1020 ms 254788 KB Output is correct
44 Correct 2449 ms 254712 KB Output is correct
45 Correct 1008 ms 254792 KB Output is correct
46 Correct 2322 ms 254872 KB Output is correct
47 Correct 774 ms 254796 KB Output is correct
48 Correct 626 ms 254792 KB Output is correct
49 Correct 2270 ms 254772 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2265 ms 254752 KB Output is correct
2 Correct 2259 ms 254732 KB Output is correct
3 Correct 4046 ms 254816 KB Output is correct
4 Correct 2009 ms 254808 KB Output is correct
5 Correct 354 ms 254792 KB Output is correct
6 Correct 1968 ms 254808 KB Output is correct
7 Correct 1962 ms 254808 KB Output is correct
8 Correct 1943 ms 254740 KB Output is correct
9 Correct 1986 ms 254756 KB Output is correct
10 Correct 4737 ms 254800 KB Output is correct
11 Correct 4660 ms 254808 KB Output is correct
12 Correct 3054 ms 254780 KB Output is correct
13 Correct 4526 ms 254804 KB Output is correct
14 Correct 5008 ms 254776 KB Output is correct
15 Correct 4403 ms 254712 KB Output is correct
16 Correct 2036 ms 254860 KB Output is correct
17 Correct 4231 ms 254824 KB Output is correct
18 Correct 4372 ms 254812 KB Output is correct
19 Correct 1852 ms 254852 KB Output is correct
20 Correct 903 ms 254856 KB Output is correct
21 Correct 2845 ms 254820 KB Output is correct
22 Correct 849 ms 254856 KB Output is correct
23 Correct 3508 ms 254800 KB Output is correct
24 Correct 4021 ms 254824 KB Output is correct
25 Correct 2356 ms 254852 KB Output is correct
26 Correct 4407 ms 254804 KB Output is correct
27 Correct 3788 ms 254816 KB Output is correct
28 Correct 2547 ms 254744 KB Output is correct
29 Correct 4185 ms 254820 KB Output is correct
30 Correct 2688 ms 254708 KB Output is correct
31 Correct 4278 ms 254820 KB Output is correct
32 Correct 2104 ms 254864 KB Output is correct
33 Correct 2041 ms 254856 KB Output is correct
34 Correct 562 ms 254856 KB Output is correct
35 Correct 697 ms 254856 KB Output is correct
36 Correct 2656 ms 254800 KB Output is correct
37 Correct 700 ms 254832 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2482 ms 254828 KB Output is correct
2 Correct 2435 ms 254920 KB Output is correct
3 Correct 2742 ms 255112 KB Output is correct
4 Execution timed out 8074 ms 84832 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1989 ms 254784 KB Output is correct
2 Correct 243 ms 254736 KB Output is correct
3 Correct 235 ms 254712 KB Output is correct
4 Correct 2258 ms 254796 KB Output is correct
5 Correct 2150 ms 254796 KB Output is correct
6 Correct 2237 ms 254808 KB Output is correct
7 Correct 1969 ms 254912 KB Output is correct
8 Execution timed out 8058 ms 84776 KB Time limit exceeded
9 Halted 0 ms 0 KB -