1 条题解
-
0

#include <bits/stdc++.h> #define EB emplace_back using std::cin; using std::cout; using std::vector; typedef unsigned int u32; typedef unsigned long long u64; typedef unsigned __int128 u128, u128set[9]; typedef std::pair <int, int> pr; typedef std::pair <u64, int> pli; constexpr u128 one = 1, row_mask = 0x1ffull, col_mask = one << 72 | 0x8040201008040201ull; const int basic_res[6][3] = { {0, 1, 2}, {1, 0, 2}, {2, 1, 0}, {0, 2, 1}, {1, 2, 0}, {2, 0, 1} }; const vector <pr> basic_op[6] = { {}, {{0, 1}}, {{0, 2}}, {{1, 2}}, {{0, 1}, {1, 2}}, {{1, 2}, {0, 1}} }; struct permutation {vector <pr> op; int res[9];} p[1296]; u64 compress(u128 x) { static u64 y; x ^= x << 11, x ^= x >> 45, x ^= x << 14, y = x % 0xffffffffffffffc5ull; return y ^= y << 13, y ^= y >> 7, y ^= y << 17, y * 0xb7e151628aed2a6b + 0x243f6a8885a308d3ull; } struct sudoku { char s[9][9]; u128set pos, tpos; u128set rowperm[1296], colperm[1296], tcolperm[1296]; u64 rowperm_h[1296], colperm_h[1296], tcolperm_h[1296]; friend std::istream & operator >> (std::istream &in, sudoku &B) { int i; static char buf[20]; for (i = 0; i < 9; ++i) in >> buf, memcpy(B.s[i], buf, 9); return in; } void init() { int i, j, k; u32 x; u128 part[9][9]; memset(pos, 0, 144), memset(tpos, 0, 144); for (i = 0; i < 9; ++i) for (j = 0; j < 9; ++j) if ((x = (u32)s[i][j] - 49u) < 9u) pos[x] |= one << (i * 9 + j), tpos[x] |= one << (i + j * 9); // row for (i = 0; i < 9; ++i) for (j = 0; j < 9; ++j) part[i][j] = pos[i] >> (j * 9) & row_mask; for (k = 0; k < 1296; ++k) { u128set &Z = rowperm[k]; int (&q)[9] = p[k].res; u64 &H = rowperm_h[k]; H = 0; for (i = 0; i < 9; ++i) { for (Z[i] = j = 0; j < 9; ++j) Z[i] |= part[i][q[j]] << (j * 9); H ^= compress(Z[i]); } } // column for (i = 0; i < 9; ++i) for (j = 0; j < 9; ++j) part[i][j] = pos[i] >> j & col_mask; for (k = 0; k < 1296; ++k) { u128set &Z = colperm[k]; int (&q)[9] = p[k].res; u64 &H = colperm_h[k]; H = 0; for (i = 0; i < 9; ++i) { for (Z[i] = j = 0; j < 9; ++j) Z[i] |= part[i][q[j]] << j; H ^= compress(Z[i]); } } // transpose + column for (i = 0; i < 9; ++i) for (j = 0; j < 9; ++j) part[i][j] = tpos[i] >> j & col_mask; for (k = 0; k < 1296; ++k) { u128set &Z = tcolperm[k]; int (&q)[9] = p[k].res; u64 &H = tcolperm_h[k]; H = 0; for (i = 0; i < 9; ++i) { for (Z[i] = j = 0; j < 9; ++j) Z[i] |= part[i][q[j]] << j; H ^= compress(Z[i]); } } } pr compare(const sudoku &B) { int i, j, k, a, b, u, v; static pli w[3888]; static u128 buf[18]; static int HC = 0; for (i = 0; i < 1296; ++i) w[i] = pli(rowperm_h[i], i), w[i + 1296] = pli(B.colperm_h[i], i + 0x10000), w[i + 2592] = pli(B.tcolperm_h[i], i + 0x30000); std::sort(w, w + 3888); for (j = i = 0; i < 3888; i = j) { for (k = i - 1; j < 3888 && w[i].first == w[j].first; ++j) if (!(w[j].second & 0x10000)) k = j; if (i == ++k || k == j) continue; for (a = i; a < k; ++a) for (b = k; b < j; ++b) { std::tie(u, v) = pr(w[a].second, w[b].second), v &= 0x2ffff, memcpy(buf, rowperm[u], 144), memcpy(buf + 9, v & 0x20000u ? B.tcolperm[v & 0xffff] : B.colperm[v], 144); std::sort(buf, buf + 9), std::sort(buf + 9, buf + 18); if (!memcmp(buf, buf + 9, 144)) return pr(u, v); fprintf(stderr, "Hash collision %d time(s).\n", ++HC); } } return pr(-1, -1); } } a[20]; void gen_permutations() { int I, i, j, k, si, sj, sk, v, o[9], O[3], n = 0; vector <pr> w; for (I = 0; I < 6; ++I) { memcpy(O, basic_res + I, 12), w.clear(); for (const pr &e : basic_op[I]) w.EB(~e.first, ~e.second); si = w.size(); for (i = 0; i < 6; ++i) { memcpy(o, basic_res + i, 12), w.resize(si); for (const pr &e : basic_op[i]) w.EB(e); sj = w.size(); for (j = 0; j < 6; ++j) { memcpy(o + 3, basic_res + j, 12), w.resize(sj); for (const pr &e : basic_op[j]) w.EB(e.first + 3, e.second + 3); sk = w.size(); for (k = 0; k < 6; ++k) { memcpy(o + 6, basic_res + k, 12), w.resize(sk); for (const pr &e : basic_op[k]) w.EB(e.first + 6, e.second + 6); for (v = 0; v < 9; ++v) p[n].res[v] = O[v / 3] * 3 + o[v]; p[n++].op = w; } } } } assert(n == 1296); } void output(const sudoku &A, const sudoku &B, int perm_a, int perm_b) { int i, j, size = 0; static std::ostringstream os; os.str(""); bool final_flip = perm_b & 0x20000; perm_b &= 0xffff; u128set Ai, Bi; for (const pr &e : p[perm_a].op) if (++size, e.first >> 31) os << 'R' << ' ' << -e.first << ' ' << -e.second << '\n'; else os << 'r' << ' ' << e.first + 1 << ' ' << e.second + 1 << '\n'; for (i = p[perm_b].op.size() - 1; i >= 0; --i) { const pr &e = p[perm_b].op[i]; if (++size, e.first >> 31) os << 'C' << ' ' << -e.first << ' ' << -e.second << '\n'; else os << 'c' << ' ' << e.first + 1 << ' ' << e.second + 1 << '\n'; } if (final_flip) ++size, os << 'F' << '\n'; memcpy(Ai, A.rowperm[perm_a], 144), memcpy(Bi, final_flip ? B.tcolperm[perm_b] : B.colperm[perm_b], 144); for (i = 0; i < 8; ++i) { j = std::find(Ai + i, Ai + 9, Bi[i]) - Ai, assert(j != 9); if (i != j) ++size, os << 'D' << ' ' << i + 1 << ' ' << j + 1 << '\n', std::swap(Ai[i], Ai[j]); } assert(Ai[8] == Bi[8]); cout << size << '\n' << os.str(); } int main() { int i, j, u, v, n; std::ios::sync_with_stdio(false), cin.tie(NULL); gen_permutations(), cin >> n; for (i = 0; i < n; ++i) cin >> a[i], a[i].init(); for (i = 0; i + 1 < n; ++i) for (j = i + 1; j < n; ++j) { std::tie(u, v) = a[i].compare(a[j]); if (~u) cout << "Yes\n", output(a[i], a[j], u, v); else cout << "No\n"; } return 0; }
- 1
信息
- ID
- 6160
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 0
- 上传者