# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
797416 | 2023-07-29T10:51:06 Z | finn__ | L-triominoes (CEOI21_ltriominoes) | C++17 | 722 ms | 468 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 { uint64_t mat[1 << W][1 << (W - 6)]; void mul_vec(uint64_t const v[1 << (W - 6)], uint64_t res[1 << (W - 6)]) const { memset(res, 0, sizeof res); for (size_t i = 0; i < 1U << W; ++i) for (size_t j = 0; j < 1U << (W - 6); ++j) if (mat[i][j] & v[j]) { res[i] = 1; break; } } }; pair<size_t, size_t> p[K]; bmatrix transitions; int main() { ios_base::sync_with_stdio(0); cin.tie(0); size_t w, h, k; cin >> w >> h >> k; assert(h <= 1000); 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); } } } } uint64_t *state = (uint64_t *)malloc((1 << (W - 6)) * sizeof *state); uint64_t *state2 = (uint64_t *)malloc((1 << (W - 6)) * sizeof *state2); 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 >> 6] ^= 1 << (x & 63); } else state[0] = 1; while (i < k) { while (pos < p[i].second) { transitions.mul_vec(state, state2), ++pos; swap(state, state2); } 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; memset(state2, 0, sizeof state2); for (size_t i = 0; i < 1 << w; ++i) if (!(i & x) && (state[i >> 6] & (i & 63))) state2[(i ^ x) >> 6] |= 1 << ((i ^ x) & 63); state = state2; } while (pos < h - 1) { transitions.mul_vec(state, state2), ++pos; swap(state, state2); } cout << ((state[((1 << w) - 1) >> 6] & (1 << (((1 << w) - 1) & 63))) ? "YES" : "NO") << '\n'; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 722 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 468 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 468 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 468 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 468 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 722 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |