src/opt/dlx/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | class dlx { | ||
| 8 | struct node { | ||
| 9 | u32 l, r, u, d, row, col; | ||
| 10 | 49052 | CEXP node(u32 l = 0, u32 r = 0, u32 u = 0, u32 d = 0, u32 row = 0, u32 col = 0) NE : l(l), r(r), u(u), d(d), row(row), col(col) {} | |
| 11 | }; | ||
| 12 | vec<node> data; | ||
| 13 | vecu cnt_col; | ||
| 14 | const bool mans; | ||
| 15 | |||
| 16 | #define l_(x) data[x].l | ||
| 17 | #define r_(x) data[x].r | ||
| 18 | #define u_(x) data[x].u | ||
| 19 | #define d_(x) data[x].d | ||
| 20 | #define row_(x) data[x].row | ||
| 21 | #define col_(x) data[x].col | ||
| 22 | // NOLINTNEXTLINE(misc-const-correctness) | ||
| 23 | #define dlxfor_(i, l, dir) for (u32 ied__ = (l), i = dir##_(ied__); i != ied__; i = dir##_(i)) | ||
| 24 | |||
| 25 | 27521 | CEXP void remove_(u32 col) NE { | |
| 26 | 27521 | r_(l_(col)) = r_(col), l_(r_(col)) = l_(col); | |
| 27 |
2/2✓ Branch 2 taken 324496 times.
✓ Branch 3 taken 27521 times.
|
352017 | dlxfor_ (i, col, d) |
| 28 |
2/2✓ Branch 10 taken 1517586 times.
✓ Branch 11 taken 324496 times.
|
1842082 | dlxfor_ (j, i, r) u_(d_(j)) = u_(j), d_(u_(j)) = d_(j), --cnt_col[col_(j)]; |
| 29 | 27521 | } | |
| 30 | 27425 | CEXP void resume_(u32 col) NE { | |
| 31 | 27425 | r_(l_(col)) = l_(r_(col)) = col; | |
| 32 |
2/2✓ Branch 2 taken 324184 times.
✓ Branch 3 taken 27425 times.
|
351609 | dlxfor_ (i, col, u) |
| 33 |
2/2✓ Branch 8 taken 1516144 times.
✓ Branch 9 taken 324184 times.
|
1840328 | dlxfor_ (j, i, r) u_(d_(j)) = d_(u_(j)) = j, ++cnt_col[col_(j)]; |
| 34 | 27425 | } | |
| 35 | template <class F> | ||
| 36 | 4790 | CEXP bool dance_(vecu& ans, F&& cb) NE { | |
| 37 | 4790 | u32 now = r_(0); | |
| 38 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4782 times.
|
4790 | if (now == 0) { |
| 39 | 8 | cb(ans); | |
| 40 | 8 | return true; | |
| 41 | } | ||
| 42 |
2/2✓ Branch 2 taken 117264 times.
✓ Branch 3 taken 4782 times.
|
122046 | dlxfor_ (i, 0, r) |
| 43 |
2/2✓ Branch 2 taken 11511 times.
✓ Branch 3 taken 105753 times.
|
117264 | if (cnt_col[i] < cnt_col[now]) now = i; |
| 44 | 4782 | remove_(now); | |
| 45 | 4782 | bool ret = false; | |
| 46 |
2/2✓ Branch 2 taken 4780 times.
✓ Branch 3 taken 4686 times.
|
9466 | dlxfor_ (i, now, d) { |
| 47 | 4780 | ans.push_back(row_(i)); | |
| 48 |
2/2✓ Branch 4 taken 22739 times.
✓ Branch 5 taken 4780 times.
|
27519 | dlxfor_ (j, i, r) remove_(col_(j)); |
| 49 | 4780 | ret |= dance_(ans, std::forward<F>(cb)); | |
| 50 |
2/2✓ Branch 4 taken 22739 times.
✓ Branch 5 taken 4780 times.
|
27519 | dlxfor_ (j, i, l) resume_(col_(j)); |
| 51 |
3/4✓ Branch 0 taken 4780 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 96 times.
✓ Branch 3 taken 4684 times.
|
4780 | if (!mans && ret) return true; |
| 52 | 4684 | ans.pop_back(); | |
| 53 | } | ||
| 54 | 4686 | resume_(now); | |
| 55 | 4686 | return ret; | |
| 56 | } | ||
| 57 | 8730 | CEXP void ins_row_(u32 row, spnu cols) NE { | |
| 58 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 8730 times.
|
8730 | assert(row > 0); |
| 59 | 8730 | cu32 n = (u32)data.size(); | |
| 60 |
2/2✓ Branch 1 taken 48372 times.
✓ Branch 2 taken 8730 times.
|
57102 | flt_ (u32, i, 0, (u32)cols.size()) { |
| 61 | 48372 | data.emplace_back(n + i - 1, n + i + 1, u_(cols[i]), cols[i], row, cols[i]); | |
| 62 | 48372 | u_(cols[i]) = d_(u_(cols[i])) = n + i; | |
| 63 | 48372 | ++cnt_col[cols[i]]; | |
| 64 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 48372 times.
|
48372 | if (d_(cols[i]) == cols[i]) d_(cols[i]) = n + i; |
| 65 | } | ||
| 66 | 8730 | r_(l_(n) = u32(data.size() - 1)) = n; | |
| 67 | 8730 | } | |
| 68 | |||
| 69 | public: | ||
| 70 | 10 | CEXPE dlx(cT_(vvecb) grid, bool multi_ans = false) NE : data{}, cnt_col{}, mans{multi_ans} { | |
| 71 | 10 | cu32 col = (u32)grid[0].size(); | |
| 72 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
|
10 | assert(col > 0), cnt_col.resize(col + 1), data.reserve(col + 1); |
| 73 |
2/2✓ Branch 1 taken 680 times.
✓ Branch 2 taken 10 times.
|
690 | flt_ (u32, i, 0, col + 1) data.emplace_back(i - 1, i + 1, i, i, 0, i); |
| 74 | 10 | r_(l_(0) = col) = 0; | |
| 75 |
2/2✓ Branch 1 taken 8730 times.
✓ Branch 2 taken 10 times.
|
8740 | flt_ (u32, i, 0, (u32)grid.size()) { |
| 76 | 8730 | vecu _; | |
| 77 | 8730 | _.reserve(col); | |
| 78 |
2/2✓ Branch 0 taken 584910 times.
✓ Branch 1 taken 8730 times.
|
593640 | flt_ (u32, j, 0, col) |
| 79 |
2/2✓ Branch 2 taken 48372 times.
✓ Branch 3 taken 536538 times.
|
584910 | if (grid[i][j]) _.push_back(j + 1); |
| 80 |
1/2✓ Branch 2 taken 8730 times.
✗ Branch 3 not taken.
|
8730 | if (_.shrink_to_fit(); !_.empty()) ins_row_(i + 1, _); |
| 81 | 8730 | } | |
| 82 | 10 | } | |
| 83 | template <class F> | ||
| 84 | requires requires(F f, vecu sol) { f(sol); } | ||
| 85 | 10 | CEXP auto dance(F&& cb) NE { | |
| 86 | 10 | std::optional ans{vecu{}}; | |
| 87 |
2/2✓ Branch 3 taken 2 times.
✓ Branch 4 taken 8 times.
|
10 | if (!dance_(ans.value(), std::forward<F>(cb))) ans = std::nullopt; |
| 88 | 10 | return ans; | |
| 89 | } | ||
| 90 | |||
| 91 | #undef l_ | ||
| 92 | #undef r_ | ||
| 93 | #undef u_ | ||
| 94 | #undef d_ | ||
| 95 | #undef row_ | ||
| 96 | #undef col_ | ||
| 97 | #undef dlxfor_ | ||
| 98 | }; | ||
| 99 | |||
| 100 | } // namespace tifa_libs | ||
| 101 |