diff options
Diffstat (limited to 'test')
117 files changed, 713 insertions, 877 deletions
diff --git a/test/GNUmakefile b/test/GNUmakefile new file mode 100644 index 0000000..cc1b4f5 --- /dev/null +++ b/test/GNUmakefile @@ -0,0 +1,41 @@ + +TESTS = $(basename $(shell find . -path ./awk -prune -o -type f -name '*.cpp' -print)) +AWK = $(basename $(shell find . -type f -name '*.awk')) +CXX = g++ -std=gnu++20 -I awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror +SAN = -fsanitize=address,undefined -DSANITIZE +TIMEOUT = 300 + +test: $(TESTS:=.ok) $(TESTS:=.san.ok) + +missing: + @find ../content -name '*.cpp' | sed 's|^../content/||' \ + | while read -r f ; do [ -e "$$f" ] || echo "$$f" ; done \ + | sort > missing.tmp + @sort missing.ignore | comm -3 missing.tmp - + @rm missing.tmp + +clean: + rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.san.ok) $(TESTS:=.d) + rm -rf awk/ + +%.ok: %.test + timeout --foreground --verbose $(TIMEOUT) prlimit -s$$((1<<32)) ./$< + @touch $@ + +%.test: %.cpp + $(CXX) -o $@ $< + +%.san.test: %.cpp + $(CXX) $(SAN) -o $@ $< + +awk/%: %.awk ../content/% + @mkdir -p $(dir $@) + awk -f $*.awk < ../content/$* > $@ + +%.d: %.cpp $(addprefix awk/,$(AWK)) + $(CXX) -M -MP -MT '$*.test $*.san.test $*.d' -MF $@ $< + +.PHONY: test clean +.SECONDARY: $(TESTS:=.test) $(addprefix awk/,$(AWK)) + +include $(TESTS:=.d) diff --git a/test/datastructures/LCT.cpp b/test/datastructures/LCT.cpp index a1e37eb..e120b6e 100644 --- a/test/datastructures/LCT.cpp +++ b/test/datastructures/LCT.cpp @@ -73,13 +73,13 @@ struct Naive { } }; dfs_comp(dfs_comp, x); - return seen[Random::integer<int>(sz(seen))]; + return seen[Random::integer<int>(ssize(seen))]; } int randomAdj(int x) { if (adj[x].empty()) return -1; - vector<int> seen(all(adj[x])); - return seen[Random::integer<int>(sz(seen))]; + vector<int> seen(begin(adj[x]), end(adj[x])); + return seen[Random::integer<int>(ssize(seen))]; } }; @@ -179,7 +179,7 @@ void performance_test() { int a = Random::integer<int>(0, N); int b = Random::integer<int>(0, N); ll w = Random::integer<ll>(-1000, 1000); - + t.start(); if (!lct.connected(&lct.nodes[a], &lct.nodes[b])) { lct.link(&lct.nodes[a], &lct.nodes[b]); diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp index 335dbae..cc57d73 100644 --- a/test/datastructures/dynamicConvexHull.cpp +++ b/test/datastructures/dynamicConvexHull.cpp @@ -29,7 +29,7 @@ void stress_test(ll range) { ll got = hd.query(x); ll expected = naive[0](x); - for (auto l : naive) expected = max(expected, l(x)); + for (auto l : naive) expected = min(expected, l(x)); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries++; @@ -49,7 +49,7 @@ void performance_test() { ll m = Random::integer<ll>(-1'000'000'000, 1'000'000'000); ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000); ll x = Random::integer<ll>(-1'000'000'000, 1'000'000'000); - + t.start(); hd.add(m, c); hash += hd.query(x); diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp index d50ca60..f692e92 100644 --- a/test/datastructures/dynamicConvexHull.lichao.cpp +++ b/test/datastructures/dynamicConvexHull.lichao.cpp @@ -8,7 +8,7 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); xs = Random::distinct(n, -range, range); - sort(all(xs)); + ranges::sort(xs); HullDynamic hd; Lichao lichao; @@ -16,11 +16,11 @@ void stress_test(ll range) { ll m = Random::integer<ll>(-range, range); ll c = Random::integer<ll>(-range, range); hd.add(m, c); - lichao.insert({-m, -c}); + lichao.insert({m, c}); for (ll x : xs) { ll gotA = hd.query(x); - ll gotB = -lichao.query(x); + ll gotB = lichao.query(x); if (gotA != gotB) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL; queries++; diff --git a/test/datastructures/fenwickTree.cpp b/test/datastructures/fenwickTree.cpp index 62e6392..f3c0274 100644 --- a/test/datastructures/fenwickTree.cpp +++ b/test/datastructures/fenwickTree.cpp @@ -23,7 +23,7 @@ void stress_test() { int i = Random::integer<int>(0, n); ll got = prefix_sum(i); ll expected = 0; - for (int j = 0; j <= i; j++) expected += naive[j]; + for (int j = 0; j < i; j++) expected += naive[j]; if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } @@ -42,7 +42,7 @@ void performance_test() { int i = Random::integer<int>(0, N); int j = Random::integer<int>(0, N); ll x = Random::integer<ll>(-1000, 1000); - + t.start(); update(i, x); hash ^= prefix_sum(j); diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp index 16caa1d..180bd24 100644 --- a/test/datastructures/fenwickTree2.cpp +++ b/test/datastructures/fenwickTree2.cpp @@ -23,7 +23,7 @@ void stress_test() { int i = Random::integer<int>(0, n); ll got = prefix_sum(i); ll expected = 0; - for (int j = 0; j <= i; j++) expected += naive[j]; + for (int j = 0; j < i; j++) expected += naive[j]; if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } @@ -44,7 +44,7 @@ void performance_test() { int j = Random::integer<int>(0, N); int k = Random::integer<int>(0, N); ll x = Random::integer<ll>(-1000, 1000); - + t.start(); update(i, j, x); hash ^= prefix_sum(k); diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp index 22b75ba..2e7431b 100644 --- a/test/datastructures/lazyPropagation.cpp +++ b/test/datastructures/lazyPropagation.cpp @@ -34,6 +34,39 @@ void stress_test() { cerr << "tested random queries: " << queries << endl; } +void stress_test_binary_search() { + ll queries = 0; + for (int tries = 0; tries < 100; tries++) { + int n = Random::integer<int>(10, 100); + vector<ll> naive = Random::integers<ll>(n, 0, 1000); + SegTree tree(naive); + for (int operations = 0; operations < 1000; operations++) { + { + int l = Random::integer<int>(0, n + 1); + int r = Random::integer<int>(0, n + 1); + //if (l > r) swap(l, r); + ll x = Random::integer<ll>(0, 1000); + tree.update(l, r, x); + for (int j = l; j < r; j++) naive[j] = x; + } + { + queries++; + int l = Random::integer<int>(0, n + 1); + int r = Random::integer<int>(0, n + 1); + ll x = Random::integer<ll>(0, 10000); + //if (l > r) swap(l, r); + int got = tree.binary_search(l, r, [x](ll v) { return v >= x; }); + ll sum; + int j; + for (j = l, sum = 0; j < r && sum < x; j++) sum += naive[j]; + int expected = sum >= x ? j : -1; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + } + cerr << "tested random binary searches: " << queries << endl; +} + void performance_test() { timer t; t.start(); @@ -45,7 +78,7 @@ void performance_test() { auto [l1, r1] = Random::pair<int>(0, N + 1); auto [l2, r2] = Random::pair<int>(0, N + 1); ll x1 = Random::integer<ll>(-1000, 1000); - + t.start(); tree.update(l1, r1, x1); hash ^= tree.query(l2, r2); @@ -55,7 +88,33 @@ void performance_test() { cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } +void performance_test_binary_search() { + timer t; + t.start(); + vector<ll> tmp(N); + SegTree tree(tmp); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + auto [l1, r1] = Random::pair<int>(0, N + 1); + auto [l2, r2] = Random::pair<int>(0, N + 1); + ll x1 = Random::integer<ll>(0, 1000); + ll x2 = Random::integer<ll>(0, 1000 * N); + + t.start(); + tree.update(l1, r1, x1); + hash ^= tree.binary_search(l2, r2, [x2](ll v) { return v >= x2; }); + t.stop(); + } + if (t.time > 2000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + int main() { stress_test(); - if (!sanitize) performance_test(); + stress_test_binary_search(); + if (!sanitize) { + performance_test(); + performance_test_binary_search(); + } } diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp index 9cf770f..30d5b58 100644 --- a/test/datastructures/lichao.cpp +++ b/test/datastructures/lichao.cpp @@ -7,7 +7,7 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); xs = Random::distinct<ll>(n, -range, range); - sort(all(xs)); + ranges::sort(xs); vector<ll> naive(n, INF); Lichao tree; @@ -42,7 +42,7 @@ constexpr int N = 200'000; void performance_test() { timer t; xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); - sort(all(xs)); + ranges::sort(xs); t.start(); Lichao tree; diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 9490d7e..1c147e3 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -1,7 +1,5 @@ #include "../util.h" -struct MCH { - #include <datastructures/monotonicConvexHull.cpp> -}; +#include <datastructures/monotonicConvexHull.cpp> struct Line { ll m, c; @@ -14,12 +12,12 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); auto ms = Random::integers<ll>(n, -range, range); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto cs = ms; for (int l = 0, r = 0; l < n;) { while (r < n && ms[l] == ms[r]) r++; auto tmp = Random::distinct<ll>(r - l, -range, range); - sort(all(tmp), greater<>{}); + ranges::sort(tmp | views::reverse); for (int c : tmp) { cs[l] = c; l++; @@ -27,12 +25,12 @@ void stress_test(ll range) { } auto xs = Random::integers<ll>(n*100, -range*n, range*n); - sort(all(xs)); + ranges::sort(xs); int i = 0; vector<Line> naive; - MCH mch; + Envelope mch; for (int k = 0; k < n; k++) { ll m = ms[k]; ll c = cs[k]; @@ -60,12 +58,12 @@ void stress_test_independent(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); auto ms = Random::integers<ll>(n, -range, range); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto cs = ms; for (int l = 0, r = 0; l < n;) { while (r < n && ms[l] == ms[r]) r++; auto tmp = Random::distinct<ll>(r - l, -range, range); - sort(all(tmp), greater<>{}); + ranges::sort(tmp | views::reverse); for (int c : tmp) { cs[l] = c; l++; @@ -74,7 +72,7 @@ void stress_test_independent(ll range) { vector<Line> naive; - MCH mch; + Envelope mch; for (int i = 0; i < n; i++) { ll m = ms[i]; ll c = cs[i]; @@ -83,7 +81,7 @@ void stress_test_independent(ll range) { naive.emplace_back(m, c); auto xs = Random::integers<ll>(100, -range, range); - sort(all(xs)); + ranges::sort(xs); auto tmp = mch; for (auto x : xs) { @@ -103,17 +101,17 @@ constexpr int N = 1'000'000; void performance_test() { timer t; auto ms = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); - sort(all(xs)); - MCH mch; + ranges::sort(xs); + Envelope mch; hash_t hash = 0; for (int operations = 0; operations < N; operations++) { ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000); ll m = ms[operations]; ll x = xs[operations]; - + t.start(); mch.add(m, c); hash += mch.query(x); diff --git a/test/datastructures/pbds.cpp b/test/datastructures/pbds.cpp deleted file mode 100644 index 9080332..0000000 --- a/test/datastructures/pbds.cpp +++ /dev/null @@ -1,11 +0,0 @@ -#include "../util.h" -#include <datastructures/pbds.cpp> - -int main() { - Tree<int> t1, t2; - swap(t1, t2); - hashSet<int> s1, s2; - swap(s1, s2); - hashMap<int, int> m1, m2; - swap(m1, m2); -}
\ No newline at end of file diff --git a/test/datastructures/persistentArray.cpp b/test/datastructures/persistentArray.cpp index 6712089..ef8e52b 100644 --- a/test/datastructures/persistentArray.cpp +++ b/test/datastructures/persistentArray.cpp @@ -24,19 +24,19 @@ void stress_test() { cur[j] = x; expected.emplace_back(t, cur); } else if (op <= 16) { - if (sz(expected) < 1) continue; - int j = Random::integer<int>(0, sz(expected)); + if (ssize(expected) < 1) continue; + int j = Random::integer<int>(0, ssize(expected)); for (int k = 0; k < m; k++) { if (got.get(k, expected[j].first) != expected[j].second[k]) cerr << "got: " << got.get(k, expected[j].first) << ", expected: " << expected[j].second[k] << FAIL; } } else { - if (sz(expected) < 1) continue; - int j = Random::integer<int>(0, sz(expected)); + if (ssize(expected) < 1) continue; + int j = Random::integer<int>(0, ssize(expected)); got.reset(expected[j].first); expected.resize(j + 1); cur = expected.back().second; } - + } queries += n; } diff --git a/test/datastructures/segmentTree.cpp b/test/datastructures/segmentTree.cpp index 39cf20f..166dfd2 100644 --- a/test/datastructures/segmentTree.cpp +++ b/test/datastructures/segmentTree.cpp @@ -47,7 +47,7 @@ void performance_test1() { int i = Random::integer<int>(0, N); auto [l, r] = Random::pair<int>(0, N + 1); ll x = Random::integer<ll>(-1000, 1000); - + t.start(); tree.update(i, x); hash ^= tree.query(l, r); @@ -68,7 +68,7 @@ void stress_test2() { vector<ll> naive(n); SegTree tree(naive); naive = Random::integers<ll>(n, -1000, 1000); - copy(all(naive), tree.tree.begin() + n); + ranges::copy(naive, tree.tree.begin() + n); for (int operations = 0; operations < 1000; operations++) { { int l = Random::integer<int>(0, n + 1); @@ -102,7 +102,7 @@ void performance_test2() { int i = Random::integer<int>(0, N); auto [l, r] = Random::pair<int>(0, N + 1); ll x = Random::integer<ll>(-1000, 1000); - + t.start(); tree.modify(l, r, x); hash ^= tree.query(i); diff --git a/test/datastructures/sparseTable.cpp b/test/datastructures/sparseTable.cpp index 9a7fac5..078f336 100644 --- a/test/datastructures/sparseTable.cpp +++ b/test/datastructures/sparseTable.cpp @@ -8,13 +8,13 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> naive = Random::integers<ll>(n, -1000, 1000); SparseTable st; - st.init(&naive); + st.init(naive); for (int operations = 0; operations < 1000; operations++) { queries++; int l = Random::integer<int>(0, n+1); int r = Random::integer<int>(0, n+1); - ll got = st.queryIdempotent(l, r); + ll got = st.query(l, r); ll expected = r <= l ? -1 : l; for (int j = l; j < r; j++) { if (naive[j] < naive[expected]) expected = j; @@ -31,14 +31,14 @@ void performance_test() { vector<ll> naive = Random::integers<ll>(N, -1000, 1000); t.start(); SparseTable st; - st.init(&naive); + st.init(naive); t.stop(); hash_t hash = 0; for (int operations = 0; operations < N; operations++) { auto [l, r] = Random::pair<int>(0, N+1); - + t.start(); - hash += st.queryIdempotent(l, r); + hash += st.query(l, r); t.stop(); } if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/datastructures/sparseTableDisjoint.cpp b/test/datastructures/sparseTableDisjoint.cpp index 1147b42..d3f42ba 100644 --- a/test/datastructures/sparseTableDisjoint.cpp +++ b/test/datastructures/sparseTableDisjoint.cpp @@ -7,7 +7,7 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> naive = Random::integers<ll>(n, -1000, 1000); DisjointST st; - st.init(&naive); + st.init(naive); for (int operations = 0; operations < 1000; operations++) { queries++; int l = Random::integer<int>(0, n+1); @@ -28,12 +28,12 @@ void performance_test() { vector<ll> naive = Random::integers<ll>(N, -1000, 1000); t.start(); DisjointST st; - st.init(&naive); + st.init(naive); t.stop(); hash_t hash = 0; for (int operations = 0; operations < N; operations++) { auto [l, r] = Random::pair<int>(0, N+1); - + t.start(); hash += st.query(l, r); t.stop(); diff --git a/test/datastructures/stlHashMap.cpp b/test/datastructures/stlHashMap.cpp deleted file mode 100644 index 77976fd..0000000 --- a/test/datastructures/stlHashMap.cpp +++ /dev/null @@ -1,4 +0,0 @@ -#include "../util.h" -#include <datastructures/stlHashMap.cpp> - -int main() {}
\ No newline at end of file diff --git a/test/datastructures/stlPriorityQueue.cpp b/test/datastructures/stlPriorityQueue.cpp deleted file mode 100644 index 669f4d4..0000000 --- a/test/datastructures/stlPriorityQueue.cpp +++ /dev/null @@ -1,6 +0,0 @@ -#include "../util.h" -#include <datastructures/stlPriorityQueue.cpp> - -int main() { - test(); -}
\ No newline at end of file diff --git a/test/datastructures/stlPriorityQueue.cpp.awk b/test/datastructures/stlPriorityQueue.cpp.awk deleted file mode 100644 index 99d0fb9..0000000 --- a/test/datastructures/stlPriorityQueue.cpp.awk +++ /dev/null @@ -1,37 +0,0 @@ -/auto/ { - print "void test() {" - print "pQueue<ll> pq, pq2;" - print "pq.push(1);" - print "pq.push(5);" - print "pq.push(7);" - print "pq2.push(2);" - print "pq2.push(4);" - print "pq2.push(8);" -} -END { - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 8) cerr << \"error, got: \" << pq.top() << \", expected: 8\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 7) cerr << \"error, got: \" << pq.top() << \", expected: 7\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 6) cerr << \"error, got: \" << pq.top() << \", expected: 6\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 5) cerr << \"error, got: \" << pq.top() << \", expected: 5\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 4) cerr << \"error, got: \" << pq.top() << \", expected: 4\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 2) cerr << \"error, got: \" << pq.top() << \", expected: 2\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 1) cerr << \"error, got: \" << pq.top() << \", expected: 1\" << FAIL;" - print "pq.pop();" - print "if (!pq.empty()) cerr << \"error, got: \" << pq.top() << \", expected: empty\" << FAIL;" - print "cerr << \"testes example\" << endl;" - print "}" -} -{ print } diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp index 669f4d4..7405e4e 100644 --- a/test/datastructures/stlRope.cpp +++ b/test/datastructures/stlRope.cpp @@ -1,6 +1,6 @@ #include "../util.h" -#include <datastructures/stlPriorityQueue.cpp> +#include <datastructures/stlRope.cpp> int main() { test(); -}
\ No newline at end of file +} diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk index e19b8fd..df7c361 100644 --- a/test/datastructures/stlRope.cpp.awk +++ b/test/datastructures/stlRope.cpp.awk @@ -20,7 +20,7 @@ print "vector<int> got, expected = {0,1,6,2,3,4,5,7};" } END { - print " got.push_back(*it)" + print " got.push_back(*it);" print "if (got != expected) cerr << \"error\" << endl;" print "}" } diff --git a/test/datastructures/stlTree.cpp b/test/datastructures/stlTree.cpp deleted file mode 100644 index 7bacbee..0000000 --- a/test/datastructures/stlTree.cpp +++ /dev/null @@ -1,2 +0,0 @@ -#include "../util.h" -#include <datastructures/stlTree.cpp> diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp index 9a3527e..4f0fe03 100644 --- a/test/datastructures/treap.cpp +++ b/test/datastructures/treap.cpp @@ -26,14 +26,14 @@ void stress_test(int T, int n) { if (a.empty()) is_ins = true; if (is_ins) { - int ind = Random::integer<int>(0, (int)sz(a)+1); + int ind = Random::integer<int>(0, (int)ssize(a)+1); ll val = Random::integer((ll)-1e18, (ll)1e18+1); t.insert(ind, val); a.insert(a.begin() + ind, val); ins--; } else { - int ind = Random::integer<int>(0, (int)sz(a)); - int cnt = Random::integer<int>(1, 1 + min<int>({(int)sz(a)-ind, rem, (int)sqrt(n)})); + int ind = Random::integer<int>(0, (int)ssize(a)); + int cnt = Random::integer<int>(1, 1 + min<int>({(int)ssize(a)-ind, rem, (int)sqrt(n)})); t.remove(ind, cnt); a.erase(a.begin() + ind, a.begin() + ind + cnt); rem -= cnt; diff --git a/test/datastructures/unionFind.cpp b/test/datastructures/unionFind.cpp index 50ad50d..ced2355 100644 --- a/test/datastructures/unionFind.cpp +++ b/test/datastructures/unionFind.cpp @@ -1,8 +1,5 @@ #include "../util.h" -struct UF { - UF(int n) {init(n);} - #include <datastructures/unionFind.cpp> -}; +#include <datastructures/unionFind.cpp> struct Naive { vector<vector<int>> adj; @@ -28,15 +25,18 @@ struct Naive { } } - int findSet(int a) { + int find(int a) { int res = a; dfs(a, [&](int x){res = min(res, x);}); return res; } - void unionSets(int a, int b) { + bool link(int a, int b) { + bool linked = false; + dfs(a, [&](int x) { linked |= x == b; }); adj[a].push_back(b); adj[b].push_back(a); + return !linked; } int size(int a) { @@ -44,22 +44,38 @@ struct Naive { dfs(a, [&](int /**/){res++;}); return res; } + + int add() { + int idx = ssize(adj); + adj.emplace_back(); + seen.push_back(counter); + return idx; + } }; void stress_test() { ll queries = 0; for (int tries = 0; tries < 200; tries++) { int n = Random::integer<int>(1, 100); - UF uf(n); + UnionFind uf(n); Naive naive(n); - for (int i = 0; i < n; i++) { + int rounds = n; + for (int i = 0; i < rounds; i++) { for (int j = 0; j < 10; j++) { int a = Random::integer<int>(0, n); int b = Random::integer<int>(0, n); - uf.unionSets(a, b); - naive.unionSets(a, b); + auto got = uf.link(a, b); + auto expected = naive.link(a, b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } - UF tmp = uf; + { + auto got = uf.add(); + auto expected = naive.add(); + assert(expected == n); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + n++; + } + UnionFind tmp = uf; for (int j = 0; j < n; j++) { { auto got = tmp.size(j); @@ -69,8 +85,8 @@ void stress_test() { { int a = Random::integer<int>(0, n); int b = Random::integer<int>(0, n); - bool got = tmp.findSet(a) == tmp.findSet(b); - bool expected = naive.findSet(a) == naive.findSet(b); + bool got = tmp.find(a) == tmp.find(b); + bool expected = naive.find(a) == naive.find(b); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } @@ -84,7 +100,7 @@ constexpr int N = 2'000'000; void performance_test() { timer t; t.start(); - UF uf(N); + UnionFind uf(N); t.stop(); hash_t hash = 0; for (int operations = 0; operations < N; operations++) { @@ -92,9 +108,9 @@ void performance_test() { int j = Random::integer<int>(0, N); int k = Random::integer<int>(0, N); int l = Random::integer<int>(0, N); - + t.start(); - uf.unionSets(i, j); + uf.link(i, j); hash += uf.size(k); hash += uf.size(l); t.stop(); diff --git a/test/datastructures/waveletTree.cpp b/test/datastructures/waveletTree.cpp index 4c51b60..06b3e03 100644 --- a/test/datastructures/waveletTree.cpp +++ b/test/datastructures/waveletTree.cpp @@ -20,7 +20,7 @@ void stress_test() { ll expected = -1; if (x >= 0 && l + x < r) { vector<ll> tmp(naive.begin() + l, naive.begin() + r); - std::sort(all(tmp)); + ranges::sort(tmp); expected = tmp[x]; } if (got != expected) { @@ -59,7 +59,7 @@ void performance_test() { auto [l2, r2] = Random::pair<int>(0, N + 1); int x1 = Random::integer<ll>(l1, r1 + 1); ll x2 = Random::integer<ll>(-1000, 1000); - + t.start(); hash ^= tree.kth(l1, r1, x1); hash ^= tree.countSmaller(l2, r2, x2); diff --git a/test/fuzz.sh b/test/fuzz.sh deleted file mode 100755 index c166506..0000000 --- a/test/fuzz.sh +++ /dev/null @@ -1,14 +0,0 @@ -#!/bin/bash -set -e -cd "$(dirname "$0")" - -while true -do - seed="0" - while [[ $seed == 0* ]]; do - seed=$(tr -dc '0-9' </dev/random | head -c 18) - done - echo "Fuzz using seed: $seed" - echo - ./test.sh --seed=$seed "$@" -done diff --git a/test/geometry.h b/test/geometry.h index 0167d5c..06520c7 100644 --- a/test/geometry.h +++ b/test/geometry.h @@ -26,7 +26,7 @@ namespace Random { vector<ll> partition(ll n, std::size_t k){//min = 0; n += k; vector<ll> res = Random::distinct<ll>(k-1, 1, n); - sort(all(res)); + ranges::sort(res); res.emplace_back(n); ll last = 0; for (std::size_t i = 0; i < k; i++) { @@ -137,4 +137,4 @@ namespace Random { while (ccw(a, b, c) == 0) c = integerPoint(range); return {a, b, c}; } -}
\ No newline at end of file +} diff --git a/test/geometry/antipodalPoints.cpp b/test/geometry/antipodalPoints.cpp index 66f063b..ec2006e 100644 --- a/test/geometry/antipodalPoints.cpp +++ b/test/geometry/antipodalPoints.cpp @@ -9,7 +9,7 @@ constexpr ll EPS = 0; #include "../geometry.h" vector<pair<int, int>> naive(vector<pt> ps) { - ll n = sz(ps); + ll n = ssize(ps); auto test = [&](int i, int j){ if (dot(ps[j] - ps[i], ps[i - 1] - ps[i]) <= 0) return false; if (dot(ps[j] - ps[i], ps[i + 1] - ps[i]) <= 0) return false; @@ -34,13 +34,13 @@ void stress_test(ll range) { auto got = antipodalPoints(ps); for (auto& [a, b] : got) if (a > b) swap(a, b); - sort(all(got)); + ranges::sort(got); auto expected = naive(ps); for (auto& [a, b] : expected) if (a > b) swap(a, b); for (auto x : expected) { - auto it = lower_bound(all(got), x); + auto it = ranges::lower_bound(got, x); if (it == got.end() || *it != x) cerr << "error" << FAIL; } queries += n; @@ -58,7 +58,7 @@ void performance_test() { auto got = antipodalPoints(ps); t.stop(); - hash_t hash = sz(got); + hash_t hash = ssize(got); if (t.time > 50) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/geometry/circle.cpp b/test/geometry/circle.cpp index 3d3d27d..dc975ff 100644 --- a/test/geometry/circle.cpp +++ b/test/geometry/circle.cpp @@ -46,9 +46,9 @@ void test_circleIntersection(ll range) { auto got = circleIntersection(c1, r1, c2, r2); - if (sz(got) != expectedCount(real(c1), imag(c1), r1, real(c2), imag(c2), r2)) cerr << "error: wrong count" << FAIL; + if (ssize(got) != expectedCount(real(c1), imag(c1), r1, real(c2), imag(c2), r2)) cerr << "error: wrong count" << FAIL; - for (int i = 0; i < sz(got); i++) { + for (int i = 0; i < ssize(got); i++) { for (int j = 0; j < i; j++) { if (abs(got[i] - got[j]) < 1e-6) cerr << "error: identical" << FAIL; } @@ -58,7 +58,7 @@ void test_circleIntersection(ll range) { if (float_error(abs(c1 - p), r1) > 1e-6) cerr << "error: 1" << FAIL; if (float_error(abs(c2 - p), r2) > 1e-6) cerr << "error: 2" << FAIL; } - queries += sz(got); + queries += ssize(got); } cerr << "tested circleIntersection: " << queries << endl; } @@ -91,9 +91,9 @@ void test_circleRayIntersection(ll range) { else expected = 1; } - if (sz(got) != expected) cerr << "error: wrong count" << FAIL; + if (ssize(got) != expected) cerr << "error: wrong count" << FAIL; - for (int i = 0; i < sz(got); i++) { + for (int i = 0; i < ssize(got); i++) { for (int j = 0; j < i; j++) { if (abs(got[i] - got[j]) < 1e-6) cerr << "error: identical" << FAIL; } @@ -103,7 +103,7 @@ void test_circleRayIntersection(ll range) { if (float_error(abs(c - p), r) > 1e-6) cerr << "error: 1" << FAIL; if (distToLine(orig, orig + dir, p) > 1e-6) cerr << "error: 2" << FAIL; } - queries += sz(got); + queries += ssize(got); } cerr << "tested circleIntersection: " << queries << endl; } diff --git a/test/geometry/closestPair.cpp b/test/geometry/closestPair.cpp index 99f9d5e..a8e1382 100644 --- a/test/geometry/closestPair.cpp +++ b/test/geometry/closestPair.cpp @@ -13,7 +13,7 @@ ll isqrt(ll x) {return (ll)sqrtl(x);} //strict convex hull ll naive(const vector<pt>& ps) { ll opt = LL::INF; - for (ll i = 0; i < sz(ps); i++) { + for (ll i = 0; i < ssize(ps); i++) { for (ll j = 0; j < i; j++) { opt = min(opt, norm(ps[i] - ps[j])); } diff --git a/test/geometry/closestPair.double.cpp b/test/geometry/closestPair.double.cpp index 427fcf8..14ccd0d 100644 --- a/test/geometry/closestPair.double.cpp +++ b/test/geometry/closestPair.double.cpp @@ -10,7 +10,7 @@ constexpr ll INF = LL::INF; //strict convex hull double naive(const vector<pt>& ps) { double opt = LL::INF; - for (ll i = 0; i < sz(ps); i++) { + for (ll i = 0; i < ssize(ps); i++) { for (ll j = 0; j < i; j++) { opt = min(opt, norm(ps[i] - ps[j])); } diff --git a/test/geometry/convexHull.cpp b/test/geometry/convexHull.cpp index 8a5ad9b..ee858f9 100644 --- a/test/geometry/convexHull.cpp +++ b/test/geometry/convexHull.cpp @@ -9,7 +9,7 @@ constexpr ll EPS = 0; //strict convex hull ll isConvexHull(const vector<pt>& ps, const vector<pt>& hull) { - ll n = sz(hull) - 1; + ll n = ssize(hull) - 1; if (n == 0) { for (pt p : ps) if (p != hull[0]) return 1; return 0; @@ -67,7 +67,7 @@ void performance_test() { t.start(); auto a = convexHull(ps); t.stop(); - hash_t hash = sz(a); + hash_t hash = ssize(a); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp index 06ad6b5..51df879 100644 --- a/test/geometry/delaunay.cpp +++ b/test/geometry/delaunay.cpp @@ -6,28 +6,27 @@ auto cross(pt p, pt a, pt b) {return cross(a - p, b - p);} #pragma GCC diagnostic ignored "-Wunused-variable" #include <geometry/delaunay.cpp> + vector<pt> convexHull(vector<pt> pts){ - sort(all(pts), [](const pt& a, const pt& b){ - return real(a) == real(b) ? imag(a) < imag(b) - : real(a) < real(b); - }); - pts.erase(unique(all(pts)), pts.end()); + ranges::sort(pts, {}, + [](pt x) { return pair{real(x), imag(x)}; }); + pts.erase(begin(ranges::unique(pts)), end(pts)); int k = 0; - vector<pt> h(2 * sz(pts)); - auto half = [&](auto begin, auto end, int t) { - for (auto it = begin; it != end; it++) { - while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points! - h[k++] = *it; + vector<pt> h(2 * ssize(pts)); + auto half = [&](auto &&v, int t) { + for (auto x: v) { + while (k > t && cross(h[k-2], h[k-1], x) < 0) k--; // allow collinear points + h[k++] = x; }}; - half(all(pts), 1); // Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. + half(pts, 1); // Untere Hülle. + half(pts | views::reverse | views::drop(1), k); // Obere Hülle h.resize(k); return h; } lll area(const vector<pt>& poly) { //poly[0] == poly.back() lll res = 0; - for (int i = 0; i + 1 < sz(poly); i++) + for (int i = 0; i + 1 < ssize(poly); i++) res += cross(poly[i], poly[i + 1]); return res; } @@ -89,15 +88,15 @@ void stress_test(ll LIM, ll range) { hull.pop_back(); auto got = delaunay(ps); - if (sz(got) % 3 != 0) cerr << "error: not triangles" << FAIL; - if (sz(got) / 3 + sz(hull) - 3 + 1 != 2 * sz(ps) - 4) cerr << "error: wrong number" << FAIL; + if (ssize(got) % 3 != 0) cerr << "error: not triangles" << FAIL; + if (ssize(got) / 3 + ssize(hull) - 3 + 1 != 2 * ssize(ps) - 4) cerr << "error: wrong number" << FAIL; //all triangles should be oriented ccw lll gotArea = 0; - for (int i = 0; i < sz(got); i += 3) gotArea += cross(got[i], got[i+1], got[i+2]); + for (int i = 0; i < ssize(got); i += 3) gotArea += cross(got[i], got[i+1], got[i+2]); if (gotArea != expectedArea) cerr << "error: wrong area" << FAIL; - for (int i = 0; i < sz(got); i++) { + for (int i = 0; i < ssize(got); i++) { int ii = i + 1; if (i / 3 != ii / 3) ii -= 3; for (int j = 0; j < i; j++) { @@ -111,7 +110,7 @@ void stress_test(ll LIM, ll range) { for (pt p : ps) seen |= p == got[i]; if (!seen) cerr << "error: invalid point" << FAIL; } - for (int i = 0; i < sz(got); i += 3) { + for (int i = 0; i < ssize(got); i += 3) { for (pt p : ps) { if (p == got[i]) continue; if (p == got[i+1]) continue; @@ -131,7 +130,7 @@ void performance_test() { t.start(); auto got = delaunay(ps); t.stop(); - hash_t hash = sz(got); + hash_t hash = ssize(got); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/geometry/formulas.cpp b/test/geometry/formulas.cpp index d63d431..f472e1f 100644 --- a/test/geometry/formulas.cpp +++ b/test/geometry/formulas.cpp @@ -107,7 +107,7 @@ void test_uniqueAngle(ll range) { if (it->second != expected) cerr << "error: inconsistent" << FAIL; queries++; } - cerr << "tested uniqueAngle: " << queries << " (" << sz(seen) << ")" << endl; + cerr << "tested uniqueAngle: " << queries << " (" << ssize(seen) << ")" << endl; } int main() { diff --git a/test/geometry/hpi.cpp b/test/geometry/hpi.cpp index a2326bc..e22e8c6 100644 --- a/test/geometry/hpi.cpp +++ b/test/geometry/hpi.cpp @@ -1,4 +1,6 @@ #include "../util.h" +#define sz(X) (ll)::size(X) +#define all(X) ::begin(X), ::end(X) constexpr ll EPS = 0; #define double ll #define polar polar<ll> @@ -14,10 +16,10 @@ ll sgn(ll x) { //https://cp-algorithms.com/geometry/halfplane-intersection.html namespace cpalgo { // Redefine epsilon and infinity as necessary. Be mindful of precision errors. - const long double eps = 1e-9, inf = 1e9; + const long double eps = 1e-9, inf = 1e9; // Basic point/vector struct. - struct Point { + struct Point { long double x, y; explicit Point(long double x_ = 0, long double y_ = 0) : x(x_), y(y_) {} @@ -26,23 +28,23 @@ namespace cpalgo { // Addition, substraction, multiply by constant, dot product, cross product. friend Point operator + (const Point& p, const Point& q) { - return Point(p.x + q.x, p.y + q.y); + return Point(p.x + q.x, p.y + q.y); } - friend Point operator - (const Point& p, const Point& q) { - return Point(p.x - q.x, p.y - q.y); + friend Point operator - (const Point& p, const Point& q) { + return Point(p.x - q.x, p.y - q.y); } - friend Point operator * (const Point& p, const long double& k) { - return Point(p.x * k, p.y * k); - } + friend Point operator * (const Point& p, const long double& k) { + return Point(p.x * k, p.y * k); + } friend long double dot(const Point& p, const Point& q) { return p.x * q.x + p.y * q.y; } - friend long double cross(const Point& p, const Point& q) { - return p.x * q.y - p.y * q.x; + friend long double cross(const Point& p, const Point& q) { + return p.x * q.y - p.y * q.x; } friend std::ostream& operator<<(std::ostream& os, const Point& p) { @@ -53,10 +55,10 @@ namespace cpalgo { }; // Basic half-plane struct. - struct Halfplane { + struct Halfplane { // 'p' is a passing point of the line and 'pq' is the direction vector of the line. - Point p, pq; + Point p, pq; long double angle; Halfplane() {} @@ -66,16 +68,16 @@ namespace cpalgo { Halfplane(array<pt, 2> ps) : Halfplane(ps[0], ps[1]) {} Halfplane(hp h) : Halfplane(h.from, h.to) {} - // Check if point 'r' is outside this half-plane. + // Check if point 'r' is outside this half-plane. // Every half-plane allows the region to the LEFT of its line. bool out(const Point& r) { - return cross(pq, r - p) < -eps; + return cross(pq, r - p) < -eps; } - // Comparator for sorting. - bool operator < (const Halfplane& e) const { + // Comparator for sorting. + bool operator < (const Halfplane& e) const { return angle < e.angle; - } + } // Intersection point of the lines of two half-planes. It is assumed they're never parallel. friend Point inter(const Halfplane& s, const Halfplane& t) { @@ -89,13 +91,13 @@ namespace cpalgo { }; // Actual algorithm - vector<Point> hp_intersect(vector<Halfplane>& H) { + vector<Point> hp_intersect(vector<Halfplane>& H) { /*Point box[4] = { // Bounding box in CCW order - Point(inf, inf), - Point(-inf, inf), - Point(-inf, -inf), - Point(inf, -inf) + Point(inf, inf), + Point(-inf, inf), + Point(-inf, -inf), + Point(inf, -inf) }; for(int i = 0; i<4; i++) { // Add bounding box half-planes. @@ -181,7 +183,7 @@ void test_check(ll range) { auto b = Random::line(range); auto c = b; while (cross(b[0] - b[1], c[0] - c[1]) == 0) c = Random::line(range); - + bool got = hp(a[0], a[1]).check(hp(b[0], b[1]), hp(c[0], c[1])); bool expected = naiveCheck(a, b, c); diff --git a/test/geometry/polygon.cpp b/test/geometry/polygon.cpp index 2653dbd..1d9f828 100644 --- a/test/geometry/polygon.cpp +++ b/test/geometry/polygon.cpp @@ -135,7 +135,7 @@ void test_insideConvex(ll LIM, ll range) { // convex hull without duplicates, h[0] != h.back() // apply comments if border counts as inside bool insideOrOnConvex(pt p, const vector<pt>& hull) { - int l = 0, r = sz(hull) - 1; + int l = 0, r = ssize(hull) - 1; if (cross(hull[0], hull[r], p) > 0) return false; while (l + 1 < r) { int m = (l + r) / 2; @@ -155,7 +155,7 @@ void test_minkowski(ll LIM, ll range) { auto got = minkowski(A, B); bool convex = true; - for (int i = 0; i < sz(got); i++) convex &= cross(got[i], got[(i+1) % sz(got)], got[(i+2) % sz(got)]) >= 0; + for (int i = 0; i < ssize(got); i++) convex &= cross(got[i], got[(i+1) % ssize(got)], got[(i+2) % ssize(got)]) >= 0; if (!convex) cerr << "error: not convex" << FAIL; for (pt a : A) { @@ -172,19 +172,19 @@ double naive_dist(const vector<pt>& ps, const vector<pt>& qs) { //check if intersect double res = LD::INF; bool intersect = true; - for (int i = 0; i < sz(qs); i++) { + for (int i = 0; i < ssize(qs); i++) { bool sep = true; for (pt p : ps) { - res = min(res, distToSegment(qs[i], qs[(i+1) % sz(qs)], p)); - sep &= cross(qs[i], qs[(i+1) % sz(qs)], p) <= 0; + res = min(res, distToSegment(qs[i], qs[(i+1) % ssize(qs)], p)); + sep &= cross(qs[i], qs[(i+1) % ssize(qs)], p) <= 0; } if (sep) intersect = false; } - for (int i = 0; i < sz(ps); i++) { + for (int i = 0; i < ssize(ps); i++) { bool sep = true; for (pt q : qs) { - res = min(res, distToSegment(ps[i], ps[(i+1) % sz(ps)], q)); - sep &= cross(ps[i], ps[(i+1) % sz(ps)], q) <= 0; + res = min(res, distToSegment(ps[i], ps[(i+1) % ssize(ps)], q)); + sep &= cross(ps[i], ps[(i+1) % ssize(ps)], q) <= 0; } if (sep) intersect = false; } @@ -263,10 +263,10 @@ void test_intersect(ll LIM, ll range) { } } } - if (sz(expected) > 1 && expected[0] == expected[1]) expected.pop_back(); + if (ssize(expected) > 1 && expected[0] == expected[1]) expected.pop_back(); - sort(all(got)); - sort(all(expected)); + ranges::sort(got); + ranges::sort(expected); if (got != expected) cerr << "error" << FAIL; diff --git a/test/geometry/segmentIntersection.cpp b/test/geometry/segmentIntersection.cpp index 0f67eb2..f48fb8a 100644 --- a/test/geometry/segmentIntersection.cpp +++ b/test/geometry/segmentIntersection.cpp @@ -40,7 +40,7 @@ vector<seg> randomSegs(int n, ll range) { } bool naive(vector<seg>& segs) { - for (ll i = 0; i < sz(segs); i++) { + for (ll i = 0; i < ssize(segs); i++) { for (ll j = 0; j < i; j++) { if (segmentIntersection(segs[i].a, segs[i].b, segs[j].a, segs[j].b)) return true; } diff --git a/test/geometry/sortAround.cpp b/test/geometry/sortAround.cpp index abd803e..895a6d6 100644 --- a/test/geometry/sortAround.cpp +++ b/test/geometry/sortAround.cpp @@ -24,7 +24,7 @@ void test_tiny() { }; auto got = expected; for (int i = 0; i < 100'000; i++) { - shuffle(all(got), Random::rng); + ranges::shuffle(got, Random::rng); sortAround(0, got); if (got != expected) cerr << "error" << FAIL; } @@ -51,8 +51,8 @@ void stress_test(ll range) { auto isLeft = [&](pt p){return real(p - c) < 0 || (real(p - c) == 0 && imag(p - c) < 0);}; auto isCCW = [&](pt a, pt b){return cross(c, a, b) > 0;}; - if (!is_partitioned(all(ps), isLeft)) cerr << "error 1" << FAIL; - auto mid = partition_point(all(ps), isLeft); + if (!ranges::is_partitioned(ps, isLeft)) cerr << "error 1" << FAIL; + auto mid = ranges::partition_point(ps, isLeft); if (!is_sorted(ps.begin(), mid, isCCW)) cerr << "error 2" << FAIL; if (!is_sorted(mid, ps.end(), isCCW)) cerr << "error 3" << FAIL; queries += n; diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp index 4635086..fd6326c 100644 --- a/test/graph/2sat.cpp +++ b/test/graph/2sat.cpp @@ -25,7 +25,7 @@ struct RandomClause { return false; } - void add(sat2& sat) const { + void add(SAT2& sat) const { int va = a; int vb = b; if (type == 0) sat.addImpl(va, vb); @@ -80,9 +80,8 @@ void stress_test() { vector<RandomClause> clauses; for (int i = 0; i < m; i++) clauses.emplace_back(n); - sat2 sat(n); + SAT2 sat(n); for (auto& c : clauses) c.add(sat); - adj = sat.adj; bool got = sat.solve(); bool expected = naive(n, clauses); @@ -113,11 +112,8 @@ void performance_test() { vector<RandomClause> clauses; for (int i = 0; i < M; i++) clauses.emplace_back(N); t.start(); - sat2 sat(N); + SAT2 sat(N); for (auto& c : clauses) c.add(sat); - t.stop(); - adj = sat.adj; - t.start(); hash_t hash = sat.solve(); t.stop(); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/graph/2sat.cpp.awk b/test/graph/2sat.cpp.awk deleted file mode 100644 index d0215d8..0000000 --- a/test/graph/2sat.cpp.awk +++ /dev/null @@ -1,6 +0,0 @@ -/scc variablen/ { - print; - print "\tvector<vector<int>> adj;"; - next -} -{ print } diff --git a/test/graph/TSP.cpp b/test/graph/TSP.cpp index 930ec88..3b1ce94 100644 --- a/test/graph/TSP.cpp +++ b/test/graph/TSP.cpp @@ -7,9 +7,9 @@ constexpr ll INF = LL::INF; #include <graph/TSP.cpp> vector<int> naive() { - int n = sz(dist); + int n = ssize(dist); vector<int> todo(n - 1); - iota(all(todo), 1); + iota(begin(todo), end(todo), 1); vector<int> res; ll best = LL::INF; do { @@ -26,7 +26,7 @@ vector<int> naive() { res.insert(res.begin(), 0); res.push_back(0); } - } while (next_permutation(all(todo))); + } while (ranges::next_permutation(todo).found); return res; } @@ -39,7 +39,7 @@ void stress_test() { auto expected = naive(); auto got = TSP(); - + if (got != expected) cerr << "error" << FAIL; queries += n; } diff --git a/test/graph/articulationPoints.bcc.cpp b/test/graph/articulationPoints.bcc.cpp index e9fc32f..927ceb4 100644 --- a/test/graph/articulationPoints.bcc.cpp +++ b/test/graph/articulationPoints.bcc.cpp @@ -8,11 +8,11 @@ struct edge { #include <datastructures/unionFind.cpp> vector<vector<int>> naiveBCC(int m) { - init(m); + UnionFind uf(m); - vector<int> seen(sz(adj), -1); + vector<int> seen(ssize(adj), -1); int run = 0; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { for (auto e : adj[i]) { run++; seen[i] = run; @@ -28,17 +28,17 @@ vector<vector<int>> naiveBCC(int m) { } } for (auto ee : adj[i]) { - if (seen[ee.to] == run) unionSets(ee.id, e.id); + if (seen[ee.to] == run) uf.link(ee.id, e.id); } } } vector<vector<int>> res(m); for (int i = 0; i < m; i++) { - res[findSet(i)].push_back(i); + res[uf.find(i)].push_back(i); } - for (auto& v : res) sort(all(v)); - res.erase(remove_if(all(res), [](const vector<int>& v){return sz(v) <= 1;}), res.end()); - sort(all(res)); + for (auto& v : res) ranges::sort(v); + res.erase(begin(ranges::remove_if(res, [](const vector<int>& v){return ssize(v) <= 1;})), end(res)); + ranges::sort(res); return res; } @@ -60,12 +60,12 @@ void stress_test_bcc(int LIM) { auto expected = naiveBCC(nextId); find(); - vector<vector<int>> got(sz(bcc)); - for (int i = 0; i < sz(bcc); i++) { + vector<vector<int>> got(ssize(bcc)); + for (int i = 0; i < ssize(bcc); i++) { for (auto e : bcc[i]) got[i].push_back(e.id); - sort(all(got[i])); + ranges::sort(got[i]); } - sort(all(got)); + ranges::sort(got); if (got != expected) cerr << "error" << FAIL; queries += n; diff --git a/test/graph/articulationPoints.bridges.cpp b/test/graph/articulationPoints.bridges.cpp index a1b89d2..15408ea 100644 --- a/test/graph/articulationPoints.bridges.cpp +++ b/test/graph/articulationPoints.bridges.cpp @@ -7,10 +7,10 @@ struct edge { #undef Edge vector<bool> naiveBridges(const vector<pair<int, int>>& edges) { - vector<bool> res(sz(edges)); + vector<bool> res(ssize(edges)); - vector<int> seen(sz(adj), -1); - for (int i = 0; i < sz(edges); i++) { + vector<int> seen(ssize(adj), -1); + for (int i = 0; i < ssize(edges); i++) { auto [a, b] = edges[i]; vector<int> todo = {a}; seen[a] = i; @@ -40,14 +40,14 @@ void stress_test_bridges() { adj.assign(n, {}); vector<pair<int, int>> edges; g.forEdges([&](int a, int b){ - adj[a].push_back({a, b, sz(edges)}); - adj[b].push_back({b, a, sz(edges)}); + adj[a].push_back({a, b, ssize(edges)}); + adj[b].push_back({b, a, ssize(edges)}); edges.emplace_back(a, b); }); auto expected = naiveBridges(edges); find(); - vector<bool> got(sz(edges)); + vector<bool> got(ssize(edges)); for (auto e : bridges) { if (got[e.id]) cerr << "error: duclicate" << FAIL; got[e.id] = true; diff --git a/test/graph/articulationPoints.cpp b/test/graph/articulationPoints.cpp index 8ee6bc4..6960f73 100644 --- a/test/graph/articulationPoints.cpp +++ b/test/graph/articulationPoints.cpp @@ -7,10 +7,10 @@ struct edge { #undef Edge vector<bool> naiveArt() { - vector<bool> res(sz(adj)); + vector<bool> res(ssize(adj)); - vector<int> seen(sz(adj), -1); - for (int i = 0; i < sz(adj); i++) { + vector<int> seen(ssize(adj), -1); + for (int i = 0; i < ssize(adj); i++) { if (adj[i].empty()) continue; seen[i] = i; vector<ll> todo = {adj[i][0].to}; @@ -72,9 +72,9 @@ void performance_test() { }); t.start(); - find(); + find(); t.stop(); - hash_t hash = sz(bridges) + sz(bcc); + hash_t hash = ssize(bridges) + ssize(bcc); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/binary_lifting.cpp b/test/graph/binary_lifting.cpp new file mode 100644 index 0000000..20318da --- /dev/null +++ b/test/graph/binary_lifting.cpp @@ -0,0 +1,60 @@ +#include "../util.h" +#include <graph/binary_lifting.cpp> +namespace expected { +#include <graph/hld.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(2, 30); + Graph<NoData> g(n); + g.tree(); + + vector<vector<int>> adj(n); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + Lift lift(adj, 0); + + expected::adj = adj; + expected::init(); + + for (int i = 0; i < n; i++) { + for (int j = 0; j <= i; j++) { + auto got = lift.lca(i, j); + auto expected = expected::get_lca(i, j); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.tree(); + vector<vector<int>> adj(N); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + hash_t hash = 0; + t.start(); + Lift lift(adj, 0); + for (int i = 1; i < N; i++) hash += lift.lca(i-1, i); + t.stop(); + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/blossom.cpp b/test/graph/blossom.cpp index f44f815..56d3132 100644 --- a/test/graph/blossom.cpp +++ b/test/graph/blossom.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace tutte { -void gauss(int n, int m); +vector<int> gauss(vector<vector<ll>> &mat); #include <graph/matching.cpp> #include <math/shortModInv.cpp> #include <math/lgsFp.cpp> @@ -15,20 +15,20 @@ void stress_test() { GM blossom(n); srand(Random::rng()); - tutte::adj.assign(n, {}); + vector<vector<int>> adj(n); Graph<NoData> g(n); g.erdosRenyi(m); g.forEdges([&](int a, int b){ - tutte::adj[a].push_back(b); - tutte::adj[b].push_back(a); + adj[a].push_back(b); + adj[b].push_back(a); blossom.adj[a].push_back(b); blossom.adj[b].push_back(a); }); ll got = blossom.match(); - ll expected = tutte::max_matching(); + ll expected = tutte::max_matching(adj); vector<bool> seen(n); ll got2 = 0; diff --git a/test/graph/bronKerbosch.cpp b/test/graph/bronKerbosch.cpp index 1a90c06..8c0a200 100644 --- a/test/graph/bronKerbosch.cpp +++ b/test/graph/bronKerbosch.cpp @@ -9,7 +9,7 @@ void naive(bits mask = {}, int l = 0) { if (mask[i]) continue; if ((adj[i] & mask) == mask) maximal = false; } - for (; l < sz(adj); l++) { + for (; l < ssize(adj); l++) { if ((adj[l] & mask) == mask) { maximal = false; mask[l] = 1; @@ -37,10 +37,10 @@ void stress_test() { naiveCliques.clear(); naive(); - sort(all(cliques), [](bits a, bits b){return a.to_ullong() < b.to_ullong();}); - sort(all(naiveCliques), [](bits a, bits b){return a.to_ullong() < b.to_ullong();}); + ranges::sort(cliques, {}, [](bits x) { return x.to_ullong(); }); + ranges::sort(naiveCliques, {}, [](bits x) { return x.to_ullong(); }); - if (cliques != naiveCliques) cerr << "got: " << sz(cliques) << ", expected: " << sz(naiveCliques) << FAIL; + if (cliques != naiveCliques) cerr << "got: " << ssize(cliques) << ", expected: " << ssize(naiveCliques) << FAIL; queries += n; } cerr << "tested random queries: " << queries << endl; @@ -62,7 +62,7 @@ void performance_test() { bronKerbosch(); t.stop(); - hash_t hash = sz(cliques); + hash_t hash = ssize(cliques); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/centroid.cpp b/test/graph/centroid.cpp index c3f1d3f..d231c3e 100644 --- a/test/graph/centroid.cpp +++ b/test/graph/centroid.cpp @@ -13,9 +13,9 @@ int subtreeSize(int c, int p) { vector<int> naive() { vector<int> res; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { bool isCentroid = true; - for (int j : adj[i]) isCentroid &= 2*subtreeSize(j, i) <= sz(adj); + for (int j : adj[i]) isCentroid &= 2*subtreeSize(j, i) <= ssize(adj); if (isCentroid) res.push_back(i); } return res; @@ -33,16 +33,16 @@ void stress_test() { adj[a].push_back(b); adj[b].push_back(a); }); - + auto expected = naive(); - sort(all(expected)); + ranges::sort(expected); for (int i = 0; i < n; i++) { auto [a, b] = find_centroid(i); vector<int> got; if (a >= 0) got.push_back(a); if (b >= 0) got.push_back(b); - sort(all(got)); + ranges::sort(got); if (got != expected) cerr << "error" << FAIL; } @@ -63,7 +63,7 @@ void performance_test() { adj[b].push_back(a); }); - t.start(); + t.start(); auto [gotA, gotB] = find_centroid(); t.stop(); hash_t hash = gotA + gotB; diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp index 8114339..ef087e3 100644 --- a/test/graph/connect.cpp +++ b/test/graph/connect.cpp @@ -52,8 +52,8 @@ void stress_test(int lim) { int m = Random::integer<int>(30, 300); vector<int> insertOrder(m); - iota(all(insertOrder), 0); - shuffle(all(insertOrder), Random::rng); + iota(begin(insertOrder), end(insertOrder), 0); + ranges::shuffle(insertOrder, Random::rng); vector<pair<int, int>> edges(m, {-1, -1}); connect con(n, m); @@ -104,15 +104,15 @@ void performance_test() { t.stop(); vector<int> insertOrder(M); - iota(all(insertOrder), 0); - shuffle(all(insertOrder), Random::rng); + iota(begin(insertOrder), end(insertOrder), 0); + ranges::shuffle(insertOrder, Random::rng); vector<bool> inserted(M); for (int i = 0, j = 0; i < N; i++) { int a = Random::integer<int>(0, N); int b = a; while (b == a) b = Random::integer<int>(0, N); - + t.start(); con.addEdge(a, b, insertOrder[i]); t.stop(); diff --git a/test/graph/cycleCounting.cpp b/test/graph/cycleCounting.cpp index 6459162..bfe313e 100644 --- a/test/graph/cycleCounting.cpp +++ b/test/graph/cycleCounting.cpp @@ -4,20 +4,16 @@ int naive(const vector<pair<int, int>>& edges, int n) { int res = 0; - for (int i = 1; i < (1ll << sz(edges)); i++) { + for (int i = 1; i < (1ll << ssize(edges)); i++) { vector<int> deg(n); - init(n); + UnionFind uf(n); int cycles = 0; - for (int j = 0; j < sz(edges); j++) { + for (int j = 0; j < ssize(edges); j++) { if (((i >> j) & 1) != 0) { auto [a, b] = edges[j]; deg[a]++; deg[b]++; - if (findSet(a) != findSet(b)) { - unionSets(a, b); - } else { - cycles++; - } + if (!uf.link(a, b)) cycles++; } } bool ok = cycles == 1; @@ -66,7 +62,7 @@ void performance_test() { t.start(); hash_t hash = cyc.count(); - cerr << sz(cyc.base) << endl; + cerr << ssize(cyc.base) << endl; t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; diff --git a/test/graph/dijkstra.cpp b/test/graph/dijkstra.cpp index dd5b826..d79e700 100644 --- a/test/graph/dijkstra.cpp +++ b/test/graph/dijkstra.cpp @@ -13,21 +13,21 @@ void stress_test(int LIM) { int n = Random::integer<int>(2, 30); int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); - vector<vector<path>> adj(n); + vector<vector<pair<int, ll>>> adj(n); vector<edge> edges; Graph<NoData, true> g(n); g.erdosRenyi(m); g.forEdges([&](int a, int b){ ll w = Random::integer<ll>(1, 1'000'000'000'000ll); - adj[a].push_back({w, b}); + adj[a].emplace_back(b, w); edges.push_back({a, b, w}); }); for (int i = 0; i < n; i++) { auto got = dijkstra(adj, i); auto expected = bellmannFord(n, edges, i); - + if (got != expected) cerr << "error" << FAIL; queries += n; } @@ -41,12 +41,12 @@ void performance_test() { timer t; Graph<NoData> g(N); g.erdosRenyi(M); - vector<vector<path>> adj(N); + vector<vector<pair<int, ll>>> adj(N); g.forEdges([&](int a, int b){ ll w1 = Random::integer<ll>(1, 1'000'000'000'000ll); ll w2 = Random::integer<ll>(1, 1'000'000'000'000ll); - adj[a].push_back({w1, b}); - adj[b].push_back({w2, a}); + adj[a].emplace_back(b, w1); + adj[b].emplace_back(a, w2); }); t.start(); diff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp deleted file mode 100644 index bd270be..0000000 --- a/test/graph/dinic.cpp +++ /dev/null @@ -1,62 +0,0 @@ -#include "../util.h" -constexpr ll INF = LL::INF; -namespace dinic { -#include <graph/dinic.cpp> -} - -namespace pushRelabel { -#include <graph/pushRelabel.cpp> -} - -void stress_test() { - ll queries = 0; - for (int tries = 0; tries < 20'000; tries++) { - int n = Random::integer<int>(2, 30); - int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); - - dinic::adj.assign(n, {}); - pushRelabel::adj.assign(n, {}); - - Graph<NoData, true> g(n); - g.erdosRenyi(m); - g.forEdges([](int a, int b){ - ll w = Random::integer<ll>(1, 1'000'000'000'000ll); - dinic::addEdge(a, b, w); - pushRelabel::addEdge(a, b, w); - }); - - ll got = dinic::maxFlow(0, n - 1); - ll expected = pushRelabel::maxFlow(0, n - 1); - - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - queries += n; - } - cerr << "tested random queries: " << queries << endl; -} - -constexpr int N = 50000; -constexpr int M = 200000; -void performance_test() { - using namespace dinic; - timer t; - Graph<NoData> g(N); - g.erdosRenyi(M); - adj.assign(N, {}); - g.forEdges([](int a, int b){ - ll w1 = Random::integer<ll>(1, 1'000'000'000'000ll); - ll w2 = Random::integer<ll>(1, 1'000'000'000'000ll); - addEdge(a, b, w1); - addEdge(b, a, w2); - }); - - t.start(); - hash_t hash = maxFlow(0, N - 1); - t.stop(); - if (t.time > 2000) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; -} - -int main() { - stress_test(); - if (!sanitize) performance_test(); -} diff --git a/test/graph/dinicScaling.cpp b/test/graph/dinitzScaling.cpp index 065dd9e..0ab9718 100644 --- a/test/graph/dinicScaling.cpp +++ b/test/graph/dinitzScaling.cpp @@ -1,6 +1,6 @@ #include "../util.h" -namespace dinic { -#include <graph/dinicScaling.cpp> +namespace dinitz { +#include <graph/dinitzScaling.cpp> } namespace pushRelabel { @@ -13,20 +13,20 @@ void stress_test() { int n = Random::integer<int>(2, 30); int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); - dinic::adj.assign(n, {}); + dinitz::adj.assign(n, {}); pushRelabel::adj.assign(n, {}); Graph<NoData, true> g(n); g.erdosRenyi(m); g.forEdges([](int a, int b){ ll w = Random::integer<ll>(1, 1'000'000'000'000ll); - dinic::addEdge(a, b, w); + dinitz::addEdge(a, b, w); pushRelabel::addEdge(a, b, w); }); - ll got = dinic::maxFlow(0, n - 1); + ll got = dinitz::maxFlow(0, n - 1); ll expected = pushRelabel::maxFlow(0, n - 1); - + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } @@ -36,7 +36,7 @@ void stress_test() { constexpr int N = 50000; constexpr int M = 200000; void performance_test() { - using namespace dinic; + using namespace dinitz; timer t; Graph<NoData> g(N); g.erdosRenyi(M); diff --git a/test/graph/euler.cpp b/test/graph/euler.cpp index b26add1..5314123 100644 --- a/test/graph/euler.cpp +++ b/test/graph/euler.cpp @@ -20,7 +20,7 @@ Euler eulerGraph(int n, int m) { } int last = -1; for (int i = 0; i < n; i++) { - if (sz(res.adj[i]) % 2 != 0) { + if (ssize(res.adj[i]) % 2 != 0) { if (last >= 0) { res.addEdge(last, i); last = -1; @@ -41,25 +41,25 @@ void stress_test() { int m = Random::integer<int>(n-1, 200); auto g = eulerGraph(n, m); - + vector<vector<int>> expected(n); for (int i = 0; i < n; i++) { for (auto [j, rev] : g.adj[i]) { expected[i].push_back(j); } - sort(all(expected[i])); + ranges::sort(expected[i]); } g.euler(0); vector<vector<int>> got(n); if (g.cycle.front() != g.cycle.back()) cerr << "error: not cyclic" << FAIL; - for (int i = 1; i < sz(g.cycle); i++) { + for (int i = 1; i < ssize(g.cycle); i++) { int a = g.cycle[i-1]; int b = g.cycle[i]; got[a].push_back(b); got[b].push_back(a); } - for (auto& v : got) sort(all(v)); + for (auto& v : got) ranges::sort(v); if (got != expected) cerr << "error" << FAIL; queries += n; diff --git a/test/graph/floydWarshall.cpp b/test/graph/floydWarshall.cpp index 5926449..819af39 100644 --- a/test/graph/floydWarshall.cpp +++ b/test/graph/floydWarshall.cpp @@ -40,7 +40,7 @@ void stress_test(int LIM) { if (path.empty()) continue; if (path.front() != i) cerr << "error: start" << FAIL; if (path.back() != k) cerr << "error: end" << FAIL; - for (int l = 1; l < sz(path); l++) { + for (int l = 1; l < ssize(path); l++) { if (floydWarshall::dist[i][path[l-1]] + orig[path[l-1]][path[l]] + floydWarshall::dist[path[l]][k] != @@ -52,7 +52,7 @@ void stress_test(int LIM) { for (int i = 0; i < n; i++) { auto got = floydWarshall::dist[i]; auto expected = bellmannFord(n, edges, i); - + if (got != expected) cerr << "error" << FAIL; queries += n; } diff --git a/test/graph/havelHakimi.cpp b/test/graph/havelHakimi.cpp index f0b6fd9..0752b85 100644 --- a/test/graph/havelHakimi.cpp +++ b/test/graph/havelHakimi.cpp @@ -13,11 +13,11 @@ void stress_test() { for (int i = 0; i < n; i++) expected[i] = g.deg(i); auto res = havelHakimi(expected); - if (sz(res) != n) cerr << "error: wrong number of nodes" << FAIL; + if (ssize(res) != n) cerr << "error: wrong number of nodes" << FAIL; vector<vector<int>> rev(n); vector<int> got(n); for (int i = 0; i < n; i++) { - got[i] = sz(res[i]); + got[i] = ssize(res[i]); for (int j : res[i]) { if (j < 0 || j >= n) cerr << "error: invalid edge" << FAIL; rev[j].push_back(i); @@ -25,11 +25,11 @@ void stress_test() { } for (int i = 0; i < n; i++) { - sort(all(res[i])); - sort(all(rev[i])); + ranges::sort(res[i]); + ranges::sort(rev[i]); if (res[i] != rev[i]) cerr << "error: graph is directed" << FAIL; for (int j : res[i]) if (j == i) cerr << "error: graph has loop" << FAIL; - for (int j = 1; j < sz(res[i]); j++) { + for (int j = 1; j < ssize(res[i]); j++) { if (res[i][j] == res[i][j-1]) cerr << "error: multiedge" << FAIL; } } @@ -54,7 +54,7 @@ void performance_test() { auto res = havelHakimi(expected); t.stop(); hash_t hash = 0; - for (auto& v : res) hash += sz(v); + for (auto& v : res) hash += ssize(v); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/hopcroftKarp.cpp b/test/graph/hopcroftKarp.cpp index a6306b6..c446c99 100644 --- a/test/graph/hopcroftKarp.cpp +++ b/test/graph/hopcroftKarp.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace kuhn { -#include <graph/maxCarBiMatch.cpp> +#include <graph/kuhn.cpp> } namespace hk { #include <graph/hopcroftKarp.cpp> diff --git a/test/graph/kruskal.cpp b/test/graph/kruskal.cpp index d80376f..157a2f4 100644 --- a/test/graph/kruskal.cpp +++ b/test/graph/kruskal.cpp @@ -1,22 +1,19 @@ #include "../util.h" #include <datastructures/unionFind.cpp> -struct edge { +#define Edge Edge_ // we have a struct named Edge in util.h + +struct Edge { int from, to; ll cost; - bool operator<(const edge& o) const { + bool operator<(const Edge& o) const { return cost > o.cost; } }; -ll kruskal(vector<edge>& edges, int n) { - init(n); - #define Edge edge - #include <graph/kruskal.cpp> - #undef Edge - return cost; -} -ll prim(vector<edge>& edges, int n) { +#include <graph/kruskal.cpp> + +ll prim(vector<Edge>& edges, int n) { vector<vector<pair<ll, int>>> adj(n); for (auto [a, b, d] : edges) { adj[a].emplace_back(d, b); @@ -51,13 +48,14 @@ void stress_test() { Graph<NoData> g(n); g.erdosRenyi(m); - vector<edge> edges; + vector<Edge> edges; g.forEdges([&](int a, int b){ ll w = Random::integer<ll>(-1'000'000'000ll, 1'000'000'000ll); edges.push_back({a, b, w}); }); - ll got = kruskal(edges, n); + vector<Edge> mst; + ll got = kruskal(n, edges, mst); ll expected = prim(edges, n); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; @@ -72,14 +70,15 @@ void performance_test() { timer t; Graph<NoData> g(N); g.erdosRenyi(M); - vector<edge> edges; + vector<Edge> edges; g.forEdges([&](int a, int b){ ll w = Random::integer<ll>(-1'000'000'000ll, 1'000'000'000ll); edges.push_back({a, b, w}); }); t.start(); - hash_t hash = kruskal(edges, N); + vector<Edge> mst; + hash_t hash = kruskal(N, edges, mst); t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/graph/maxCarBiMatch.cpp b/test/graph/kuhn.cpp index 6672d30..0a6a9a4 100644 --- a/test/graph/maxCarBiMatch.cpp +++ b/test/graph/kuhn.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace kuhn { -#include <graph/maxCarBiMatch.cpp> +#include <graph/kuhn.cpp> } namespace hk { #include <graph/hopcroftKarp.cpp> diff --git a/test/graph/matching.cpp b/test/graph/matching.cpp index ccd98e6..d737954 100644 --- a/test/graph/matching.cpp +++ b/test/graph/matching.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace tutte { -void gauss(int n, int m); +vector<int> gauss(vector<vector<ll>> &mat); #include <graph/matching.cpp> #include <math/shortModInv.cpp> #include <math/lgsFp.cpp> @@ -15,19 +15,19 @@ void stress_test() { GM blossom(n); srand(Random::rng()); - tutte::adj.assign(n, {}); + vector<vector<int>> adj(n); Graph<NoData> g(n); g.erdosRenyi(m); g.forEdges([&](int a, int b){ - tutte::adj[a].push_back(b); - tutte::adj[b].push_back(a); + adj[a].push_back(b); + adj[b].push_back(a); blossom.adj[a].push_back(b); blossom.adj[b].push_back(a); }); - ll got = tutte::max_matching(); + ll got = tutte::max_matching(adj); ll expected = blossom.match(); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; @@ -43,14 +43,14 @@ void performance_test() { Graph<NoData> g(N); g.erdosRenyi(M); srand(Random::rng()); - tutte::adj.assign(N, {}); + vector<vector<int>> adj(N); g.forEdges([&](int a, int b){ - tutte::adj[a].push_back(b); - tutte::adj[b].push_back(a); + adj[a].push_back(b); + adj[b].push_back(a); }); t.start(); - hash_t hash = tutte::max_matching(); + hash_t hash = tutte::max_matching(adj); t.stop(); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/graph/pushRelabel.cpp b/test/graph/pushRelabel.cpp index 00a73d1..ca50860 100644 --- a/test/graph/pushRelabel.cpp +++ b/test/graph/pushRelabel.cpp @@ -1,6 +1,6 @@ #include "../util.h" -namespace dinic { -#include <graph/dinicScaling.cpp> +namespace dinitz { +#include <graph/dinitzScaling.cpp> } namespace pushRelabel { @@ -13,20 +13,20 @@ void stress_test() { int n = Random::integer<int>(2, 30); int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); - dinic::adj.assign(n, {}); + dinitz::adj.assign(n, {}); pushRelabel::adj.assign(n, {}); Graph<NoData, true> g(n); g.erdosRenyi(m); g.forEdges([](int a, int b){ ll w = Random::integer<ll>(1, 1'000'000'000'000ll); - dinic::addEdge(a, b, w); + dinitz::addEdge(a, b, w); pushRelabel::addEdge(a, b, w); }); ll got = pushRelabel::maxFlow(0, n - 1); - ll expected = dinic::maxFlow(0, n - 1); - + ll expected = dinitz::maxFlow(0, n - 1); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp index 6fc2f4d..c7c4608 100644 --- a/test/graph/reroot.cpp +++ b/test/graph/reroot.cpp @@ -47,7 +47,7 @@ void performance_test() { t.start(); Reroot re; auto ans = re.solve(); - hash = accumulate(all(ans), 0LL); + hash = accumulate(begin(ans), end(ans), 0LL); t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp index 7c1261f..ebd3af0 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -9,11 +9,11 @@ void stress_test() { Graph<NoData, true> g(n); g.erdosRenyi(m); - adj.assign(n, {}); - g.forEdges([](int a, int b){ + vector<vector<int>> adj(n); + g.forEdges([&](int a, int b){ adj[a].push_back(b); }); - scc(); + SCC scc(adj); auto reach = [&](int a) -> vector<bool> { vector<bool> seen(n); @@ -28,12 +28,21 @@ void stress_test() { return seen; }; + vector<int> seen(n); + for (int i = 0; i < ssize(scc.sccs); i++) { + for (int v: scc.sccs[i]) { + if (scc.idx[v] != i) cerr << v << " is in scc " << i << ", but idx[" << v << "] = " << scc.idx[v] << FAIL; + seen[v]++; + } + } + for (int a = 0; a < n; a++) { + if (seen[a] != 1) cerr << a << " occurs " << seen[a] << " times in sccs" << FAIL; vector<bool> reacha = reach(a); for (int b = 0; b < n; b++) { - if (idx[a] == idx[b]) { + if (scc.idx[a] == scc.idx[b]) { if (!reacha[b]) cerr << a << " and " << b << " should be in different SCCs" << FAIL; - } else if (idx[a] < idx[b]) { + } else if (scc.idx[a] < scc.idx[b]) { if (reacha[b]) cerr << a << " should come before " << b << " in topological order" << FAIL; } } @@ -49,16 +58,16 @@ void performance_test() { timer t; Graph<NoData, true> g(N); g.erdosRenyi(M); - adj.assign(N, {}); - g.forEdges([](int a, int b){ + vector<vector<int>> adj(N); + g.forEdges([&](int a, int b){ adj[a].push_back(b); }); t.start(); - scc(); + SCC scc(adj); t.stop(); hash_t hash = 0; - for (int x : idx) hash += x; + for (int x : scc.idx) hash += x; if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/stoerWagner.cpp b/test/graph/stoerWagner.cpp index cc01a7d..3b67aac 100644 --- a/test/graph/stoerWagner.cpp +++ b/test/graph/stoerWagner.cpp @@ -13,7 +13,7 @@ namespace pushRelabel { #include <graph/pushRelabel.cpp> ll minCut() { ll res = INF; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { for (int j = 0; j < i; j++) { if (i == j) continue; res = min(res, maxFlow(i, j)); @@ -48,7 +48,7 @@ void stress_test() { ll got = stoerWagner::stoer_wagner(); ll expected = pushRelabel::minCut(); - + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } diff --git a/test/graph/treeIsomorphism.cpp b/test/graph/treeIsomorphism.cpp index e5fd817..1594016 100644 --- a/test/graph/treeIsomorphism.cpp +++ b/test/graph/treeIsomorphism.cpp @@ -45,7 +45,7 @@ void stress_test_eq() { void test_tiny() { vector<int> expected = {1,1,1,1,2,3,6,11,23}; //#A000055 - for (int i = 1; i < sz(expected); i++) { + for (int i = 1; i < ssize(expected); i++) { set<pair<int, int>> got; tree t(i); @@ -63,9 +63,9 @@ void test_tiny() { got.insert(t.treeLabel()); } - if (sz(got) != expected[i]) cerr << i << ", got: " << sz(got) << ", expected: " << expected[i] << FAIL; + if (ssize(got) != expected[i]) cerr << i << ", got: " << ssize(got) << ", expected: " << expected[i] << FAIL; } - cerr << "tested tiny: " << sz(expected) << endl; + cerr << "tested tiny: " << ssize(expected) << endl; } void stress_test_neq() { @@ -110,7 +110,7 @@ void performance_test() { tt.adj[b].push_back(a); }); - t.start(); + t.start(); auto [gotA, gotB] = tt.treeLabel(); t.stop(); hash_t hash = gotA + gotB; diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp index af57619..556ba7b 100644 --- a/test/graph/virtualTree.cpp +++ b/test/graph/virtualTree.cpp @@ -21,7 +21,7 @@ int lca(int u, int v) { } void init(vector<vector<int>>& adj) { - int n = (int)sz(adj); + int n = (int)ssize(adj); d.assign(n, 0); in = par = out = d; int counter = 0; @@ -44,7 +44,7 @@ void stress_test() { vector<int> ind = Random::distinct(Random::integer(1, n+1), 0, n); auto [idk, tree] = virtualTree(ind); vector<pair<int, int>> edges; - for (int i=0; i<sz(idk); i++) for (int v : tree[i]) { + for (int i=0; i<ssize(idk); i++) for (int v : tree[i]) { edges.emplace_back(idk[i], idk[v]); } @@ -60,7 +60,7 @@ void stress_test() { }; dfs(dfs, 0, -1, -1); - sort(all(edges)), sort(all(edges2)); + ranges::sort(edges), ranges::sort(edges2); if (edges != edges2) cerr << "WA edge list does not match" << FAIL; } cerr << "tested random 50'000 tests" << endl; @@ -83,7 +83,7 @@ void performance_test() { ll hash = 0; t.start(); auto [idk, tree] = virtualTree(ind); - hash = accumulate(all(idk), 0LL); + hash = accumulate(begin(idk), end(idk), 0LL); t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/math/berlekampMassey.cpp b/test/math/berlekampMassey.cpp index c7e83fc..93832b0 100644 --- a/test/math/berlekampMassey.cpp +++ b/test/math/berlekampMassey.cpp @@ -12,10 +12,10 @@ struct RandomRecurence { } ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); @@ -60,7 +60,7 @@ void performance_test() { cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } - + int main() { stress_test(); if (!sanitize) performance_test(); diff --git a/test/math/bigint.cpp b/test/math/bigint.cpp index 53e18dd..2d75343 100644 --- a/test/math/bigint.cpp +++ b/test/math/bigint.cpp @@ -9,7 +9,7 @@ struct modInt { stringstream a; a << x; string b = a.str(); - for (ll i = b[0] == '-' ? 1 : 0; i < sz(b); i++) { + for (ll i = b[0] == '-' ? 1 : 0; i < ssize(b); i++) { value *= 10; value += b[i] - '0'; value %= MOD; @@ -115,7 +115,7 @@ void stress_test(int LIM) { } cerr << "tested random queries: " << queries << endl; } - + int main() { stress_test(100); if (!sanitize) stress_test(1000); diff --git a/test/math/binomial0.cpp b/test/math/binomial0.cpp index 00c04d4..17a5f91 100644 --- a/test/math/binomial0.cpp +++ b/test/math/binomial0.cpp @@ -4,17 +4,16 @@ constexpr ll mod = 1'394'633'899; #include <math/binomial0.cpp> - void stress_test() { vector<ll> last = {1}; ll queries = 0; for (ll i = 0; i < 10'000; i++) { for (ll j = 0; j <= i; j++) { - ll got = calc_binom(i, j); + ll got = binom(i, j); ll expected = last[j]; - if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial1.cpp b/test/math/binomial1.cpp index f6fe20b..3a7b291 100644 --- a/test/math/binomial1.cpp +++ b/test/math/binomial1.cpp @@ -7,11 +7,11 @@ void stress_test() { ll queries = 0; for (ll i = 0; i <= 61; i++) { for (ll j = 0; j <= i; j++) { - ll got = calc_binom(i, j); + ll got = binom(i, j); ll expected = last[j]; - if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial2.cpp b/test/math/binomial2.cpp index b55c8af..ce6a07c 100644 --- a/test/math/binomial2.cpp +++ b/test/math/binomial2.cpp @@ -8,11 +8,11 @@ void stress_test() { ll queries = 0; for (ll i = 0; i <= 1000; i++) { for (ll j = 0; j <= i; j++) { - ll got = calc_binom(i, j); + ll got = binom(i, j); ll expected = last[j]; - if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial3.cpp b/test/math/binomial3.cpp index 4a99689..eaca24e 100644 --- a/test/math/binomial3.cpp +++ b/test/math/binomial3.cpp @@ -11,11 +11,11 @@ void stress_test() { ll queries = 0; for (ll i = 0; i < mod; i++) { for (ll j = 0; j <= i; j++) { - ll got = calc_binom(i, j, mod); + ll got = binom(i, j, mod); ll expected = last[j]; - if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp index 09480b1..2ba3525 100644 --- a/test/math/cycleDetection.cpp +++ b/test/math/cycleDetection.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/cycleDetection.cpp> pair<ll, ll> naive(ll x0, function<ll(ll)> f) { diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp index 167aa62..21a5736 100644 --- a/test/math/gauss.cpp +++ b/test/math/gauss.cpp @@ -7,10 +7,10 @@ vector<vector<double>> mat; #include <math/gauss.cpp> vector<vector<double>> inverseMat(const vector<vector<double>>& m) { - int n = sz(m); + int n = ssize(m); mat = m; for (int i = 0; i < n; i++) { - if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + if (ssize(mat[i]) != n) cerr << "error: no square matrix" << FAIL; mat[i].resize(2*n); mat[i][n+i] = 1; } @@ -27,10 +27,10 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) { } vector<vector<double>> mul(const vector<vector<double>>& a, const vector<vector<double>>& b) { - int n = sz(a); - int m = sz(b[0]); - int x = sz(b); - if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + int n = ssize(a); + int m = ssize(b[0]); + int x = ssize(b); + if (ssize(a[0]) != ssize(b)) cerr << "error: wrong dimensions" << FAIL; vector<vector<double>> res(n, vector<double>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { @@ -48,21 +48,21 @@ void test_tiny() { {0, 5, 6, 7}, {0, 0, 8, 9}, }; - if (gauss(sz(mat)) != UNIQUE) cerr << "error: 1" << FAIL; + if (gauss(ssize(mat)) != UNIQUE) cerr << "error: 1" << FAIL; mat = { {-1, 1, 0, -1}, { 2, 6, 0, 10}, { 1, -2, 0, 0}, }; - if (gauss(sz(mat)) != MULTIPLE) cerr << "error: 2" << FAIL; + if (gauss(ssize(mat)) != MULTIPLE) cerr << "error: 2" << FAIL; mat = { {-1, 1, 0, -1}, { 2, 6, 0, 10}, { 1, -2, 0, 1}, }; - if (gauss(sz(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL; + if (gauss(ssize(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL; } void stress_test_inv() { diff --git a/test/math/inversions.cpp b/test/math/inversions.cpp index 42ab343..86d87d0 100644 --- a/test/math/inversions.cpp +++ b/test/math/inversions.cpp @@ -1,10 +1,9 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/inversions.cpp> ll naive(const vector<ll>& v) { ll res = 0; - for (ll i = 0; i < sz(v); i++) { + for (ll i = 0; i < ssize(v); i++) { for (ll j = 0; j < i; j++) { if (v[j] > v[i]) res++; } diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp index 2492af4..ab1c62e 100644 --- a/test/math/inversionsMerge.cpp +++ b/test/math/inversionsMerge.cpp @@ -3,7 +3,7 @@ ll naive(const vector<ll>& v) { ll res = 0; - for (ll i = 0; i < sz(v); i++) { + for (ll i = 0; i < ssize(v); i++) { for (ll j = 0; j < i; j++) { if (v[j] > v[i]) res++; } @@ -17,7 +17,7 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> v(n); for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ): - shuffle(all(v), Random::rng); + ranges::shuffle(v, Random::rng); ll expected = naive(v); ll got = mergeSort(v); if (got != expected) { diff --git a/test/math/kthperm.cpp b/test/math/kthperm.cpp index 1bf8db3..ca95699 100644 --- a/test/math/kthperm.cpp +++ b/test/math/kthperm.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/kthperm.cpp> void stress_test(int LIM) { @@ -7,13 +6,13 @@ void stress_test(int LIM) { for (int i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); vector<ll> expected(n); - iota(all(expected), 0); + iota(begin(expected), end(expected), 0); ll k = 0; do { auto got = kthperm(n, k); if (got != expected) cerr << "error" << FAIL; k++; - } while (k < 100 && next_permutation(all(expected))); + } while (k < 100 && ranges::next_permutation(expected).found); queries += n; } cerr << "tested queries: " << queries << endl; diff --git a/test/math/kthperm_permIndex.cpp b/test/math/kthperm_permIndex.cpp index d84524e..5e05c73 100644 --- a/test/math/kthperm_permIndex.cpp +++ b/test/math/kthperm_permIndex.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/kthperm.cpp> #include <math/permIndex.cpp> diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp index 6db586a..d8967a0 100644 --- a/test/math/lgsFp.cpp +++ b/test/math/lgsFp.cpp @@ -1,6 +1,5 @@ #include "../util.h" #include <math/shortModInv.cpp> -vector<vector<ll>> mat; constexpr ll mod = 1'000'000'007; namespace lgs { #include <math/lgsFp.cpp> @@ -8,30 +7,26 @@ namespace lgs { vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) { - int n = sz(m); - mat = m; + int n = ssize(m); + vector<vector<ll>> mat = m; for (int i = 0; i < n; i++) { - if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + if (ssize(mat[i]) != n) cerr << "error: no square matrix" << FAIL; mat[i].resize(2*n); mat[i][n+i] = 1; } - lgs::gauss(sz(mat), sz(mat[0])); - vector<vector<ll>> res(m); + vector<int> pivots = lgs::gauss(mat); for (int i = 0; i < n; i++) { - res[i] = vector<ll>(mat[i].begin() + n, mat[i].end()); - for (int j = 0; j < n; j++) { - if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL; - if (j == i && mat[i][j] != 1) cerr << "error: not full rank?" << FAIL; - } + if (pivots[i] != i) cerr << "error: not full rank?" << FAIL; + mat[i].erase(begin(mat[i]), begin(mat[i]) + n); } - return res; + return mat; } vector<vector<ll>> mul(const vector<vector<ll>>& a, const vector<vector<ll>>& b) { - int n = sz(a); - int m = sz(b[0]); - int x = sz(b); - if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + int n = ssize(a); + int m = ssize(b[0]); + int x = ssize(b); + if (ssize(a[0]) != ssize(b)) cerr << "error: wrong dimensions" << FAIL; vector<vector<ll>> res(n, vector<ll>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { @@ -53,18 +48,17 @@ void test_square() { vector<vector<ll>> m(n); for (auto& v : m) v = Random::integers<ll>(n, 0, mod); - mat = m; - lgs::gauss(sz(mat), sz(mat[0])); + lgs::gauss(m); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { - hash += mat[i][j]; + hash += m[i][j]; } } queries += n; } - cerr << "tested sqaures: " << queries << " (hash: " << hash << ")" << endl;; + cerr << "tested squares: " << queries << " (hash: " << hash << ")" << endl;; } void stress_test_inv() { @@ -82,8 +76,7 @@ void stress_test_inv() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { - if (i == j && prod[i][j] != 1) cerr << "error: not inverted" << FAIL; - if (i != j && prod[i][j] != 0) cerr << "error: not inverted" << FAIL; + if (prod[i][j] != (i == j)) cerr << "error: not inverted" << FAIL; } } @@ -98,15 +91,14 @@ void performance_test() { vector<vector<ll>> m(N); for (auto& v : m) v = Random::integers<ll>(N, 0, mod); - mat = m; t.start(); - lgs::gauss(sz(mat), sz(mat[0])); + lgs::gauss(m); t.stop(); hash_t hash = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { - hash += mat[i][j]; + hash += m[i][j]; } } if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index 977221e..a2ac01d 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -6,16 +6,15 @@ vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { return mulSlow(a, b); } - struct RandomRecurence { vector<ll> f, c, cache; RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearRecurrenceNTT.cpp b/test/math/linearRecurrenceNTT.cpp index ca7e29e..f7615d6 100644 --- a/test/math/linearRecurrenceNTT.cpp +++ b/test/math/linearRecurrenceNTT.cpp @@ -12,10 +12,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearRecurrenceOld.cpp b/test/math/linearRecurrenceOld.cpp index 6435d5a..b3d1611 100644 --- a/test/math/linearRecurrenceOld.cpp +++ b/test/math/linearRecurrenceOld.cpp @@ -6,10 +6,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearSieve.cpp b/test/math/linearSieve.cpp index fbed4b5..1a5286f 100644 --- a/test/math/linearSieve.cpp +++ b/test/math/linearSieve.cpp @@ -57,7 +57,7 @@ void performance_test() { timer t; t.start(); sieve(); - hash_t hash = sz(primes); + hash_t hash = ssize(primes); t.stop(); if (!sanitize) { if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/math/longestIncreasingSubsequence.cpp b/test/math/longestIncreasingSubsequence.cpp index d08cf57..5bc3936 100644 --- a/test/math/longestIncreasingSubsequence.cpp +++ b/test/math/longestIncreasingSubsequence.cpp @@ -9,7 +9,7 @@ constexpr ll INF = LL::INF; template<bool STRICT> bool isLis(const vector<ll>& a, const vector<int>& lis) { - for (int i = 1; i < sz(lis); i++) { + for (int i = 1; i < ssize(lis); i++) { if (lis[i-1] >= lis[i]) return false; if (a[lis[i-1]] > a[lis[i]]) return false; if (STRICT && a[lis[i-1]] == a[lis[i]]) return false; @@ -20,12 +20,12 @@ bool isLis(const vector<ll>& a, const vector<int>& lis) { template<bool STRICT> vector<int> naive(const vector<ll>& a) { vector<int> res; - for (ll i = 1; i < (1ll << sz(a)); i++) { + for (ll i = 1; i < (1ll << ssize(a)); i++) { vector<int> tmp; - for (ll j = 0; j < sz(a); j++) { + for (ll j = 0; j < ssize(a); j++) { if (((i >> j) & 1) != 0) tmp.push_back(j); } - if (sz(tmp) >= sz(res) && isLis<STRICT>(a, tmp)) res = tmp; + if (ssize(tmp) >= ssize(res) && isLis<STRICT>(a, tmp)) res = tmp; } return res; } @@ -56,10 +56,9 @@ void performance_test() { timer t; auto a = Random::integers<ll>(N, -10'000, 10'000); auto b = Random::integers<ll>(N, -10'000, 10'000); - sort(all(b)); + ranges::sort(b); auto c = Random::integers<ll>(N, -10'000, 10'000); - sort(all(c)); - reverse(all(c)); + ranges::sort(c | views::reverse); hash_t hash = 0; t.start(); hash += lis(a).size(); diff --git a/test/math/matrixPower.cpp b/test/math/matrixPower.cpp index b1d6783..083dded 100644 --- a/test/math/matrixPower.cpp +++ b/test/math/matrixPower.cpp @@ -7,15 +7,15 @@ struct mat { mat(int dim = 0, int diag = 1) : m(dim, vector<ll>(dim)) { for (int i = 0; i < dim; i++) m[i][i] = diag; } - mat(const vector<ll> c) : m(sz(c), vector<ll>(sz(c))) { + mat(const vector<ll> c) : m(ssize(c), vector<ll>(ssize(c))) { m[0] = c; - for (ll i = 1; i < sz(c); i++) { + for (ll i = 1; i < ssize(c); i++) { m[i][i-1] = 1; } } mat operator*(const mat& o) const { - int dim = sz(m); + int dim = ssize(m); mat res(dim, 0); for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { @@ -29,7 +29,7 @@ struct mat { } vector<ll> operator*(const vector<ll>& o) const { - int dim = sz(m); + int dim = ssize(m); vector<ll> res(dim); for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { @@ -48,10 +48,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); @@ -67,13 +67,13 @@ void stress_test() { RandomRecurence f(n); precalc(mat(f.c)); auto tmp = f.f; - reverse(all(tmp)); + ranges::reverse(tmp); for (int j = 0; j < 100; j++) { ll k = Random::integer<ll>(0, 1000); vector<ll> got = calc(k, tmp); - vector<ll> expected(sz(f.f)); + vector<ll> expected(ssize(f.f)); for (ll l = 0; l < n; l++) expected[n - 1 - l] = f(k + l); if (got != expected) cerr << "error" << FAIL; @@ -89,7 +89,7 @@ void performance_test() { timer t; RandomRecurence f(N); auto tmp = f.f; - reverse(all(tmp)); + ranges::reverse(tmp); t.start(); precalc(mat(f.c)); diff --git a/test/math/millerRabin.base32.cpp b/test/math/millerRabin.base32.cpp index 069f125..e9a4b57 100644 --- a/test/math/millerRabin.base32.cpp +++ b/test/math/millerRabin.base32.cpp @@ -95,7 +95,7 @@ void extra_tests() { t.start(); auto got = isPrime(x); t.stop(); - bool expected = sz(factors) == 1 && factors.begin()->second == 1; + bool expected = ssize(factors) == 1 && factors.begin()->second == 1; if (got != expected) cerr << "error: " << x << FAIL; } if (t.time > 10) cerr << "too slow" << FAIL; diff --git a/test/math/millerRabin.cpp b/test/math/millerRabin.cpp index 18fad40..e7feba1 100644 --- a/test/math/millerRabin.cpp +++ b/test/math/millerRabin.cpp @@ -87,7 +87,7 @@ void extra_tests() { t.start(); auto got = isPrime(x); t.stop(); - bool expected = sz(factors) == 1 && factors.begin()->second == 1; + bool expected = ssize(factors) == 1 && factors.begin()->second == 1; if (got != expected) cerr << "error: " << x << FAIL; } if (t.time > 10) cerr << "too slow" << FAIL; diff --git a/test/math/modExp.cpp b/test/math/modExp.cpp deleted file mode 100644 index 4d2b4b2..0000000 --- a/test/math/modExp.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include "../util.h" -#include <math/modExp.cpp> - -void stress_test() { - ll queries = 0; - for (ll i = 0; i < 10'000; i++) { - int a = Random::integer<int>(1, 100); - int n = Random::integer<int>(2, 100); - ll expected = 1; - ll k = 0; - do { - auto got = powMod(a, k, n); - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - k++; - expected = (expected * a) % n; - } while (k < 100); - queries += n; - } - cerr << "tested queries: " << queries << endl; -} - -constexpr int N = 1'000'000; -void performance_test() { - timer t; - hash_t hash = 0; - for (int operations = 0; operations < N; operations++) { - ll a = Random::integer<ll>(0, 1'000'000'000); - ll b = Random::integer<ll>(0, 1'000'000'000); - ll n = Random::integer<ll>(2, 1'000'000'000); - t.start(); - hash += powMod(a, b, n); - t.stop(); - } - if (t.time > 750) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; -} - -int main() { - stress_test(); - if (!sanitize) performance_test(); -} - diff --git a/test/math/permIndex.cpp b/test/math/permIndex.cpp index 8dcfd6b..2f19985 100644 --- a/test/math/permIndex.cpp +++ b/test/math/permIndex.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/permIndex.cpp> void stress_test(int LIM) { @@ -7,13 +6,13 @@ void stress_test(int LIM) { for (int i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); vector<ll> cur(n); - iota(all(cur), 0); + iota(begin(cur), end(cur), 0); ll expected = 0; do { auto got = permIndex(cur); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; expected++; - } while (expected < 100 && next_permutation(all(cur))); + } while (expected < 100 && ranges::next_permutation(cur).found); queries += n; } cerr << "tested queries: " << queries << endl; @@ -23,7 +22,7 @@ constexpr int N = 500'000; void performance_test() { timer t; vector<ll> cur(N); - iota(all(cur), 0); + iota(begin(cur), end(cur), 0); reverse(cur.end() - 10, cur.end()); t.start(); auto hash = permIndex(cur); diff --git a/test/math/polynomial.cpp b/test/math/polynomial.cpp index f4a9486..adf3773 100644 --- a/test/math/polynomial.cpp +++ b/test/math/polynomial.cpp @@ -11,7 +11,7 @@ poly randomPoly(int deg) { ll eval(const vector<ll>& p, ll x) { ll res = 0; - for (ll i = 0, j = 1; i < sz(p); i++, j = (j * x) % mod) { + for (ll i = 0, j = 1; i < ssize(p); i++, j = (j * x) % mod) { res += j * p[i]; res %= mod; } @@ -50,7 +50,7 @@ void test_add() { auto c = a; c += b; - if (sz(c) > sz(a) && sz(c) > sz(b)) cerr << "error: wrong degree" << FAIL; + if (ssize(c) > ssize(a) && ssize(c) > ssize(b)) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + m + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -74,7 +74,7 @@ void test_mul() { auto b = randomPoly(m); auto c = a * b; - if (sz(c) > sz(a) + sz(b) - 1) cerr << "error: wrong degree" << FAIL; + if (ssize(c) > ssize(a) + ssize(b) - 1) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + m + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -97,8 +97,8 @@ void test_shift() { auto a = randomPoly(n); auto b = a << m; - if (sz(b) > sz(a)) cerr << sz(a) << " " << sz(b) << endl; - if (sz(b) > sz(a)) cerr << "error: wrong degree" << FAIL; + if (ssize(b) > ssize(a)) cerr << ssize(a) << " " << ssize(b) << endl; + if (ssize(b) > ssize(a)) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -126,8 +126,8 @@ void test_divmod() { auto b = randomPoly(m); auto [div, rem] = a.divmod(b); - if (sz(rem) > sz(b)) cerr << "error: wrong degree (rem)" << FAIL; - if (sz(div) > 1 + max<ll>(0, sz(a) - sz(b))) cerr << "error: wrong degree (div)" << FAIL; + if (ssize(rem) > ssize(b)) cerr << "error: wrong degree (rem)" << FAIL; + if (ssize(div) > 1 + max<ll>(0, ssize(a) - ssize(b))) cerr << "error: wrong degree (div)" << FAIL; for (int i = 0; i <= n + m; i++) { ll x = Random::integer<ll>(0, mod); @@ -142,7 +142,7 @@ void test_divmod() { } cerr << "tested divmod: " << queries << endl; } - + int main() { test_eval(); test_add(); diff --git a/test/math/primeSieve.cpp b/test/math/primeSieve.cpp index a675f6a..52570e2 100644 --- a/test/math/primeSieve.cpp +++ b/test/math/primeSieve.cpp @@ -18,7 +18,7 @@ void stress_test() { if (got) found.push_back(i); queries++; } - primes.resize(sz(found)); + primes.resize(ssize(found)); if (primes != found) cerr << "error: primes" << FAIL; for (int i = 0; i < 1'000'000; i++) { ll x = Random::integer<ll>(2, N); @@ -34,7 +34,7 @@ void performance_test() { timer t; t.start(); primeSieve(); - hash_t hash = sz(primes); + hash_t hash = ssize(primes); t.stop(); if (!sanitize) { if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/math/primitiveRoot.cpp b/test/math/primitiveRoot.cpp index cd0b388..6ad7429 100644 --- a/test/math/primitiveRoot.cpp +++ b/test/math/primitiveRoot.cpp @@ -63,7 +63,7 @@ void stress_test2() { map<ll, int> facts; factor(x, facts); if (x % 2 == 0) facts.erase(facts.find(2)); - bool expected = sz(facts) == 1; + bool expected = ssize(facts) == 1; if (x % 4 == 0) expected = false; if (x == 2 || x == 4) expected = true; diff --git a/test/math/shortModInv.cpp b/test/math/shortModInv.cpp index 0e91900..5e74907 100644 --- a/test/math/shortModInv.cpp +++ b/test/math/shortModInv.cpp @@ -7,7 +7,7 @@ void stress_test() { ll n = Random::integer<ll>(2, 1'000'000'000); ll x = 0; do { - x = Random::integer<ll>(0, n); + x = Random::integer<ll>(0, 1'000'000'000); } while (gcd(x, n) != 1); ll y = multInv(x, n); ll got = (x*y) % n; diff --git a/test/math/transforms/fft.cpp b/test/math/transforms/fft.cpp index 35f7e15..aa7ddd2 100644 --- a/test/math/transforms/fft.cpp +++ b/test/math/transforms/fft.cpp @@ -2,14 +2,14 @@ #include <math/transforms/fft.cpp> vector<cplx> to_cplx(const vector<ll>& in) { - vector<cplx> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = in[i]; + vector<cplx> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = in[i]; return res; } vector<ll> from_cplx(const vector<cplx>& in) { - vector<ll> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + vector<ll> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = llround(real(in[i])); return res; } diff --git a/test/math/transforms/fftMul.cpp b/test/math/transforms/fftMul.cpp index 72fd4d8..38e7c73 100644 --- a/test/math/transforms/fftMul.cpp +++ b/test/math/transforms/fftMul.cpp @@ -5,21 +5,21 @@ #include <math/transforms/fftMul.cpp> vector<ll> from_cplx(const vector<cplx>& in) { - vector<ll> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + vector<ll> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = llround(real(in[i])); return res; } vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyBitwise.cpp b/test/math/transforms/multiplyBitwise.cpp index e89ba4e..f460204 100644 --- a/test/math/transforms/multiplyBitwise.cpp +++ b/test/math/transforms/multiplyBitwise.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) <= i && sz(b) <= i) { + if (ssize(a) <= i && ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i&j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyFFT.cpp b/test/math/transforms/multiplyFFT.cpp index a54020c..f11ec45 100644 --- a/test/math/transforms/multiplyFFT.cpp +++ b/test/math/transforms/multiplyFFT.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyNTT.cpp b/test/math/transforms/multiplyNTT.cpp index 90c606a..48a1aa3 100644 --- a/test/math/transforms/multiplyNTT.cpp +++ b/test/math/transforms/multiplyNTT.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; res[i+j] %= mod; } diff --git a/test/math/transforms/seriesOperations.cpp b/test/math/transforms/seriesOperations.cpp index 29c91c7..1242537 100644 --- a/test/math/transforms/seriesOperations.cpp +++ b/test/math/transforms/seriesOperations.cpp @@ -24,7 +24,7 @@ namespace reference {//checked against yosupo } vector<ll> poly_deriv(vector<ll> a){ - for(int i = 0; i < sz(a)-1; i++) + for(int i = 0; i < ssize(a)-1; i++) a[i] = a[i+1] * (i+1) % mod; a.pop_back(); return a; @@ -32,8 +32,8 @@ namespace reference {//checked against yosupo vector<ll> poly_integr(vector<ll> a){ if(a.empty()) return {0}; - a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); - for(int i = sz(a)-2; i > 0; i--) + a.push_back(a.back() * powMod(ssize(a), mod-2, mod) % mod); + for(int i = ssize(a)-2; i > 0; i--) a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; a[0] = 0; return a; @@ -51,7 +51,7 @@ namespace reference {//checked against yosupo for(int len = 1; len < n; len *= 2){ vector<ll> p = poly_log(q, 2*len); for(int i = 0; i < 2*len; i++) - p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; + p[i] = (mod - p[i] + (i < ssize(a) ? a[i] : 0)) % mod; vector<ll> q2 = q; q2.resize(2*len); ntt(p), ntt(q2); diff --git a/test/missing.ignore b/test/missing.ignore new file mode 100644 index 0000000..c5f97bc --- /dev/null +++ b/test/missing.ignore @@ -0,0 +1,7 @@ +datastructures/pbds.cpp +other/pragmas.cpp +other/stuff.cpp +other/timed.cpp +tests/gcc5bug.cpp +tests/precision.cpp +tests/whitespace.cpp diff --git a/test/other/bitOps.cpp b/test/other/bitOps.cpp index 707c3f0..adaa49a 100644 --- a/test/other/bitOps.cpp +++ b/test/other/bitOps.cpp @@ -31,9 +31,7 @@ ll naive(ll x) { bits.push_back(x & 1); x >>= 1; } - reverse(all(bits)); - next_permutation(all(bits)); - reverse(all(bits)); + ranges::next_permutation(bits | views::reverse); x = 0; for (ll i = 0, j = 1; i < 63; i++, j <<= 1) { if (bits[i] != 0) x |= j; @@ -56,4 +54,4 @@ void test_nextPerm() { int main() { test_subsets(); test_nextPerm(); -}
\ No newline at end of file +} diff --git a/test/other/josephus2.cpp b/test/other/josephus2.cpp index 21154a1..074b481 100644 --- a/test/other/josephus2.cpp +++ b/test/other/josephus2.cpp @@ -4,8 +4,8 @@ template<ll O> ll naive(ll n, ll k) { vector<ll> state(n); - iota(all(state), O); - for (ll i = k-1; state.size() > 1; i = (i + k - 1) % sz(state)) { + iota(begin(state), end(state), O); + for (ll i = k-1; state.size() > 1; i = (i + k - 1) % ssize(state)) { state.erase(state.begin() + i); } return state[0]; @@ -15,7 +15,7 @@ void stress_test() { ll tests = 0; for (ll i = 1; i < 2'000; i++) { auto got = rotateLeft(i); - auto expected = naive<1>(i, 2); + auto expected = naive<0>(i, 2); if (got != expected) cerr << "error: " << i << FAIL; tests++; } diff --git a/test/other/josephusK.cpp b/test/other/josephusK.cpp index b6680b8..dab291b 100644 --- a/test/other/josephusK.cpp +++ b/test/other/josephusK.cpp @@ -5,8 +5,8 @@ template<ll O> ll naive(ll n, ll k) { vector<ll> state(n); - iota(all(state), O); - for (ll i = k-1; state.size() > 1; i = (i + k - 1) % sz(state)) { + iota(begin(state), end(state), O); + for (ll i = k-1; state.size() > 1; i = (i + k - 1) % ssize(state)) { state.erase(state.begin() + i); } return state[0]; diff --git a/test/other/pbs.cpp b/test/other/pbs.cpp index 4fa4470..4a8da2e 100644 --- a/test/other/pbs.cpp +++ b/test/other/pbs.cpp @@ -49,7 +49,7 @@ void stress_test() { for (int i=1; i<n; i++) { edges.emplace_back(Random::integer(0, i), i); } - shuffle(all(edges), Random::rng); + ranges::shuffle(edges, Random::rng); queries.clear(); for (int i=0; i<Q; i++) { auto x = Random::distinct(2, n); @@ -80,7 +80,7 @@ void performance_test() { for (int i=1; i<n; i++) { edges.emplace_back(Random::integer(0, i), i); } - shuffle(all(edges), Random::rng); + ranges::shuffle(edges, Random::rng); queries.clear(); for (int i=0; i<Q; i++) { auto x = Random::distinct(2, n); @@ -91,7 +91,7 @@ void performance_test() { t.start(); vector<int> ans = pbs(Q, MAX_OPERATIONS); t.stop(); - ll hash = accumulate(all(ans), 0LL); + ll hash = accumulate(begin(ans), end(ans), 0LL); if (t.time > 900) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/other/sos.cpp b/test/other/sos.cpp deleted file mode 100644 index 52b55ed..0000000 --- a/test/other/sos.cpp +++ /dev/null @@ -1,50 +0,0 @@ -#include "../util.h" - -vector<ll> sos(const vector<ll>& in) { - #include <other/sos.cpp> - return res; -} - -vector<ll> naive(const vector<ll>& in) { - vector<ll> res(sz(in)); - for (ll i = 0; i < sz(in); i++) { - for (ll j = 0; j <= i; j++) { - if ((i | j) == i) { - res[i] += in[j]; - } - } - } - return res; -} - -void stress_test() { - ll tests = 0; - for (ll i = 0; i < 1000; i++) { - int n = Random::integer<int>(1, 100); - auto in = Random::integers<ll>(n, -1000, 1000); - auto got = sos(in); - auto expected = naive(in); - if (got != expected) cerr << "error: " << i << FAIL; - tests += n; - } - cerr << "tested random queries: " << tests << endl; -} - -constexpr int N = 10'000'000; -void performance_test() { - timer t; - auto in = Random::integers<ll>(N, -1000, 1000); - t.start(); - auto res = sos(in); - t.stop(); - hash_t hash = 0; - for (ll x : res) hash += x; - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; -} - -int main() { - stress_test(); - if (!sanitize) performance_test(); -} - diff --git a/test/string/deBruijn.cpp b/test/string/deBruijn.cpp index 09ba611..6bbbad9 100644 --- a/test/string/deBruijn.cpp +++ b/test/string/deBruijn.cpp @@ -5,13 +5,13 @@ bool isDeBruijn(string s, int n, int k) { ll expected = 1; for (ll i = 0; i < n; i++) expected *= k; - if (expected != sz(s)) return false; + if (expected != ssize(s)) return false; s += s; set<string_view> seen; - for (ll i = 0; 2*i < sz(s); i++) { + for (ll i = 0; 2*i < ssize(s); i++) { seen.insert(string_view(s).substr(i, n)); } - return sz(seen) == expected; + return ssize(seen) == expected; } void stress_test() { @@ -21,7 +21,7 @@ void stress_test() { auto [l, r] = Random::pair<char>('b', 'f'); auto got = deBruijn(n, l, r); if (!isDeBruijn(got, n, r - l + 1)) cerr << "error" << FAIL; - queries += sz(got); + queries += ssize(got); } cerr << "tested random queries: " << queries << endl; } @@ -32,7 +32,7 @@ void performance_test() { t.start(); auto res = deBruijn(N, '0', '1'); t.stop(); - hash_t hash = sz(res); + hash_t hash = ssize(res); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/duval.cpp b/test/string/duval.cpp index 0475386..88e2fb7 100644 --- a/test/string/duval.cpp +++ b/test/string/duval.cpp @@ -6,8 +6,8 @@ constexpr int N = 20'000'000; bool isLyndon(string_view s) { string t = string(s) + string(s); - for (ll i = 1; i < sz(s); i++) { - if (s >= t.substr(i, sz(s))) return false; + for (ll i = 1; i < ssize(s); i++) { + if (s >= t.substr(i, ssize(s))) return false; } return !s.empty(); } @@ -21,11 +21,11 @@ void stress_test_duval() { if (got.empty()) cerr << "error: a" << FAIL; if (got.front().first != 0) cerr << "error: b" << FAIL; if (got.back().second != n) cerr << "error: c" << FAIL; - for (int j = 1; j < sz(got); j++) { - if (got[j - 1].second != got[j].first) cerr << "error: d" << FAIL; + for (int j = 1; j < ssize(got); j++) { + if (got[j - 1].second != got[j].first) cerr << "error: d" << FAIL; } for (auto [l, r] : got) { - if (!isLyndon(string_view(s).substr(l, r-l))) cerr << "error: e" << FAIL; + if (!isLyndon(string_view(s).substr(l, r-l))) cerr << "error: e" << FAIL; } queries += n; } @@ -45,7 +45,7 @@ void performance_test_duval() { } int naive(string s) { - ll n = sz(s); + ll n = ssize(s); s += s; int res = 0; for (int i = 0; i < n; i++) { diff --git a/test/string/kmp.cpp b/test/string/kmp.cpp index f70a887..8ebeb64 100644 --- a/test/string/kmp.cpp +++ b/test/string/kmp.cpp @@ -2,8 +2,8 @@ #include <string/kmp.cpp> vector<int> naive(string_view s) { - vector<int> res(sz(s) + 1, -1); - for (int i = 0; i < sz(s); i++) { + vector<int> res(ssize(s) + 1, -1); + for (int i = 0; i < ssize(s); i++) { for (int j = 0; j <= i; j++) if (s.substr(0, j) == s.substr(i-j+1, j)) res[i+1] = j; diff --git a/test/string/longestCommonSubsequence.cpp b/test/string/longestCommonSubsequence.cpp index 68ec71b..8c32d61 100644 --- a/test/string/longestCommonSubsequence.cpp +++ b/test/string/longestCommonSubsequence.cpp @@ -4,19 +4,19 @@ bool isSubstr(string_view s, string_view sub) { int i = 0; for (char c : s) { - if (i < sz(sub) && c == sub[i]) i++; + if (i < ssize(sub) && c == sub[i]) i++; } - return i >= sz(sub); + return i >= ssize(sub); } string naive(string_view s, string_view t) { string res = ""; - for (ll i = 1; i < (1ll << sz(s)); i++) { + for (ll i = 1; i < (1ll << ssize(s)); i++) { string tmp; - for (ll j = 0; j < sz(s); j++) { + for (ll j = 0; j < ssize(s); j++) { if (((i >> j) & 1) != 0) tmp.push_back(s[j]); } - if (sz(tmp) >= sz(res) && isSubstr(t, tmp)) res = tmp; + if (ssize(tmp) >= ssize(res) && isSubstr(t, tmp)) res = tmp; } return res; } @@ -44,7 +44,7 @@ void performance_test() { t.start(); auto res = lcss(a, b); t.stop(); - hash_t hash = sz(res); + hash_t hash = ssize(res); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/lyndon.cpp b/test/string/lyndon.cpp index 905bf8e..154ba66 100644 --- a/test/string/lyndon.cpp +++ b/test/string/lyndon.cpp @@ -3,8 +3,8 @@ bool isLyndon(string_view s) { string t = string(s) + string(s); - for (ll i = 1; i < sz(s); i++) { - if (s >= t.substr(i, sz(s))) return false; + for (ll i = 1; i < ssize(s); i++) { + if (s >= t.substr(i, ssize(s))) return false; } return !s.empty(); } @@ -12,8 +12,8 @@ bool isLyndon(string_view s) { vector<string> naive(ll n, char mi, char ma) { vector<string> res; auto dfs = [&](auto&& self, string pref)->void{ - if (sz(pref) <= n && isLyndon(pref)) res.push_back(pref); - if (sz(pref) >= n) return; + if (ssize(pref) <= n && isLyndon(pref)) res.push_back(pref); + if (ssize(pref) >= n) return; for (char c = mi; c <= ma; c++) { self(self, pref + c); } @@ -39,7 +39,7 @@ void stress_test() { auto got = fast(n, l, r); auto expected = naive(n, l, r); if (got != expected) cerr << "error" << FAIL; - queries += sz(expected); + queries += ssize(expected); } cerr << "tested random queries: " << queries << endl; } @@ -50,7 +50,7 @@ void performance_test() { t.start(); auto res = fast(N, 'a', 'f'); t.stop(); - hash_t hash = sz(res); + hash_t hash = ssize(res); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/manacher.cpp b/test/string/manacher.cpp index bde1c89..ada0486 100644 --- a/test/string/manacher.cpp +++ b/test/string/manacher.cpp @@ -2,16 +2,16 @@ #include <string/manacher.cpp> vector<int> naive(string_view s) { - vector<int> res(2 * sz(s) + 1); - for (int i = 0; i < sz(s); i++) { //odd palindromes + vector<int> res(2 * ssize(s) + 1); + for (int i = 0; i < ssize(s); i++) { //odd palindromes int j = 2*i+1; - while (i+res[j] < sz(s) && i-res[j] >= 0 && s[i-res[j]] == s[i+res[j]]) res[j]++; + while (i+res[j] < ssize(s) && i-res[j] >= 0 && s[i-res[j]] == s[i+res[j]]) res[j]++; res[j]*=2; res[j]--; } - for (int i = 0; i <= sz(s); i++) { //even palindromes + for (int i = 0; i <= ssize(s); i++) { //even palindromes int j = 2*i; - while (i+res[j] < sz(s) && i-res[j]-1 >= 0 && s[i-res[j]-1] == s[i+res[j]]) res[j]++; + while (i+res[j] < ssize(s) && i-res[j]-1 >= 0 && s[i-res[j]-1] == s[i+res[j]]) res[j]++; res[j] *= 2; } return res; diff --git a/test/string/rollingHash.cpp b/test/string/rollingHash.cpp index ba8fc40..d19a153 100644 --- a/test/string/rollingHash.cpp +++ b/test/string/rollingHash.cpp @@ -3,7 +3,7 @@ string thueMorse(ll n) { string res = "a"; - while (sz(res) < n) { + while (ssize(res) < n) { string tmp = res; for (char& c : tmp) c ^= 1; res += tmp; @@ -12,7 +12,7 @@ string thueMorse(ll n) { } auto getHash(const string& s) { - return Hash(s)(0, sz(s)); + return Hash(s)(0, ssize(s)); } void testThueMorse() { @@ -20,13 +20,13 @@ void testThueMorse() { set<string> expected; string s = thueMorse(1000); Hash h(s); - for (int l = 0; l < sz(s); l++) { - for (int r = l + 1; r <= sz(s); r++) { + for (int l = 0; l < ssize(s); l++) { + for (int r = l + 1; r <= ssize(s); r++) { got.insert(h(l, r)); expected.insert(s.substr(l, r - l)); } } - if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL; + if (ssize(got) != ssize(expected)) cerr << "error: thueMorse" << FAIL; cerr << "thueMorse: ok" << endl; } @@ -43,13 +43,13 @@ void testSmall(int depth) { auto dfs = [&](auto&& self, string pref)->void { expected++; got.insert(getHash(pref)); - if(sz(pref) >= depth) return; + if(ssize(pref) >= depth) return; for (char c = 'a'; c <= 'z'; c++) { self(self, pref + c); } }; dfs(dfs, ""); - if (sz(got) != expected) cerr << "error: small" << FAIL; + if (ssize(got) != expected) cerr << "error: small" << FAIL; cerr << "small: ok" << endl; } @@ -58,13 +58,13 @@ void stress_test() { set<string> expected; string s = Random::string(1000, "abc"); Hash h(s); - for (int l = 0; l < sz(s); l++) { - for (int r = l + 1; r <= sz(s); r++) { + for (int l = 0; l < ssize(s); l++) { + for (int r = l + 1; r <= ssize(s); r++) { got.insert(h(l, r)); expected.insert(s.substr(l, r - l)); } } - if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL; + if (ssize(got) != ssize(expected)) cerr << "error: stress test" << FAIL; cerr << "stress test: ok" << endl; } diff --git a/test/string/rollingHashCf.cpp b/test/string/rollingHashCf.cpp index 9acce2d..d0f90aa 100644 --- a/test/string/rollingHashCf.cpp +++ b/test/string/rollingHashCf.cpp @@ -5,7 +5,7 @@ constexpr ll RandomQ = 318LL << 53; string thueMorse(ll n) { string res = "a"; - while (sz(res) < n) { + while (ssize(res) < n) { string tmp = res; for (char& c : tmp) c ^= 1; res += tmp; @@ -14,7 +14,7 @@ string thueMorse(ll n) { } auto getHash(const string& s) { - return Hash(s, RandomQ)(0, sz(s)); + return Hash(s, RandomQ)(0, ssize(s)); } void testThueMorse() { @@ -22,13 +22,13 @@ void testThueMorse() { set<string> expected; string s = thueMorse(1000); Hash h(s, RandomQ); - for (int l = 0; l < sz(s); l++) { - for (int r = l + 1; r <= sz(s); r++) { + for (int l = 0; l < ssize(s); l++) { + for (int r = l + 1; r <= ssize(s); r++) { got.insert(h(l, r)); expected.insert(s.substr(l, r - l)); } } - if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL; + if (ssize(got) != ssize(expected)) cerr << "error: thueMorse" << FAIL; cerr << "thueMorse: ok" << endl; } @@ -45,13 +45,13 @@ void testSmall(int depth) { auto dfs = [&](auto&& self, string pref)->void { expected++; got.insert(getHash(pref)); - if(sz(pref) >= depth) return; + if(ssize(pref) >= depth) return; for (char c = 'a'; c <= 'z'; c++) { self(self, pref + c); } }; dfs(dfs, ""); - if (sz(got) != expected) cerr << "error: small" << FAIL; + if (ssize(got) != expected) cerr << "error: small" << FAIL; cerr << "small: ok" << endl; } @@ -60,13 +60,13 @@ void stress_test() { set<string> expected; string s = Random::string(1000, "abc"); Hash h(s, RandomQ); - for (int l = 0; l < sz(s); l++) { - for (int r = l + 1; r <= sz(s); r++) { + for (int l = 0; l < ssize(s); l++) { + for (int r = l + 1; r <= ssize(s); r++) { got.insert(h(l, r)); expected.insert(s.substr(l, r - l)); } } - if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL; + if (ssize(got) != ssize(expected)) cerr << "error: stress test" << FAIL; cerr << "stress test: ok" << endl; } diff --git a/test/string/suffixArray.cpp b/test/string/suffixArray.cpp index 1314155..37049f6 100644 --- a/test/string/suffixArray.cpp +++ b/test/string/suffixArray.cpp @@ -2,9 +2,9 @@ #include <string/suffixArray.cpp> vector<int> naive(string_view s) { - vector<int> SA(sz(s)); - iota(all(SA), 0); - sort(all(SA), [s](int a, int b){ + vector<int> SA(ssize(s)); + iota(begin(SA), end(SA), 0); + ranges::sort(SA, [s](int a, int b){ return s.substr(a) < s.substr(b); }); return SA; @@ -12,7 +12,7 @@ vector<int> naive(string_view s) { int lcp(string_view s, int x, int y) { int res = 0; - while (x + res < sz(s) && y + res < sz(s) && s[x + res] == s[y + res]) res++; + while (x + res < ssize(s) && y + res < ssize(s) && s[x + res] == s[y + res]) res++; return res; } @@ -50,7 +50,7 @@ void performance_test() { SuffixArray sa(s); t.stop(); hash_t hash = 0; - for (int i = 0; i < sz(sa.SA); i++) hash += i*sa.SA[i]; + for (int i = 0; i < ssize(sa.SA); i++) hash += i*sa.SA[i]; if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/suffixAutomaton.cpp b/test/string/suffixAutomaton.cpp index 146ae11..dacbb83 100644 --- a/test/string/suffixAutomaton.cpp +++ b/test/string/suffixAutomaton.cpp @@ -4,10 +4,10 @@ pair<int, int> naive(string_view s, string_view t) { int pos = 0; int len = 0; - for (int j = 0; j < sz(t); j++) { - for (int i = 0; i < sz(s); i++) { + for (int j = 0; j < ssize(t); j++) { + for (int i = 0; i < ssize(s); i++) { int cur = 0; - while (i+cur < sz(s) && j+cur < sz(t) && s[i+cur] == t[j+cur]) cur++; + while (i+cur < ssize(s) && j+cur < ssize(t) && s[i+cur] == t[j+cur]) cur++; if (cur > len) { pos = j; len = cur; @@ -43,7 +43,7 @@ void performance_test() { SuffixAutomaton sa(s); t.stop(); hash_t hash = 0; - for (ll c = 0; c < sz(s);) { + for (ll c = 0; c < ssize(s);) { int m = Random::integer<int>(1, 1000); s = Random::string(m, "abc"); t.start(); diff --git a/test/string/suffixTree.cpp b/test/string/suffixTree.cpp index 9181c2e..6f3d912 100644 --- a/test/string/suffixTree.cpp +++ b/test/string/suffixTree.cpp @@ -2,8 +2,8 @@ #include <string/suffixTree.cpp> vector<string> naive(string_view s) { - vector<string> res(sz(s)); - for (ll i = 0; i < sz(s); i++) { + vector<string> res(ssize(s)); + for (ll i = 0; i < ssize(s); i++) { res[i] = s.substr(i); } return res; @@ -19,7 +19,7 @@ void stress_test() { auto dfs = [&](auto&& self, string pref, ll node) -> void { auto& [l, r, _, next] = st.tree[node]; if (l >= 0) pref += s.substr(l, r - l); - if (pref.back() == '#') got[n + 1 - sz(pref)] = pref; + if (pref.back() == '#') got[n + 1 - ssize(pref)] = pref; for (auto [__, j] : next) { self(self, pref, j); } @@ -39,7 +39,7 @@ void performance_test() { t.start(); SuffixTree st(s); t.stop(); - hash_t hash = sz(st.tree); + hash_t hash = ssize(st.tree); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/z.cpp b/test/string/z.cpp index f190482..a11984a 100644 --- a/test/string/z.cpp +++ b/test/string/z.cpp @@ -2,9 +2,9 @@ #include <string/z.cpp> vector<int> naive(const string& s) { - vector<int> res(sz(s)); - for (int i = 1; i < sz(s); i++) { - while (i + res[i] < sz(s) && s[res[i]] == s[i + res[i]]) res[i]++; + vector<int> res(ssize(s)); + for (int i = 1; i < ssize(s); i++) { + while (i + res[i] < ssize(s) && s[res[i]] == s[i + res[i]]) res[i]++; } return res; } diff --git a/test/test.sh b/test/test.sh deleted file mode 100755 index a3e6ea9..0000000 --- a/test/test.sh +++ /dev/null @@ -1,131 +0,0 @@ -#!/bin/bash -set -e -cd "$(dirname "$0")" -ulimit -s 4000000 -export MALLOC_PERTURB_="$((2#01011001))" -shopt -s lastpipe -export UBSAN_OPTIONS=halt_on_error=1:print_stacktrace=1 - -declare -A cppstandard -cppstandard["string/suffixArray.cpp"]="gnu++20" -cppstandard["other/pbs.cpp"]="gnu++20" -seedmacro="" -compilerflags="-O2" -debugflags="-O2 -fsanitize=address,undefined" - -process_awk() { - awk_file=$(realpath --relative-to="${PWD}" "${1}") - cpp_file=${awk_file%.awk} - folder=$(dirname $awk_file) - #echo "$awk_file" - mkdir -p "./awk/$folder" - awk -f "$awk_file" < "../content/$cpp_file" > "./awk/$cpp_file" -} - -test_file() { - file=$(realpath --relative-to="${PWD}" "${1}") - echo "$file:" - - echo "compiling with sanitizer..." - std="gnu++17" - if [[ -v cppstandard[$file] ]]; then - std=${cppstandard[$file]} - fi - g++ -std=$std "$file" -I ./awk/ -I ../content/ $debugflags -Wall -Wextra -Wshadow -Werror -DSANITIZE $seedmacro - echo "running with sanitizer..." - timeout --foreground 90s ./a.out - rm ./a.out - - echo "compiling -O2..." - std="gnu++17" - if [[ -v cppstandard[$file] ]]; then - std=${cppstandard[$file]} - fi - g++ -std=$std "$file" -I ./awk/ -I ../content/ $compilerflags -Wall -Wextra -Wshadow -Werror $seedmacro - echo "running -O2..." - timeout --foreground 60s ./a.out - echo "" - rm ./a.out -} - -list_missing() { - declare -A ignore - ignore["other/bitOps.cpp"]=1 - ignore["other/pragmas.cpp"]=1 - ignore["other/stuff.cpp"]=1 - ignore["other/timed.cpp"]=1 - ignore["tests/gcc5bug.cpp"]=1 - ignore["tests/precision.cpp"]=1 - ignore["tests/whitespace.cpp"]=1 - - total=0 - missing=0 - - if [[ ! -v $1 ]]; then - echo "missing tests:" - fi - find ../content/ -type f -name '*.cpp' -print0 | sort -z | while read -d $'\0' file - do - total=$((total+1)) - file=${file#../content/} - if [ ! -f "$file" ] && [[ ! -v ignore["$file"] ]]; then - missing=$((missing+1)) - if [[ ! -v $1 ]]; then - echo " $file" - fi - fi - done - if [[ -v $1 ]]; then - covered=$((total-missing)) - coverage=$((100*covered/total)) - echo "REQUIRED=$(( total < 4 ? 0 : total - 4 ))" - echo "TOTAL=$total" - echo "COVERED=$covered" - echo "MISSING=$missing" - fi -} - -coverage() { - list_missing 1 -} - -rm -rf ./awk/ -find . -type f -path '*.awk' -print0 | sort -z | while read -d $'\0' file -do - process_awk "$file" -done - -if [ "$#" -ne 0 ]; then - for arg in "$@" - do - if [[ $arg == "--awk" ]]; then - echo "processed all awk files" - elif [[ $arg == "--missing" ]]; then - list_missing - elif [[ $arg == "--coverage" ]]; then - coverage - elif [[ $arg == --seed=* ]]; then - seedmacro="-DSEED=${arg:7}ll" - elif [[ $arg == "--debug" ]]; then - debugflags="-g -fsanitize=address,undefined" - elif [ -d "$arg" ]; then - dir=$(realpath --relative-to="${PWD}" "$arg") - find . -type f -path "./${dir}/*.cpp" -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file - do - test_file "$file" - done - elif [ -f "$arg" ]; then - test_file "$arg" - else - echo "did not recognize: $arg" - exit 1 - fi - done -else - find . -type f -path '*.cpp' -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file - do - test_file "$file" - done - list_missing -fi - diff --git a/test/util.h b/test/util.h index 8de393d..880ff04 100644 --- a/test/util.h +++ b/test/util.h @@ -1,16 +1,12 @@ #include <bits/stdc++.h> using namespace std; -#define all(x) std::begin(x), std::end(x) -#define sz(x) (ll)std::size(x) - #ifdef SANITIZE constexpr bool sanitize = true; #else constexpr bool sanitize = false; #endif - using ll = long long; using lll = __int128; using ld = long double; @@ -20,6 +16,16 @@ namespace INT {constexpr int INF = 0x3FFF'FFFF;} namespace LL {constexpr ll INF = 0x3FFF'FFFF'FFFF'FFFFll;} namespace LD {constexpr ld INF = numeric_limits<ld>::infinity();} +#ifdef SANITIZE +template<typename T> +T _lg_check(T n) { + assert(n > 0); + return __lg(n); +} + +#define __lg _lg_check +#endif + namespace details { template<typename T = ll> bool isPrime(T x) { @@ -116,7 +122,7 @@ namespace Random { std::string string(std::size_t n, string_view chars) { std::string res(n, '*'); - for (char& c : res) c = chars[integer(sz(chars))]; + for (char& c : res) c = chars[integer(ssize(chars))]; return res; } @@ -175,6 +181,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; @@ -190,7 +220,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() { @@ -215,7 +245,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>{}); @@ -264,9 +294,9 @@ public: Graph(int n) : adj(n) {} - int m() const {return sz(edges);} - int n() const {return sz(adj);} - int deg(int x) const {return sz(adj[x]);} + int m() const {return ssize(edges);} + int n() const {return ssize(adj);} + int deg(int x) const {return ssize(adj[x]);} Graph& clear() { adj.assign(adj.size(), {}); @@ -278,33 +308,33 @@ public: if (!LOOPS && from == to) return false; if (!MULTI && adj[from].find(to) != adj[from].end()) return false; edges.emplace_back(from, to, w); - _addAdj(sz(edges) - 1); + _addAdj(ssize(edges) - 1); return true; } Graph& reverse() { for (auto& e : edges) swap(e.from, e.to); adj.assign(adj.size(), {}); - for (int i = 0; i < sz(edges); i++) _addAdj(i); + for (int i = 0; i < ssize(edges); i++) _addAdj(i); return *this; } Graph& shuffle() { - std::shuffle(all(edges), Random::rng); + ranges::shuffle(edges, Random::rng); if constexpr (!DIR) { for (auto& e : edges) { if (Random::integer(0, 2)) swap(e.from, e.to); } } adj.assign(adj.size(), {}); - for (int i = 0; i < sz(edges); i++) _addAdj(i); + for (int i = 0; i < ssize(edges); i++) _addAdj(i); return *this; } Graph& permutate() { vector<int> perm(n()); - iota(all(perm), 0); - std::shuffle(all(perm), Random::rng); + iota(begin(perm), end(perm), 0); + ranges::shuffle(perm, Random::rng); for (auto& e : edges) { e.from = perm[e.from]; e.to = perm[e.to]; @@ -382,7 +412,7 @@ public: } } } - std::shuffle(all(tmp), Random::rng); + ranges::shuffle(tmp, Random::rng); for (auto [a, b] : tmp) { if (todo <= 0) break; if (addEdge(a, b)) todo--; @@ -420,3 +450,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>; + |