Submission #800554

#TimeUsernameProblemLanguageResultExecution timeMemory
800554JohannL-triominoes (CEOI21_ltriominoes)C++14
17 / 100
2277 ms67104 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector<bool> vb; typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pii> vpii; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() const int maxW = 13; int W, H, K; map<int, int> blocked; typedef bitset<1 << maxW> bs; typedef vector<bs> vbs; typedef vector<vbs> vvbs; bs dp[2]; bs mat[1 << maxW]; vvbs lift; vvbs mod; void dfs(int idx, int base, int next, bs &nextdp) { if (idx == W) { nextdp[next] = true; return; } if (base & (1 << idx)) dfs(idx + 1, base, next, nextdp); else { // _X my pos: 1 << idx // TT // _T if (idx < W - 1 && ((3 << idx) & next) == 0) dfs(idx + 1, base | (1 << idx), next | (3 << idx), nextdp); // _TT // _T_ if (idx > 0 && ((3 << (idx - 1)) & next) == 0) dfs(idx + 1, base | (1 << idx), next | (3 << (idx - 1)), nextdp); // T_ // TT if (idx < W - 1 && (base & (3 << idx)) == 0 && (next & (2 << idx)) == 0) dfs(idx + 2, base | (3 << idx), next | (2 << idx), nextdp); // _T // TT if (idx < W - 1 && (base & (3 << idx)) == 0 && (next & (1 << idx)) == 0) dfs(idx + 2, base | (3 << idx), next | (1 << idx), nextdp); } } void mul(bs &base, int liftidx, bs &re, int block = 0) { re = 0; for (int j = 0; j < 1 << W; ++j) { if (!base[j]) continue; if (j & block) continue; re |= lift[liftidx][j | block]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> W >> H >> K; for (int k = 0, x, y; k < K; ++k) { cin >> x >> y; --x, --y; blocked[y] = blocked[y] | (1 << x); } lift.assign(4, vbs(1 << W)); for (int i = 0; i < 1 << W; ++i) dfs(0, i, 0, lift[0][i]); for (int j = 1; j < sz(lift); ++j) for (int i = 0; i < 1 << W; ++i) mul(lift[j - 1][i], j - 1, lift[j][i]); assert(W < 13); mod.assign(1 << W, vbs(3)); for (int i = 0; i < (1 << W); ++i) { mul(lift[3][i], 2, mod[i][0]); mul(mod[i][0], 0, mod[i][1]); mul(mod[i][1], 0, mod[i][2]); } assert(W < 13); if (false) { dp[0] = 0; dp[0][0] = true; for (int i = 0; i < H; ++i) { int ii = i & 1; int ni = ii ^ 1; dp[ni] = 0; mul(dp[ii], 0, dp[ni], blocked[i]); } if (dp[H & 1][0]) cout << "YES\n"; else cout << "NO\n"; } else { bs start = 0, tmp; start[0] = 1; blocked[H - 1] = blocked[H - 1] | 0; int h = 0; for (pii p : blocked) { int delta = p.first - h; if (delta >= 11) { tmp = 0; for (int i = 0; i < (1 << W); ++i) if (start[i]) tmp |= mod[i][delta % 3]; swap(tmp, start); h = p.first; } else { for (int j = sz(lift) - 1; j >= 0; --j) { if (p.first - h >= (1 << j)) { h += (1 << j); mul(start, j, tmp); swap(start, tmp); } } assert(p.first == h); } mul(start, 0, tmp, p.second); swap(start, tmp); ++h; } if (start[0]) cout << "YES\n"; else cout << "NO\n"; } return 0; }
#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...