GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 79.5% 70 / 0 / 88
Functions: 46.7% 7 / 0 / 15
Branches: 68.2% 75 / 0 / 110
test/cpv_local/opt/dlx.bzoj1501.cpp
Line Branch Exec Source
1 // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/1501
2
3 #include "../../../src/opt/dlx/lib.hpp"
4 #include "../../../src/util/traits/others/lib.hpp"
5
6 using namespace tifa_libs;
7 namespace PieceOperation {
8 ✗ constexpr u32 flip4(u32 x) { return (x & 1) << 3 | ((x >> 1) & 1) << 2 | ((x >> 2) & 1) << 1 | ((x >> 3) & 1); }
9 ✗ constexpr u32 expand4(u32 x) { return (x & 8) << 9 | (x & 4) << 6 | (x & 2) << 3 | (x & 1); }
10 ✗ constexpr u32 flip16(u32 x) { return flip4((x >> 12) & 15) << 12 | flip4((x >> 8) & 15) << 8 | flip4((x >> 4) & 15) << 4 | flip4(x & 15); }
11 ✗ constexpr u32 rot16(u32 x) { return expand4(flip4((x >> 12) & 15)) << 3 | expand4(flip4((x >> 8) & 15)) << 2 | expand4(flip4((x >> 4) & 15)) << 1 | expand4(flip4(x & 15)); }
12 ✗ constexpr u32 rearrange16(u32 x) {
13 ✗ assert(x);
14 ✗ while (!(x & 0xf000)) x <<= 4;
15 ✗ while (!(x & 0x8888)) x = (((x >> 12) & 7) << 13) | (((x >> 8) & 7) << 9) | (((x >> 4) & 7) << 5) | ((x & 7) << 1);
16 ✗ return x;
17 }
18
19 const u32 pieces_base[] = {0x1c800, 0x2f000, 0x3e800, 0x4cc00, 0x588e0, 0x6f400, 0x7ea00, 0x8ec00, 0x9e300, 0xa4e40, 0xb8c60, 0xcf800};
20 ✗ constexpr u32 flip(u32 piece) { return (piece & 0xf0000) | rearrange16(flip16(piece & 0xffff)); }
21 ✗ constexpr u32 rotate(u32 piece) { return (piece & 0xf0000) | rearrange16(rot16(piece & 0xffff)); }
22
23 ✗ std::vector<u32> getall() {
24 ✗ std::set<u32> s;
25 ✗ for (auto&& i : pieces_base) s.merge(std::set<u32>{i, rotate(i), rotate(rotate(i)), rotate(rotate(rotate(i))), flip(i), rotate(flip(i)), rotate(rotate(flip(i))), rotate(rotate(rotate(flip(i))))});
26 ✗ std::vector<u32> ans;
27 ✗ for (auto&& j : s) ans.push_back(j);
28 ✗ return ans;
29 ✗ }
30 } // namespace PieceOperation
31
32 const u32 pieces[60] = {0x14c00, 0x18c00, 0x1c400, 0x1c800, 0x28888, 0x2f000, 0x32e00, 0x344c0, 0x388c0, 0x38e00, 0x3c440, 0x3c880, 0x3e200, 0x3e800, 0x4cc00, 0x522e0, 0x588e0, 0x5e220, 0x5e880, 0x62f00, 0x644c4, 0x64c44, 0x64f00, 0x688c8, 0x68c88, 0x6f200, 0x6f400, 0x7ae00, 0x7c4c0, 0x7c8c0, 0x7ea00, 0x84cc0, 0x86e00, 0x88cc0, 0x8cc40, 0x8cc80, 0x8ce00, 0x8e600, 0x8ec00, 0x93e00, 0x944c8, 0x94c88, 0x97c00, 0x988c4, 0x98c44, 0x9c700, 0x9e300, 0xa4e40, 0xb26c0, 0xb6c80, 0xb8c60, 0xbc620, 0xc1f00, 0xc444c, 0xc888c, 0xc8f00, 0xcc444, 0xcc888, 0xcf100, 0xcf800};
33
34 class Board {
35 protected:
36 u64 data[10] = {};
37 bool pplaced[16] = {};
38 u32 pcord[16][2] = {{10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}, {10, 10}};
39
40 public:
41 constexpr Board() = default;
42
43 10 friend auto& operator>>(istream_c auto& is, Board& board) {
44 10 strn s;
45
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 10 times.
 110 for (u64 _ = 0xfffffffff, i = 0; i < 10; ++i, _ >>= 4) {
46
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 is >> s;
47 100 board.data[i] = _;
48
2/2
✓ Branch 0 taken 550 times.
✓ Branch 1 taken 100 times.
 650 for (usz j = 0; j <= i; ++j)
49
3/4
✓ Branch 1 taken 550 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 82 times.
✓ Branch 4 taken 468 times.
 550 if (isalpha(s[j])) {
50
1/2
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
 82 board.pplaced[s[j] & 15] = true;
51
1/2
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
 82 auto& coord = board.pcord[s[j] & 15];
52 82 coord[0] = std::min(coord[0], (u32)i);
53 82 coord[1] = std::min(coord[1], (u32)j);
54
1/2
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
 82 board.data[i] |= u64(s[j] & 15) << (4 * (9 - j));
55 }
56 }
57 10 return is;
58 10 }
59
60 8 friend auto& operator<<(ostream_c auto& os, Board const& board) {
61 u32 _;
62
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 8 times.
 88 for (usz i = 0; i < 10; ++i) {
63
3/4
✓ Branch 1 taken 440 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 440 times.
✓ Branch 5 taken 80 times.
 520 for (usz j = 0; j <= i; ++j) os << ((_ = board.get(i, j)) ? (char)(_ + '@') : '.');
64 80 os << '\n';
65 }
66 8 return os;
67 }
68
69 440 constexpr u32 get(usz row, usz col) const {
70
2/4
✓ Branch 0 taken 440 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 440 times.
✗ Branch 3 not taken.
 440 assert(row < 10 && col <= row);
71 440 return (data[row] >> (4 * (9 - col))) & 15;
72 }
73
74 33000 constexpr bool can_place_4x4(usz row, usz col, usz piece) const {
75
2/4
✓ Branch 0 taken 33000 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 33000 times.
 33000 if (row > 9 || col > row) return false;
76 33000 auto&& pid = (piece >> 16) & 15;
77
2/2
✓ Branch 0 taken 4070 times.
✓ Branch 1 taken 28930 times.
 33000 if (pplaced[pid]) {
78
4/4
✓ Branch 0 taken 502 times.
✓ Branch 1 taken 3568 times.
✓ Branch 2 taken 428 times.
✓ Branch 3 taken 74 times.
 4070 if (row != pcord[pid][0] || col != pcord[pid][1])
79 3996 return false;
80 } else
81 28930 pid = 0;
82
83 29004 usz p[4] = {(piece >> 12) & 15, (piece >> 8) & 15, (piece >> 4) & 15, piece & 15};
84
85
2/2
✓ Branch 0 taken 56038 times.
✓ Branch 1 taken 8730 times.
 64768 for (usz i = 0, s = 0, end_ = !!p[0] + !!p[1] + !!p[2] + !!p[3]; i < end_; ++i) {
86
2/2
✓ Branch 0 taken 5346 times.
✓ Branch 1 taken 50692 times.
 56038 if (row + i > 9) return false;
87 50692 isz ofs = 4 * (6 - (isz)col);
88
2/2
✓ Branch 0 taken 3641 times.
✓ Branch 1 taken 47051 times.
 50692 s = (ofs < 0 ? (data[row + i] << -ofs | ((1ull << -ofs) - 1)) : (data[row + i] >> ofs)) & 0xffff;
89
6/6
✓ Branch 0 taken 44668 times.
✓ Branch 1 taken 6024 times.
✓ Branch 2 taken 38805 times.
✓ Branch 3 taken 11887 times.
✓ Branch 4 taken 33220 times.
✓ Branch 5 taken 17472 times.
 50692 s = usz(((s >> 12) & 15) == pid) << 3 | usz(((s >> 8) & 15) == pid) << 2 | usz(((s >> 4) & 15) == pid) << 1 | ((s & 15) == pid);
90
2/2
✓ Branch 0 taken 14928 times.
✓ Branch 1 taken 35764 times.
 50692 if (p[i] & (p[i] ^ s)) return false;
91 }
92 8730 return true;
93 }
94
95 96 constexpr void place_4x4(usz row, usz col, usz piece) {
96 96 auto&& pid = (piece >> 16) & 15;
97
2/2
✓ Branch 1 taken 320 times.
✓ Branch 2 taken 96 times.
 416 for (usz i = row; i < std::min((usz)10, row + 4); ++i)
98
2/2
✓ Branch 1 taken 1256 times.
✓ Branch 2 taken 320 times.
 1576 for (usz j = col; j < std::min((usz)10, col + 4); ++j) data[i] |= ((pid * !!(piece & (1 << (15 - (i - row) * 4 - j + col)))) << (4 * (9 - j)));
99 96 }
100 };
101
102 10 int main() {
103 using std::cin, std::cout;
104
105 10 Board board;
106
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 cin >> board;
107 10 vvecb maps;
108 10 vec<pt3<usz>> coord;
109 {
110 139680 auto encode = [](usz row, usz col) { return 12 + row * (row + 1) / 2 + col; };
111 10 vecb _;
112
2/2
✓ Branch 0 taken 600 times.
✓ Branch 1 taken 10 times.
 610 for (usz id = 0; id < sizeof(pieces) / sizeof(pieces[0]); ++id)
113
2/2
✓ Branch 0 taken 6000 times.
✓ Branch 1 taken 600 times.
 6600 for (usz i = 0; i < 10; ++i)
114
2/2
✓ Branch 0 taken 33000 times.
✓ Branch 1 taken 6000 times.
 39000 for (usz j = 0; j <= i; ++j)
115
2/2
✓ Branch 1 taken 8730 times.
✓ Branch 2 taken 24270 times.
 33000 if (board.can_place_4x4(i, j, pieces[id])) {
116 8730 _.clear();
117
1/2
✓ Branch 1 taken 8730 times.
✗ Branch 2 not taken.
 8730 _.resize(67);
118
1/2
✓ Branch 1 taken 8730 times.
✗ Branch 2 not taken.
 8730 _[((pieces[id] >> 16) & 15) - 1] = 1;
119
2/2
✓ Branch 0 taken 34920 times.
✓ Branch 1 taken 8730 times.
 43650 for (usz _i = 0; _i < 4; ++_i)
120
3/4
✓ Branch 2 taken 139680 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 139680 times.
✓ Branch 6 taken 34920 times.
 174600 for (usz _j = 0; _j < 4; ++_j) _[encode(i + _i, j + _j)] = pieces[id] & (1 << (15 - _i * 4 - _j));
121
1/2
✓ Branch 1 taken 8730 times.
✗ Branch 2 not taken.
 8730 coord.emplace_back(id, i, j);
122
1/2
✓ Branch 1 taken 8730 times.
✗ Branch 2 not taken.
 8730 maps.push_back(_);
123 }
124 10 }
125
126 10 auto res = dlx(maps).dance(fn_0);
127
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 8 times.
 10 if (!res) {
128
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 cout << "No solution\n";
129 2 return 0;
130 }
131
3/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 96 times.
✓ Branch 9 taken 8 times.
 104 for (auto x : res.value()) {
132 96 auto&& [id, i, j] = coord[x - 1];
133 96 board.place_4x4(i, j, pieces[id]);
134 }
135
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 cout << board;
136
6/6
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 2 times.
✓ Branch 4 taken 8 times.
✓ Branch 5 taken 2 times.
✓ Branch 7 taken 8 times.
✓ Branch 8 taken 2 times.
 22 }
137