src/edh/garsia_wachs/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | //! v.front() == inf && v.back() == inf | ||
| 8 | template <class T, class F> | ||
| 9 | requires requires(F f, u32 m0, u32 m1, u32 r, u32 j, T a) { f(m0, m1, r, j, a); } | ||
| 10 | 10 | void garsia_wachs(vec<T>& v, F&& f) NE { | |
| 11 | 10 | u32 n = (u32)v.size() - 2, cnt = n + 1, k, j; | |
| 12 | 10 | vecu idx(n + 1); | |
| 13 | 10 | std::iota(begin(idx), end(idx), 0); | |
| 14 |
2/2✓ Branch 0 taken 124194 times.
✓ Branch 1 taken 10 times.
|
124204 | while (n-- > 1) { |
| 15 |
2/2✓ Branch 0 taken 827209183 times.
✓ Branch 1 taken 42779 times.
|
827251962 | for (k = 1; k <= n; ++k) |
| 16 |
2/2✓ Branch 2 taken 81415 times.
✓ Branch 3 taken 827127768 times.
|
827209183 | if (v[k - 1] < v[k + 1]) break; |
| 17 | 124194 | T a = v[k] + v[k - 1]; | |
| 18 |
1/2✓ Branch 0 taken 428249330 times.
✗ Branch 1 not taken.
|
428249330 | for (j = k - 1; ~j; --j) |
| 19 |
2/2✓ Branch 3 taken 124194 times.
✓ Branch 4 taken 428125136 times.
|
428249330 | if (v[j] > v[k] + v[k - 1]) break; |
| 20 | 124194 | v.erase(begin(v) + k - 1), v.erase(begin(v) + k - 1), v.insert(begin(v) + j + 1, a); | |
| 21 | 124194 | f(idx[k - 1], idx[k], ++cnt, j + 1, a); | |
| 22 | 124194 | idx.erase(begin(idx) + k - 1), idx.erase(begin(idx) + k - 1); | |
| 23 | 124194 | idx.insert(begin(idx) + j + 1, cnt); | |
| 24 | } | ||
| 25 | 10 | } | |
| 26 | |||
| 27 | } // namespace tifa_libs | ||
| 28 |