test/cpv_local/math/josephus.cpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	100.0%	42 / 0 / 42
Functions:	100.0%	3 / 0 / 3
Branches:	55.3%	63 / 0 / 114

    test/cpv_local/math/josephus.cpp
    
        Line
        Branch
        Exec
        Source
      
        // competitive-verifier: STANDALONE
      
        #include "../../../src/math/josephus/lib.hpp"
      
        #include "../base.hpp"
      
        using namespace tifa_libs;
      
        decltype(default_timer.passed()) cnt_ys, cnt_bf;
      
        12
        vecuu Josephus_bf(u64 n, u64 k, u64 m) {
      
          3/6✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.

        12
          assert(m && k && m <= n);
      
          1/2✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.

        12
          assert(m <= 10000);
      
          1/2✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.

        12
          vecuu ans(m);
      
        12
          std::list<u64> l;
      
          3/4✓ Branch 1 taken 7797784 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7797784 times.
✓ Branch 4 taken 12 times.

        7797796
          flt_ (u64, i, 0, n) l.push_back(i);
      
        12
          auto it = begin(l);
      
          2/2✓ Branch 0 taken 54030 times.
✓ Branch 1 taken 12 times.

        54042
          flt_ (u32, i, 0, (u32)m) {
      
          2/2✓ Branch 0 taken 20343684030 times.
✓ Branch 1 taken 54030 times.

        20343738060
            flt_ (u32, j, 1, (u32)k)
      
          2/2✓ Branch 3 taken 176351 times.
✓ Branch 4 taken 20343507679 times.

        20343684030
              if (++it == end(l)) it = begin(l);
      
        54030
            ans[i] = *it;
      
          2/2✓ Branch 4 taken 26 times.
✓ Branch 5 taken 54004 times.

        54030
            if ((it = l.erase(it)) == end(l)) it = begin(l);
      
          }
      
        24
          return ans;
      
        12
        }
      
        12
        void test(u64 n, u64 k) {
      
        12
          u64 m = std::min(10000_u64, n);
      
        12
          default_timer.tic(__LINE__);
      
          1/2✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.

        12
          auto wants = Josephus_bf(n, k, m);
      
        12
          default_timer.tac();
      
          1/2✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.

        12
          cnt_bf += default_timer.passed();
      
          2/2✓ Branch 0 taken 54030 times.
✓ Branch 1 taken 12 times.

        54042
          flt_ (u32, i, 1, (u32)m + 1) {
      
        54030
            default_timer.tic(__LINE__);
      
        54030
            u64 got = Josephus(n, k, i);
      
        54030
            default_timer.tac();
      
          1/2✓ Branch 2 taken 54030 times.
✗ Branch 3 not taken.

        54030
            cnt_ys += default_timer.passed();
      
          4/8✓ Branch 1 taken 54030 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 54030 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 54030 times.
✗ Branch 8 not taken.
✓ Branch 14 taken 54030 times.
✗ Branch 15 not taken.

        54030
            check(got, wants[i - 1], check_param(n), check_param(k), check_param(i));
      
          }
      
          2/4✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.

        12
          std::cerr << std::format("Josephus: {}, BF: {}\n", cnt_ys, cnt_bf);
      
        12
        }
      
        1
        int main() {
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(10, 1));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(10, 2));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(10, 3));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(1000, 1));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(1000, 2));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(1000, 3));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(1000, 42));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(1919810, 1));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(1919810, 2));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(1919810, 42));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(1919810, 114514));
      
          3/6✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.

        1
          timer_(test(114514, 1919810));
      
        1
        }

Line	Branch	Exec	Source
1			// competitive-verifier: STANDALONE
2
3			#include "../../../src/math/josephus/lib.hpp"
4			#include "../base.hpp"
5
6			using namespace tifa_libs;
7			decltype(default_timer.passed()) cnt_ys, cnt_bf;
8		12	vecuu Josephus_bf(u64 n, u64 k, u64 m) {
9	3/6 ✓ Branch 0 taken 12 times. ✗ Branch 1 not taken. ✓ Branch 2 taken 12 times. ✗ Branch 3 not taken. ✓ Branch 4 taken 12 times. ✗ Branch 5 not taken.	12	assert(m && k && m <= n);
10	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 12 times.	12	assert(m <= 10000);
11	1/2 ✓ Branch 1 taken 12 times. ✗ Branch 2 not taken.	12	vecuu ans(m);
12		12	std::list<u64> l;
13	3/4 ✓ Branch 1 taken 7797784 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 7797784 times. ✓ Branch 4 taken 12 times.	7797796	flt_ (u64, i, 0, n) l.push_back(i);
14		12	auto it = begin(l);
15	2/2 ✓ Branch 0 taken 54030 times. ✓ Branch 1 taken 12 times.	54042	flt_ (u32, i, 0, (u32)m) {
16	2/2 ✓ Branch 0 taken 20343684030 times. ✓ Branch 1 taken 54030 times.	20343738060	flt_ (u32, j, 1, (u32)k)
17	2/2 ✓ Branch 3 taken 176351 times. ✓ Branch 4 taken 20343507679 times.	20343684030	if (++it == end(l)) it = begin(l);
18		54030	ans[i] = *it;
19	2/2 ✓ Branch 4 taken 26 times. ✓ Branch 5 taken 54004 times.	54030	if ((it = l.erase(it)) == end(l)) it = begin(l);
20			}
21		24	return ans;
22		12	}
23
24		12	void test(u64 n, u64 k) {
25		12	u64 m = std::min(10000_u64, n);
26		12	default_timer.tic(__LINE__);
27	1/2 ✓ Branch 1 taken 12 times. ✗ Branch 2 not taken.	12	auto wants = Josephus_bf(n, k, m);
28		12	default_timer.tac();
29	1/2 ✓ Branch 2 taken 12 times. ✗ Branch 3 not taken.	12	cnt_bf += default_timer.passed();
30	2/2 ✓ Branch 0 taken 54030 times. ✓ Branch 1 taken 12 times.	54042	flt_ (u32, i, 1, (u32)m + 1) {
31		54030	default_timer.tic(__LINE__);
32		54030	u64 got = Josephus(n, k, i);
33		54030	default_timer.tac();
34	1/2 ✓ Branch 2 taken 54030 times. ✗ Branch 3 not taken.	54030	cnt_ys += default_timer.passed();
35	4/8 ✓ Branch 1 taken 54030 times. ✗ Branch 2 not taken. ✓ Branch 4 taken 54030 times. ✗ Branch 5 not taken. ✓ Branch 7 taken 54030 times. ✗ Branch 8 not taken. ✓ Branch 14 taken 54030 times. ✗ Branch 15 not taken.	54030	check(got, wants[i - 1], check_param(n), check_param(k), check_param(i));
36			}
37	2/4 ✓ Branch 1 taken 12 times. ✗ Branch 2 not taken. ✓ Branch 4 taken 12 times. ✗ Branch 5 not taken.	12	std::cerr << std::format("Josephus: {}, BF: {}\n", cnt_ys, cnt_bf);
38		12	}
39
40		1	int main() {
41	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(10, 1));
42	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(10, 2));
43	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(10, 3));
44	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(1000, 1));
45	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(1000, 2));
46	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(1000, 3));
47	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(1000, 42));
48	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(1919810, 1));
49	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(1919810, 2));
50	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(1919810, 42));
51	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(1919810, 114514));
52	3/6 ✓ Branch 4 taken 1 time. ✗ Branch 5 not taken. ✓ Branch 7 taken 1 time. ✗ Branch 8 not taken. ✓ Branch 10 taken 1 time. ✗ Branch 11 not taken.	1	timer_(test(114514, 1919810));
53		1	}
54