test/cpv/library-checker-number_theory/stern_brocot_tree.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/stern_brocot_tree | ||
| 2 | #include "../../../src/io/fastin/lib.hpp" | ||
| 3 | #include "../../../src/io/fastout/lib.hpp" | ||
| 4 | #include "../../../src/nt/sbt/lib.hpp" | ||
| 5 | |||
| 6 | using namespace tifa_libs; | ||
| 7 | using sbt_t = sbt<u64>; | ||
| 8 | |||
| 9 | 18 | int main() { | |
| 10 | int n; | ||
| 11 | 18 | fin_uint >> n; | |
| 12 |
2/2✓ Branch 0 taken 1300531 times.
✓ Branch 1 taken 18 times.
|
1300549 | while (n--) { |
| 13 | 1300531 | strn s; | |
| 14 | 1300531 | fin >> s; | |
| 15 | u64 k; | ||
| 16 | u64 a, b, c, d; | ||
| 17 |
5/6✓ Branch 1 taken 257204 times.
✓ Branch 2 taken 257204 times.
✓ Branch 3 taken 233699 times.
✓ Branch 4 taken 295222 times.
✓ Branch 5 taken 257202 times.
✗ Branch 6 not taken.
|
1300531 | switch (s.front()) { |
| 18 | 257204 | case 'E': { | |
| 19 | 257204 | fin_uint >> a >> b; | |
| 20 | 257204 | vec<std::pair<char, u64>> path; | |
| 21 |
3/4✓ Branch 1 taken 1311625 times.
✓ Branch 2 taken 1331143 times.
✓ Branch 4 taken 2642768 times.
✗ Branch 5 not taken.
|
2899972 | sbt_t::walk_to(a, b, [&path](bool dir, u64 step) { path.emplace_back(dir ? 'R' : 'L', step); }); |
| 22 | 257204 | fout << path.size(); | |
| 23 |
2/2✓ Branch 11 taken 2642768 times.
✓ Branch 12 taken 257204 times.
|
2899972 | for (auto [dir, step] : path) fout << ' ' << dir << ' ' << step; |
| 24 | 257204 | fout << '\n'; | |
| 25 | 257204 | } break; | |
| 26 | 257204 | case 'D': { | |
| 27 | 257204 | fin_uint >> k; | |
| 28 | 257204 | sbt_t s; | |
| 29 | char ch; | ||
| 30 |
2/2✓ Branch 0 taken 2642769 times.
✓ Branch 1 taken 257204 times.
|
2899973 | flt_ (u64, i, 0, k, _) { |
| 31 | 2642769 | fin >> ch >> _; | |
| 32 |
2/2✓ Branch 0 taken 1311626 times.
✓ Branch 1 taken 1331143 times.
|
2642769 | ch == 'R' ? s.movr(_) : s.movl(_); |
| 33 | } | ||
| 34 | 257204 | fout << s.x << ' ' << s.y << '\n'; | |
| 35 | 257204 | } break; | |
| 36 | 233699 | case 'L': { | |
| 37 | 233699 | fin_uint >> a >> b >> c >> d; | |
| 38 | 233699 | auto s = sbt_t::walk_to_lca(a, b, c, d); | |
| 39 | 233699 | fout << s.x << ' ' << s.y << '\n'; | |
| 40 | 233699 | } break; | |
| 41 | 295222 | case 'A': { | |
| 42 | 295222 | fin_uint >> d >> a >> b; | |
| 43 | 295222 | vec<std::pair<char, u64>> path; | |
| 44 |
3/4✓ Branch 1 taken 1862226 times.
✓ Branch 2 taken 1880293 times.
✓ Branch 4 taken 3742519 times.
✗ Branch 5 not taken.
|
4037741 | sbt_t::walk_to(a, b, [&path](bool dir, u64 step) { path.emplace_back(dir ? 'R' : 'L', step); }); |
| 45 |
2/2✓ Branch 4 taken 2953543 times.
✓ Branch 5 taken 170896 times.
|
3124439 | for (auto it = path.begin(); it != path.end(); ++it) { |
| 46 |
2/2✓ Branch 1 taken 2829217 times.
✓ Branch 2 taken 124326 times.
|
2953543 | if (it->second <= d) d -= it->second; |
| 47 | else { | ||
| 48 | 124326 | it->second = d, d = 0; | |
| 49 |
1/2✓ Branch 5 taken 124326 times.
✗ Branch 6 not taken.
|
124326 | path.erase(++it, path.end()); |
| 50 | 124326 | break; | |
| 51 | } | ||
| 52 | } | ||
| 53 |
2/2✓ Branch 0 taken 167689 times.
✓ Branch 1 taken 127533 times.
|
295222 | if (d) fout << "-1\n"; |
| 54 | else { | ||
| 55 | 127533 | sbt_t s; | |
| 56 |
2/2✓ Branch 7 taken 1001012 times.
✓ Branch 8 taken 127533 times.
|
1128545 | for (auto [dir, step] : path) |
| 57 |
2/2✓ Branch 0 taken 496916 times.
✓ Branch 1 taken 504096 times.
|
1001012 | if (dir == 'R') s.movr(step); |
| 58 | 504096 | else s.movl(step); | |
| 59 | 127533 | fout << s.x << ' ' << s.y << '\n'; | |
| 60 | } | ||
| 61 | 295222 | } break; | |
| 62 | 257202 | case 'R': { | |
| 63 | 257202 | fin_uint >> a >> b; | |
| 64 | 257202 | auto _ = sbt_t::walk_to(a, b); | |
| 65 | 257202 | fout << _.lx << ' ' << _.ly << ' ' << _.rx << ' ' << _.ry << '\n'; | |
| 66 | 257202 | } break; | |
| 67 | } | ||
| 68 | 1300531 | } | |
| 69 | 18 | return 0; | |
| 70 | } | ||
| 71 |