src/math/ds/youngt/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 Youngt { | ||
| 8 | vvecu d; | ||
| 9 | u32 n; | ||
| 10 | |||
| 11 | public: | ||
| 12 | CEXPE Youngt(spnu l) NE { | ||
| 13 | for (auto i : l) insert(i); | ||
| 14 | } | ||
| 15 | 22 | CEXP Youngt(itlu l = {}) NE { | |
| 16 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 22 times.
|
22 | for (auto i : l) insert(i); |
| 17 | 22 | } | |
| 18 | CEXP Youngt(itl<itlu> l) NE { | ||
| 19 | for (auto&& i : l) d.emplace_back(i); | ||
| 20 | } | ||
| 21 | |||
| 22 | // height() == len(longest non-decresing seq.) | ||
| 23 | ND CEXP u32 height() CNE { return (u32)d.size(); } | ||
| 24 | // width() == len(longest increasing seq.) | ||
| 25 | 22 | ND CEXP u32 width() CNE { return (u32)d[0].size(); } | |
| 26 | ND CEXP u32 CR size() CNE { return n; } | ||
| 27 | CEXP vvecu& data() NE { return d; } | ||
| 28 | ND CEXP vvecu CR data() CNE { return d; } | ||
| 29 | CEXP u32& operator()(u32 h, u32 w) NE { return d[h][w]; } | ||
| 30 | CEXP u32 CR operator()(u32 h, u32 w) CNE { return d[h][w]; } | ||
| 31 | ND CEXP u32 hook(u32 h, u32 w) CNE { | ||
| 32 | assert(h < height() && w < d[h].size()); | ||
| 33 | return u32(d[h].size() - w + h); | ||
| 34 | } | ||
| 35 | 44286 | CEXP void insert(u32 val) NE { | |
| 36 | 44286 | ++n; | |
| 37 |
2/2✓ Branch 5 taken 6236901 times.
✓ Branch 6 taken 2551 times.
|
6239452 | for (auto& i : d) { |
| 38 | 6236901 | auto it = lower_bound(i, val); | |
| 39 |
2/2✓ Branch 2 taken 41735 times.
✓ Branch 3 taken 6195166 times.
|
6236901 | if (it == end(i)) return i.push_back(val); |
| 40 | 6195166 | swap(val, *it); | |
| 41 | } | ||
| 42 | 7653 | d.push_back({val}); | |
| 43 | } | ||
| 44 | friend std::ostream& operator<<(std::ostream& os, Youngt CR yt) NE { | ||
| 45 | for (u32 i = 0; i < yt.height() - 1; ++i) | ||
| 46 | flt_ (u32, j, 0, (u32)yt.d[i].size()) os << yt.d[i][j] << " \n"[j == yt.d[i].size() - 1]; | ||
| 47 | os << yt.d.back()[0]; | ||
| 48 | for (u32 j = 1; j < yt.d.back().size(); ++j) os << ' ' << yt.d.back()[j]; | ||
| 49 | return os; | ||
| 50 | } | ||
| 51 | }; | ||
| 52 | |||
| 53 | } // namespace tifa_libs | ||
| 54 |