smawk.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <vector> | ||
| 4 | #include <cassert> | ||
| 5 | #include <optional> | ||
| 6 | #include <concepts> | ||
| 7 | |||
| 8 | namespace smawk { | ||
| 9 | |||
| 10 | 435 | template <typename T> struct value_t { | |
| 11 | T v; | ||
| 12 | int col; | ||
| 13 | }; | ||
| 14 | |||
| 15 | // Get(int row, int col) -> T | ||
| 16 | // Select(int row, const value_t<T>& opt_0, const value_t<T>& opt_1) returns 0 or 1 for which is better | ||
| 17 | template <typename T, typename Get, typename Select> concept totally_monotone_matrix_oracle = | ||
| 18 | std::default_initializable<T> && std::movable<T> | ||
| 19 | && std::invocable<Get, int, int> && std::convertible_to<std::invoke_result_t<Get, int, int>, T> | ||
| 20 | && std::predicate<Select, int, const value_t<T>&, const value_t<T>&>; | ||
| 21 | |||
| 22 | |||
| 23 | template <typename Get, typename Select, typename T = std::invoke_result_t<Get, int, int>> | ||
| 24 | requires totally_monotone_matrix_oracle<T, Get, Select> | ||
| 25 | class LARSCH { | ||
| 26 | public: | ||
| 27 | int N; | ||
| 28 | Get get; | ||
| 29 | Select select; | ||
| 30 | int L; | ||
| 31 | int num_rows; | ||
| 32 | |||
| 33 | std::vector<std::vector<value_t<T>>> stk; | ||
| 34 | std::vector<std::pair<value_t<T>, int>> bests; | ||
| 35 | ✗ | LARSCH() {} | |
| 36 | 14 | LARSCH(int N_, Get&& get_, Select&& select_) : N(N_), get(std::forward<Get>(get_)), select(std::forward<Select>(select_)) { | |
| 37 |
3/4✓ Branch 24 → 25 taken 12 times.
✓ Branch 24 → 30 taken 2 times.
✗ Branch 27 → 28 not taken.
✓ Branch 27 → 29 taken 12 times.
|
14 | L = N ? 31 - __builtin_clz(N) : 0; |
| 38 |
1/1✓ Branch 39 → 40 taken 14 times.
|
14 | stk.resize(L); |
| 39 |
1/1✓ Branch 46 → 57 taken 14 times.
|
14 | bests.resize(L); |
| 40 | // N >> L == 1, unless N == 0 | ||
| 41 |
2/2✓ Branch 60 → 47 taken 20 times.
✓ Branch 60 → 61 taken 14 times.
|
34 | for (int i = 0; i < L; i++) { |
| 42 |
2/3✗ Branch 54 → 55 not taken.
✓ Branch 54 → 56 taken 20 times.
✓ Branch 56 → 57 taken 20 times.
|
20 | stk[i].reserve(N >> (i+1)); |
| 43 | } | ||
| 44 | 14 | num_rows = 0; | |
| 45 | 14 | } | |
| 46 | |||
| 47 | 64 | value_t<T> push_and_query_next() { | |
| 48 | 64 | assert(num_rows < N); | |
| 49 | 64 | int inp_row = num_rows++; | |
| 50 | |||
| 51 | 64 | int l = 0; | |
| 52 | 64 | value_t<T> nbest; | |
| 53 | 44 | while (true) { | |
| 54 |
1/2✗ Branch 20 → 21 not taken.
✓ Branch 20 → 22 taken 108 times.
|
108 | int r = inp_row >> l; |
| 55 |
2/2✓ Branch 23 → 24 taken 44 times.
✓ Branch 23 → 34 taken 64 times.
|
108 | int col = l == 0 ? inp_row : stk[l-1][r].col; |
| 56 |
2/2✓ Branch 37 → 38 taken 12 times.
✓ Branch 37 → 73 taken 96 times.
|
108 | if (l == L) { |
| 57 | // special case: just return the unique element | ||
| 58 | 12 | assert(r == 0); | |
| 59 | 12 | assert(inp_row == 0); | |
| 60 | 12 | int row = ((r+1) << l) - 1; | |
| 61 |
3/3✓ Branch 42 → 43 taken 2 times.
✓ Branch 42 → 50 taken 10 times.
✓ Branch 46 → 47 taken 2 times.
|
12 | if (l == 0) nbest = {get(row, col), col}; |
| 62 | 10 | else nbest = {std::move(stk[l-1][r].v), stk[l-1][r].col}; | |
| 63 | 12 | l--; | |
| 64 | 64 | break; | |
| 65 | } | ||
| 66 | 96 | assert(l < L); | |
| 67 | |||
| 68 |
2/2✓ Branch 78 → 79 taken 44 times.
✓ Branch 78 → 157 taken 52 times.
|
96 | if (r & 1) { |
| 69 | 44 | int row = ((r+1) << l) - 1; | |
| 70 | 44 | value_t<T> prv_col_top; | |
| 71 |
3/3✓ Branch 83 → 84 taken 28 times.
✓ Branch 83 → 91 taken 16 times.
✓ Branch 87 → 88 taken 28 times.
|
44 | if (l == 0) prv_col_top = {get(row, col), col}; |
| 72 | 16 | else prv_col_top = {std::move(stk[l-1][r].v), stk[l-1][r].col}; | |
| 73 | |||
| 74 | 44 | assert(bests[l].second <= r); | |
| 75 | |||
| 76 | // just check this guy at this row, and then push it into the next layer, but don't query yet | ||
| 77 |
5/5✓ Branch 129 → 130 taken 41 times.
✓ Branch 129 → 141 taken 3 times.
✓ Branch 139 → 140 taken 41 times.
✓ Branch 140 → 141 taken 13 times.
✓ Branch 140 → 156 taken 28 times.
|
44 | if (bests[l].second == r || select(row, bests[l].first, prv_col_top)) { |
| 78 | // prv_col_top is better here | ||
| 79 | 16 | bests[l].first = std::move(prv_col_top); | |
| 80 | 16 | bests[l].second = r; | |
| 81 | } | ||
| 82 | } | ||
| 83 |
2/2✓ Branch 164 → 165 taken 37 times.
✓ Branch 164 → 193 taken 59 times.
|
96 | if (bests[l].second == r) { |
| 84 | // We've committed to the new column being the best, so let's prune the stack and propagate to ensure consistency. | ||
| 85 | 37 | assert(int(stk[l].size()) >= (r+1)/2); | |
| 86 |
1/1✓ Branch 180 → 181 taken 37 times.
|
37 | stk[l].resize((r+1)/2); |
| 87 | // We can just set .second only, since the only time it's read is the r&1 case, which will override bests[l].first | ||
| 88 |
2/2✓ Branch 184 → 185 taken 18 times.
✓ Branch 184 → 193 taken 19 times.
|
37 | if (l+1 < L) bests[l+1].second = (r+1)/2; |
| 89 | } | ||
| 90 | 96 | std::optional<value_t<T>> to_push; | |
| 91 |
2/2✓ Branch 238 → 195 taken 30 times.
✓ Branch 238 → 239 taken 84 times.
|
114 | while (int(stk[l].size()) > (r+1)/2) { |
| 92 |
1/2✗ Branch 203 → 204 not taken.
✓ Branch 203 → 205 taken 30 times.
|
30 | int row = (int(stk[l].size()) << (l+1)) - 1; |
| 93 |
1/1✓ Branch 208 → 209 taken 30 times.
|
30 | value_t<T> nv{get(row, col), col}; |
| 94 |
3/3✓ Branch 219 → 220 taken 30 times.
✓ Branch 220 → 221 taken 18 times.
✓ Branch 220 → 229 taken 12 times.
|
30 | if (select(row, stk[l].back(), nv)) { |
| 95 | 18 | stk[l].pop_back(); | |
| 96 | 18 | to_push = std::move(nv); | |
| 97 | } else { | ||
| 98 | break; | ||
| 99 | } | ||
| 100 | } | ||
| 101 |
2/2✓ Branch 245 → 246 taken 17 times.
✓ Branch 245 → 254 taken 79 times.
|
96 | if (to_push) { |
| 102 |
1/1✓ Branch 253 → 279 taken 17 times.
|
17 | stk[l].emplace_back(std::move(*to_push)); |
| 103 | } else { | ||
| 104 |
1/2✗ Branch 262 → 263 not taken.
✓ Branch 262 → 264 taken 79 times.
|
79 | int row = (int(stk[l].size()+1) << (l+1)) - 1; |
| 105 |
4/4✓ Branch 266 → 267 taken 45 times.
✓ Branch 266 → 279 taken 34 times.
✓ Branch 275 → 276 taken 45 times.
✓ Branch 277 → 278 taken 45 times.
|
79 | if (row < N) stk[l].emplace_back(get(row, col), col); |
| 106 | } | ||
| 107 |
2/2✓ Branch 279 → 280 taken 44 times.
✓ Branch 279 → 288 taken 52 times.
|
96 | if (r & 1) { |
| 108 | // go return | ||
| 109 | 44 | nbest = std::move(bests[l].first); | |
| 110 | 44 | l--; | |
| 111 | 44 | break; | |
| 112 |
2/2✓ Branch 290 → 291 taken 8 times.
✓ Branch 290 → 295 taken 44 times.
|
52 | } else if (((r+2) << l) - 1 >= N) { |
| 113 | // go return | ||
| 114 | 8 | nbest.col = col; | |
| 115 | 8 | break; | |
| 116 | } else { | ||
| 117 | 44 | l++; | |
| 118 | 44 | continue; | |
| 119 | } | ||
| 120 | assert(false); | ||
| 121 | } | ||
| 122 |
2/2✓ Branch 394 → 300 taken 52 times.
✓ Branch 394 → 395 taken 64 times.
|
116 | for (; l >= 0; l--) { |
| 123 | 52 | int r = inp_row >> l; | |
| 124 | 52 | assert(!(r & 1)); | |
| 125 |
1/2✗ Branch 302 → 303 not taken.
✓ Branch 302 → 304 taken 52 times.
|
52 | int row = ((r+1) << l) - 1; |
| 126 | 52 | bests[l].first = std::move(nbest); | |
| 127 | 52 | bool did_set = false; | |
| 128 | 43 | while (true) { | |
| 129 | 95 | int idx = bests[l].second; | |
| 130 | 95 | assert(idx <= r); | |
| 131 |
2/2✓ Branch 320 → 321 taken 25 times.
✓ Branch 320 → 331 taken 70 times.
|
95 | int col = (l == 0 ? idx : stk[l-1][idx].col); |
| 132 | 95 | assert(col <= bests[l].first.col); | |
| 133 | 95 | value_t<T> cnd; | |
| 134 |
2/2✓ Branch 344 → 345 taken 15 times.
✓ Branch 344 → 358 taken 80 times.
|
95 | if (l > 0 && idx == r) cnd = {std::move(stk[l-1][r].v), col}; |
| 135 |
1/1✓ Branch 361 → 362 taken 80 times.
|
80 | else cnd = {get(row, col), col}; |
| 136 |
5/5✓ Branch 365 → 366 taken 43 times.
✓ Branch 365 → 371 taken 52 times.
✓ Branch 369 → 370 taken 43 times.
✓ Branch 370 → 371 taken 14 times.
✓ Branch 370 → 372 taken 29 times.
|
95 | if (!did_set || select(row, nbest, cnd)) { |
| 137 | 66 | did_set = true; | |
| 138 | 66 | nbest = std::move(cnd); | |
| 139 | } | ||
| 140 |
2/2✓ Branch 379 → 380 taken 43 times.
✓ Branch 379 → 392 taken 52 times.
|
95 | if (col == bests[l].first.col) break; |
| 141 | 43 | bests[l].second++; | |
| 142 | } | ||
| 143 | } | ||
| 144 | 64 | assert(l == -1); | |
| 145 | 64 | return nbest; | |
| 146 | } | ||
| 147 | }; | ||
| 148 | |||
| 149 | template <typename Get, typename Select, typename T = std::invoke_result_t<Get&&, int, int>> | ||
| 150 | requires totally_monotone_matrix_oracle<T, Get&&, Select&&> | ||
| 151 | 84 | std::vector<value_t<T>> smawk(int N, int M, Get&& get, Select&& select) { | |
| 152 | // TODO: If M >> N, then we should do an extra layer of column filter on the outside. The cutoff should be M > 2N or so. | ||
| 153 |
1/1✓ Branch 3 → 4 taken 43 times.
|
84 | std::vector<value_t<T>> res(N); |
| 154 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 11 → 6 taken 192 times.
✓ Branch 11 → 12 taken 43 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 5 → 4 taken 20464989 times.
✓ Branch 5 → 6 taken 41 times.
|
20465265 | for (int i = 0; i < N; i++) res[i].col = -1; |
| 155 |
2/2std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 14 → 15 taken 43 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 6 → 7 taken 41 times.
|
84 | std::vector<int> stks(N); |
| 156 |
4/6std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 16 → 17 taken 36 times.
✓ Branch 16 → 20 taken 7 times.
✗ Branch 17 → 18 not taken.
✓ Branch 17 → 19 taken 36 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 7 → 8 taken 41 times.
✗ Branch 7 → 9 not taken.
|
84 | int L = N ? 31 - __builtin_clz(N) : 0; |
| 157 |
2/2std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 22 → 23 taken 43 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 9 → 10 taken 41 times.
|
84 | std::vector<int> stk_ends(L+1); |
| 158 | 84 | stk_ends[0] = 0; | |
| 159 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 66 → 29 taken 60 times.
✓ Branch 66 → 67 taken 43 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 22 → 11 taken 552 times.
✓ Branch 22 → 23 taken 41 times.
|
696 | for (int l = 0; l < L; l++) { |
| 160 | 612 | int sz = 0; | |
| 161 | 43338468 | auto check_col = [&](int col, int min_sz) -> void { | |
| 162 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 50 → 3 taken 191 times.
✓ Branch 50 → 51 taken 120 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 5 → 3 taken 26067637 times.
✓ Branch 5 → 6 taken 5983450 times.
|
32051398 | while (sz > min_sz) { |
| 163 |
1/2✗ Branch 12 → 13 not taken.
✓ Branch 12 → 14 taken 191 times.
|
26067828 | int row = (sz << (l+1)) - 1; |
| 164 |
1/1✓ Branch 18 → 19 taken 191 times.
|
26067828 | value_t<T> cnd(get(row, col), col); |
| 165 |
5/5std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 29 → 30 taken 191 times.
✓ Branch 30 → 31 taken 87 times.
✓ Branch 30 → 45 taken 104 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 3 → 4 taken 10382271 times.
✓ Branch 3 → 6 taken 15685366 times.
|
26067828 | if (select(row, res[row], cnd)) { |
| 166 | // we prefer cnd, save this | ||
| 167 | 10382358 | res[row] = std::move(cnd); | |
| 168 | 10382358 | sz--; | |
| 169 | } else { | ||
| 170 | break; | ||
| 171 | } | ||
| 172 | } | ||
| 173 | |||
| 174 |
5/6std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✗ Branch 65 → 66 not taken.
✓ Branch 65 → 67 taken 224 times.
✓ Branch 67 → 68 taken 181 times.
✓ Branch 67 → 158 taken 43 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 6 → 7 taken 21668651 times.
✓ Branch 6 → 10 taken 165 times.
|
21669040 | if (sz < (N >> (l+1))) { |
| 175 | 21668832 | int row = ((sz+1) << (l+1)) - 1; | |
| 176 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 85 → 86 taken 79 times.
✓ Branch 85 → 116 taken 102 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 7 → 8 taken 8827963 times.
✓ Branch 7 → 9 taken 12840688 times.
|
21668832 | if (res[row].col == col) { |
| 177 | 8828042 | stks[stk_ends[l] + sz] = col; | |
| 178 | 8828042 | sz++; | |
| 179 | } else { | ||
| 180 |
1/1✓ Branch 120 → 121 taken 102 times.
|
12840790 | value_t<T> cnd(get(row, col), col); |
| 181 | // This is a legal optimization, but I'm not sure it buys anything real, so just stub it out with true || | ||
| 182 | if (true || res[row].col == -1 || res[row].col < col || !select(row, cnd, res[row])) { | ||
| 183 | 12840790 | res[row] = std::move(cnd); | |
| 184 | 12840790 | stks[stk_ends[l] + sz] = col; | |
| 185 | 12840790 | sz++; | |
| 186 | } | ||
| 187 | } | ||
| 188 | } | ||
| 189 | }; | ||
| 190 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 33 → 36 taken 30 times.
✓ Branch 33 → 37 taken 30 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 11 → 14 taken 40 times.
✓ Branch 11 → 15 taken 512 times.
|
612 | if (l == 0) { |
| 191 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 36 → 34 taken 160 times.
✓ Branch 36 → 53 taken 30 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 14 → 12 taken 10382476 times.
✓ Branch 14 → 19 taken 40 times.
|
10382706 | for (int col = 0; col < M; col++) { |
| 192 |
1/1✓ Branch 34 → 35 taken 160 times.
|
10382636 | check_col(col, 0); |
| 193 | } | ||
| 194 | } else { | ||
| 195 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 52 → 41 taken 64 times.
✓ Branch 52 → 53 taken 30 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 18 → 16 taken 11286340 times.
✓ Branch 18 → 19 taken 512 times.
|
11286946 | for (int z = stk_ends[l-1]; z < stk_ends[l]; z++) { |
| 196 |
1/1✓ Branch 47 → 48 taken 64 times.
|
11286404 | check_col(stks[z], (z - stk_ends[l-1]) / 2); |
| 197 | } | ||
| 198 | } | ||
| 199 | 612 | assert(sz <= (N >> (l+1))); | |
| 200 | 612 | stk_ends[l+1] = stk_ends[l] + sz; | |
| 201 | } | ||
| 202 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 125 → 68 taken 103 times.
✓ Branch 125 → 126 taken 43 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 44 → 24 taken 593 times.
✓ Branch 44 → 45 taken 41 times.
|
780 | for (int l = L; l >= 0; l--) { |
| 203 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 68 → 69 taken 60 times.
✓ Branch 68 → 120 taken 43 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 24 → 25 taken 552 times.
✓ Branch 24 → 41 taken 41 times.
|
696 | int z = l == 0 ? 0 : stk_ends[l-1]; |
| 204 |
5/6std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✗ Branch 121 → 122 not taken.
✓ Branch 121 → 123 taken 295 times.
✓ Branch 123 → 73 taken 192 times.
✓ Branch 123 → 124 taken 103 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 42 → 26 taken 20464989 times.
✓ Branch 42 → 43 taken 593 times.
|
20465877 | for (int r = 0; r < (N >> l); r += 2) { |
| 205 | 20465181 | int row = ((r+1) << l) - 1; | |
| 206 | // TODO: You could not reset this? Not sure if it buys anything real. | ||
| 207 | 20465181 | res[row].col = -1; | |
| 208 |
8/8std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 107 → 108 taken 147 times.
✓ Branch 107 → 112 taken 283 times.
✓ Branch 112 → 78 taken 370 times.
✓ Branch 112 → 113 taken 60 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 35 → 36 taken 21518582 times.
✓ Branch 35 → 37 taken 20614968 times.
✓ Branch 37 → 27 taken 42133143 times.
✓ Branch 37 → 38 taken 407 times.
|
42133980 | for (; z < (l == 0 ? M : stk_ends[l]); z++) { |
| 209 |
4/4std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 78 → 79 taken 111 times.
✓ Branch 78 → 83 taken 259 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 27 → 28 taken 21518200 times.
✓ Branch 27 → 29 taken 20614943 times.
|
42133513 | int col = l == 0 ? z : stks[z]; |
| 210 |
1/1✓ Branch 84 → 85 taken 370 times.
|
42133513 | value_t<T> cnd = {get(row, col), col}; |
| 211 |
9/9std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 89 → 90 taken 178 times.
✓ Branch 89 → 95 taken 192 times.
✓ Branch 93 → 94 taken 178 times.
✓ Branch 94 → 95 taken 41 times.
✓ Branch 94 → 98 taken 137 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 29 → 30 taken 21668154 times.
✓ Branch 29 → 31 taken 20464989 times.
✓ Branch 30 → 31 taken 2393738 times.
✓ Branch 30 → 32 taken 19274416 times.
|
42133513 | if (res[row].col == -1 || select(row, res[row], cnd)) { |
| 212 | 22858960 | res[row] = std::move(cnd); | |
| 213 | } | ||
| 214 |
8/8std::__debug::vector<smawk::value_t<move_only_t>, std::allocator<smawk::value_t<move_only_t> > > smawk::smawk<check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}, move_only_t>(int, int, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, int)#1}&&, check_smawk(int, int, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >)::{lambda(int, smawk::value_t<move_only_t> const&, smawk::value_t<move_only_t> const&)#1}&&):
✓ Branch 98 → 99 taken 262 times.
✓ Branch 98 → 104 taken 108 times.
✓ Branch 103 → 104 taken 130 times.
✓ Branch 103 → 106 taken 132 times.
std::vector<smawk::value_t<int>, std::allocator<smawk::value_t<int> > > smawk::smawk<main::{lambda(int, int)#1}, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}, int>(int, int, main::{lambda(int, int)#1}&&, main::{lambda(int, smawk::value_t<int>, smawk::value_t<int>)#1}&&):
✓ Branch 32 → 33 taken 42131659 times.
✓ Branch 32 → 34 taken 1484 times.
✓ Branch 33 → 34 taken 21667077 times.
✓ Branch 33 → 38 taken 20464582 times.
|
42133513 | if ((r+1) < (N >> l) && col == res[((r+2) << l) - 1].col) break; |
| 215 | } | ||
| 216 | 20465181 | assert(res[row].col != -1); | |
| 217 | } | ||
| 218 | } | ||
| 219 | 127 | return res; | |
| 220 | 127 | } | |
| 221 | |||
| 222 | // namespace smawk | ||
| 223 | } | ||
| 224 |