diff options
Diffstat (limited to 'test/util.h')
| -rw-r--r-- | test/util.h | 35 |
1 files changed, 33 insertions, 2 deletions
diff --git a/test/util.h b/test/util.h index 6f23b82..e123fc2 100644 --- a/test/util.h +++ b/test/util.h @@ -168,6 +168,30 @@ namespace Random { exit(1); } +namespace detail { + double benchmark() { + mt19937 rng(734820734); + vector<unsigned> a(10000000); + for (unsigned &x: a) x = rng(); + chrono::steady_clock::time_point start = chrono::steady_clock::now(); + vector<unsigned> dp(ssize(a)+1, numeric_limits<unsigned>::max()); + int res = 0; + for (unsigned x: a) { + auto it = ranges::upper_bound(dp, x); + res = max(res, (int)(it - begin(dp))); + *it = x; + } + chrono::steady_clock::time_point end = chrono::steady_clock::now(); + assert(res == 6301); + double t = + chrono::duration_cast<chrono::duration<double, milli>>(end - start) + .count(); + return 30/t; + } + + double speed = benchmark(); +} + struct timer { bool running = false; double time = 0; @@ -183,7 +207,7 @@ struct timer { auto end = chrono::steady_clock::now(); if (!running) cerr << "timer not running!" << FAIL; running = false; - time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count(); + time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count() * detail::speed; } void reset() { @@ -208,7 +232,7 @@ namespace c20 { return {{a[I]...}}; } } - + template<class T, std::size_t N> constexpr std::array<std::remove_cv_t<T>, N> to_array(T (&a)[N]) { return c20::detail::to_array_impl(a, std::make_index_sequence<N>{}); @@ -413,3 +437,10 @@ ld float_error(ld given, ld expected) { } return numeric_limits<ld>::infinity(); } + +#include <ext/pb_ds/assoc_container.hpp> +template<typename T> +using Tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, + __gnu_pbds::rb_tree_tag, + __gnu_pbds::tree_order_statistics_node_update>; + |