제출 #797220

#제출 시각아이디문제언어결과실행 시간메모리
797220finn__L-triominoes (CEOI21_ltriominoes)C++17
28 / 100
71 ms596 KiB
#include <bits/stdc++.h> using namespace std; constexpr size_t W = 6, 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 x = y.transpose(); 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[i] & x.mat[j]).any(); return res; } bmatrix pow(size_t n) const { bmatrix a = *this; bmatrix res; for (size_t i = 0; i < 1U << W; ++i) res.mat[i][i] = 1; while (n) { if (n & 1) res = res * a; a = a * a; n >>= 1; } return res; } 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]; bitset<1 << W> f[1 << W]; vector<uint32_t> pre[1 << W][1 << W]; bitset<1 << (W << 1)> visited; 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 i = 0; i < 1U << w; ++i) f[i][0] = 1; for (size_t i = 0; i < 1U << w; ++i) for (size_t j = 0; j < 1U << w; ++j) if (f[i][j]) 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)); f[ni][nj] = 1; pre[ni][nj].push_back((i << W) | j); } if (h + 1 < w && !(j & (1 << h)) && !(j & (1 << (h + 1)))) { size_t ni = i ^ (1 << h), nj = j ^ (1 << h) ^ (1 << (h + 1)); f[ni][j] = 1; pre[ni][nj].push_back((i << W) | j); } if (h + 1 < w && !(i & (1 << (h + 1))) && !(j & (1 << h))) { size_t ni = i ^ (1 << h) ^ (1 << (h + 1)), nj = j ^ (1 << h); f[ni][nj] = 1; pre[ni][nj].push_back((i << W) | j); } 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)); f[ni][nj] = 1; pre[ni][nj].push_back((i << W) | j); } } bmatrix transitions; for (size_t i = 0; i < 1 << w; ++i) { queue<uint32_t> q; q.push((((1 << w) - 1) << W) | i); visited.reset(); while (!q.empty()) { uint32_t u = q.front(); q.pop(); if (!(u & ((1 << W) - 1))) { transitions.mat[i][u >> W] = 1; } for (auto const &v : pre[u >> W][u & ((1 << W) - 1)]) if (!visited[v]) { q.push(v); visited[v] = 1; } } } sort(p, p + k, [](auto const &a, auto const &b) { return a.second < b.second; }); bitset<1 << W> state, state2; 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 = transitions.pow(p[i].second - pos).mul_vec(state); 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 = transitions.pow(h - 1 - pos).mul_vec(state); } cout << (state[(1 << w) - 1] ? "YES" : "NO") << '\n'; }

컴파일 시 표준 에러 (stderr) 메시지

ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:109:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     for (size_t i = 0; i < 1 << w; ++i)
      |                        ~~^~~~~~~~
ltrominoes.cpp:159:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  159 |         for (size_t i = 0; i < 1 << w; ++i)
      |                            ~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...