mzuenni tests

12 files changed, 0 insertions, 585 deletions

diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp
deleted file mode 100644
index f9dd619..0000000
--- a/datastructures/test/fenwickTree.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#include "../fenwickTree.cpp"
-
-void test(int n) {
-	vector<ll> naive(n);
-	init(n);
-
-	for (int i = 0; i < 1000; i++) {
-		int p = util::randint(n);
-		ll delta = util::randint();
-		update(p, delta);
-		naive[p] += delta;
-
-		int r = util::randint(n+1);
-
-		ll naive_result = 0;
-		for (int i = 0; i < r; i++) naive_result += naive[i];
-		ll fenwick_result = prefix_sum(r);
-		assert(naive_result == fenwick_result);
-	}
-}
-
-int main() {
-	test(1);
-	test(100);
-	test(1000);
-}
diff --git a/datastructures/test/fenwickTree2.cpp b/datastructures/test/fenwickTree2.cpp
deleted file mode 100644
index 18ebcb7..0000000
--- a/datastructures/test/fenwickTree2.cpp
+++ /dev/null
@@ -1,28 +0,0 @@
-#include "../fenwickTree2.cpp"
-
-void test(int n) {
-	vector<ll> naive(n);
-	for (int i = 0; i < n; i++) naive[i] = util::randint();
-	init(naive);
-
-	for (int i = 0; i < 1000; i++) {
-		int l = util::randint(n), r = util::randint(n);
-		if (l > r) swap(l, r);
-		ll delta = util::randint();
-		update(l, r, delta);
-		for (int i = l; i < r; i++) naive[i] += delta;
-
-		r = util::randint(n+1);
-
-		ll naive_result = 0;
-		for (int i = 0; i < r; i++) naive_result += naive[i];
-		ll fenwick_result = prefix_sum(r);
-		assert(naive_result == fenwick_result);
-	}
-}
-
-int main() {
-	test(1);
-	test(100);
-	test(1000);
-}
diff --git a/datastructures/test/lazyPropagation.awk b/datastructures/test/lazyPropagation.awk
deleted file mode 100644
index fc39305..0000000
--- a/datastructures/test/lazyPropagation.awk
+++ /dev/null
@@ -1,86 +0,0 @@
-
-/Neutral element for combine/ {
-	print "#ifndef SEGTREE_FIRST_NEG"
-	print "# ifndef SEGTREE_MAX"
-	print
-	print "# else"
-	tmp = $0
-	sub(/0/, "numeric_limits<T>::min()", tmp)
-	print tmp
-	print "# endif"
-	print "#else"
-	sub(/0/, "numeric_limits<T>::max()")
-	print
-	print "#endif"
-	next
-}
-
-/Modify this \+ E/ {
-	print "#ifndef SEGTREE_FIRST_NEG"
-	print "# ifndef SEGTREE_MAX"
-	print
-	print "# else"
-	tmp = $0
-	sub(/a \+ b/, "max(a, b)", tmp)
-	print tmp
-	print "# endif"
-	print "#else"
-	sub(/a \+ b/, "a < 0 ? a : min(a, b)")
-	print
-	print "#endif"
-	next
-}
-
-/Unused value by updates/ {
-	print "#ifndef SEGTREE_FIRST_NEG"
-	print
-	print "#else"
-	sub(/0/, /numeric_limits<U>::max()/)
-	print
-	print "#endif"
-	next
-}
-
-/And this \+ UF/ {
-	print
-	getline set_tree
-	getline set_lazy
-	print "#ifndef SEGTREE_MAX"
-	print "# ifndef SEGTREE_FIRST_NEG"
-	print set_tree
-	print "# else"
-	tmp = set_tree
-	sub(/val \* k\[i\]/, "val", tmp)
-	print tmp
-	print "# endif"
-	print set_lazy
-	print "#else"
-	sub(/= val \* k\[i\]/, "+= val", set_tree)
-	sub(/= val/, "+= val", set_lazy)
-	print set_tree
-	print set_lazy
-	print "#endif"
-	next
-}
-
-/Optional/ { print "#ifdef SEGTREE_MAX" }
-/^\};$/ { print "#endif" }
-
-/SegTree\(const vector<T>& a\)/ {
-	print "#ifndef SEGTREE_INIT_DEFAULT"
-	print
-	print "#else"
-	getline
-	sub(/\/\//, "")
-	print
-	print "#endif"
-	getline
-	print
-	print "#ifndef SEGTREE_INIT_DEFAULT"
-	getline
-	print
-	print "#endif"
-	next
-}
-
-{ print }
diff --git a/datastructures/test/lazyPropagation.cpp b/datastructures/test/lazyPropagation.cpp
deleted file mode 100644
index df97b14..0000000
--- a/datastructures/test/lazyPropagation.cpp
+++ /dev/null
@@ -1,102 +0,0 @@
-#include "lazyPropagation.tmp.cpp"
-
-void test(int n) {
-#ifndef SEGTREE_INIT_DEFAULT
-	vector<ll> a(n);
-	for (ll &x: a) x = util::randint();
-	SegTree seg(a);
-#else
-	ll init = util::randint();
-# ifdef SEGTREE_FIRST_NEG
-	init = abs(init);
-# endif
-	vector<ll> a(n, init);
-	SegTree seg(n, init);
-#endif
-	for (int i = 0; i < 5*n; i++) {
-		{
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-			ll v = util::randint();
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
-			if (v == 0) v = 1;
-# endif
-#endif
-			for (int j = l; j < r; j++) {
-#ifndef SEGTREE_MAX
-				a[j] = v;
-#else
-				a[j] += v;
-#endif
-			}
-			seg.update(l, r, v);
-		}
-		{
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
-			ll comp = 0;
-# else
-			ll comp = numeric_limits<ll>::min();
-# endif
-#else
-			ll comp = numeric_limits<ll>::max();
-#endif
-			for (int j = l; j < r; j++) {
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
-				comp += a[j];
-# else
-				comp = max(comp, a[j]);
-# endif
-#else
-				if (comp >= 0 && comp > a[j]) comp = a[j];
-#endif
-			}
-			assert(seg.query(l, r) == comp);
-		}
-#ifdef SEGTREE_MAX
-		{
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-			ll bound = util::randint();
-			int found = -1;
-			for (int j = l; j < r; j++) {
-				if (a[j] >= bound) {
-					found = j;
-					break;
-				}
-			}
-			assert(seg.lower_bound(l, r, bound) == found);
-		}
-#endif
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-	{
-#ifndef SEGTREE_INIT_DEFAULT
-		vector<ll> a;
-		SegTree seg(a);
-#else
-		SegTree seg(0);
-#endif
-		seg.update(0, 0, util::randint());
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
-		assert(seg.query(0, 0) == 0);
-# else
-		assert(seg.query(0, 0) == numeric_limits<ll>::min());
-# endif
-#else
-		assert(seg.query(0, 0) == numeric_limits<ll>::max());
-#endif
-	}
-}
diff --git a/datastructures/test/monotonicConvexHull.cpp b/datastructures/test/monotonicConvexHull.cpp
deleted file mode 100644
index 08927a2..0000000
--- a/datastructures/test/monotonicConvexHull.cpp
+++ /dev/null
@@ -1,27 +0,0 @@
-#define sz(X) ((int)size(X))
-#include "../monotonicConvexHull.cpp"
-
-int main() {
-	{
-		Envelope env;
-		env.add(10, 0);
-		assert(env.query(0) == 0);
-		assert(env.query(1) == 10);
-		env.add(8, 5);
-		assert(env.query(1) == 10);
-		assert(env.query(2) == 20);
-		assert(env.query(3) == 29);
-		env.add(7, 10);
-		assert(env.query(10) == 80);
-		env.add(0, 0);
-		assert(env.query(11) == 0);
-	}
-
-	{
-		Envelope env;
-		env.add(1, 0);
-		env.add(0, 10);
-		env.add(-1, 10);
-		assert(env.query(7) == 3);
-	}
-}
diff --git a/datastructures/test/persistent.cpp b/datastructures/test/persistent.cpp
deleted file mode 100644
index 5e5f864..0000000
--- a/datastructures/test/persistent.cpp
+++ /dev/null
@@ -1,11 +0,0 @@
-#define all(X) begin(X), end(X)
-#include "../persistent.cpp"
-
-int main() {
-	int time = 0;
-	persistent<int> p(time, 0);
-	p.set(1);
-	int t1 = time;
-	p.set(2);
-	assert(p.get(t1) == 1);
-}
diff --git a/datastructures/test/segmentTree.awk b/datastructures/test/segmentTree.awk
deleted file mode 100644
index e863d4e..0000000
--- a/datastructures/test/segmentTree.awk
+++ /dev/null
@@ -1,74 +0,0 @@
-
-/Neutral element for combine/ {
-	print "#ifndef SEGTREE_MUL"
-	print "# ifndef SEGTREE_FIRST_NEG"
-	print
-	print "# else"
-	tmp = $0
-	sub(/0/, "numeric_limits<ll>::max()", tmp)
-	print tmp
-	print "# endif"
-	print "#else"
-	sub(/0/, "1")
-	print
-	print "#endif"
-	next
-}
-
-/modify this \+ neutral/ {
-	print "#ifndef SEGTREE_MUL"
-	print "# ifndef SEGTREE_FIRST_NEG"
-	print
-	print "# else"
-	tmp = $0
-	sub(/a \+ b/, "a < 0 ? a : min(a, b)", tmp)
-	print tmp
-	print "# endif"
-	print "#else"
-	sub(/a \+ b/, "a*b % MOD")
-	print
-	print "#endif"
-	next
-}
-
-/SegTree\(vector<T>& a\)/ {
-	print "#ifndef SEGTREE_INIT_DEFAULT"
-	print
-	getline
-	print
-	print "#else"
-	getline
-	sub(/\/\//, "")
-	print
-	getline
-	sub(/\/\//, "")
-	print
-	print "#endif"
-	next
-}
-
-/remove for range update/ {
-	print "#ifndef SEGTREE_RANGE_UPDATE"
-	print
-	getline
-	print
-	getline
-	print "\t\t}"
-	print "#endif"
-	print "\t}"
-	next
-}
-
-/void update/ {
-	print "#ifndef SEGTREE_RANGE_UPDATE"
-}
-
-/OR: range update/ {
-	print "#else"
-}
-
-/^\};$/ {
-	print "#endif"
-}
-
-{ print }
diff --git a/datastructures/test/segmentTree.cpp b/datastructures/test/segmentTree.cpp
deleted file mode 100644
index 44d99b6..0000000
--- a/datastructures/test/segmentTree.cpp
+++ /dev/null
@@ -1,100 +0,0 @@
-#ifdef SEGTREE_MUL
-constexpr ll MOD = 1'000'000'007;
-#endif
-
-#include "segmentTree.tmp.cpp"
-
-void test(int n) {
-#ifndef SEGTREE_INIT_DEFAULT
-	vector<ll> a(n);
-	for (ll &x: a) x = util::randint();
-	SegTree seg(a);
-#else
-	ll init = util::randint();
-# ifdef SEGTREE_FIRST_NEG
-	init = abs(init);
-# endif
-	vector<ll> a(n, init);
-	SegTree seg(n, init);
-#endif
-	for (int i = 0; i < 5*n; i++) {
-		{
-#ifndef SEGTREE_RANGE_UPDATE
-			int j = util::randint(n);
-			ll v = util::randint();
-			a[j] = v;
-			seg.update(j, v);
-#else
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-			ll v = util::randint();
-			for (int j = l; j < r; j++) {
-# ifndef SEGTREE_MUL
-				a[j] += v;
-# else
-				a[j] = a[j]*v % MOD;
-# endif
-			}
-			seg.modify(l, r, v);
-#endif
-		}
-		{
-#ifndef SEGTREE_RANGE_UPDATE
-			int l = util::randint(n+1);
-			int r = util::randint(n+1);
-			if (l > r) swap(l, r);
-# ifndef SEGTREE_MUL
-#  ifndef SEGTREE_FIRST_NEG
-			ll comp = 0;
-#  else
-			ll comp = numeric_limits<ll>::max();
-#  endif
-# else
-			ll comp = 1;
-# endif
-			for (int j = l; j < r; j++) {
-# ifndef SEGTREE_MUL
-#  ifndef SEGTREE_FIRST_NEG
-				comp += a[j];
-#  else
-				if (comp >= 0 && comp > a[j]) comp = a[j];
-#  endif
-# else
-				comp = comp * a[j] % MOD;
-# endif
-			}
-			assert(seg.query(l, r) == comp);
-#else
-			int j = util::randint(n);
-			assert(seg.query(j) == a[j]);
-#endif
-		}
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-	{
-#ifndef SEGTREE_INIT_DEFAULT
-		vector<ll> a;
-		SegTree seg(a);
-#else
-		SegTree seg(0);
-#endif
-#ifndef SEGTREE_RANGE_UPDATE
-# ifndef SEGTREE_MUL
-#  ifndef SEGTREE_FIRST_NEG
-		assert(seg.query(0, 0) == 0);
-#  else
-		assert(seg.query(0, 0) == numeric_limits<ll>::max());
-#  endif
-# else
-		assert(seg.query(0, 0) == 1);
-# endif
-#else
-		seg.modify(0, 0, util::randint());
-#endif
-	}
-}
diff --git a/datastructures/test/sparseTable.cpp b/datastructures/test/sparseTable.cpp
deleted file mode 100644
index 03ef548..0000000
--- a/datastructures/test/sparseTable.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#define sz ssize
-#define all(X) begin(X), end(X)
-#include "../sparseTable.cpp"
-
-void test(int n) {
-	vector<ll> values(n);
-	for (ll &x: values) x = util::randint();
-	SparseTable st;
-	st.init(values);
-	for (int i = 0; i < n; i++) {
-		int l = util::randint(n);
-		int r = util::randint(n);
-		if (l > r) swap(l, r);
-		r++;
-		assert(
-			values[st.queryIdempotent(l, r)]
-			==
-			*min_element(values.begin()+l, values.begin()+r)
-		);
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-}
diff --git a/datastructures/test/sparseTableDisjoint.cpp b/datastructures/test/sparseTableDisjoint.cpp
deleted file mode 100644
index 7ef6483..0000000
--- a/datastructures/test/sparseTableDisjoint.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#define sz ssize
-#define all(X) begin(X), end(X)
-#include "../sparseTableDisjoint.cpp"
-
-void test(int n) {
-	vector<ll> values(n);
-	for (ll &x: values) x = util::randint();
-	DisjointST st;
-	st.init(values);
-	for (int i = 0; i < n; i++) {
-		int l = util::randint(n);
-		int r = util::randint(n);
-		if (l > r) swap(l, r);
-		r++;
-		assert(
-			st.query(l, r)
-			==
-			accumulate(values.begin()+l, values.begin()+r, 0ll)
-		);
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-}
diff --git a/datastructures/test/treap2.cpp b/datastructures/test/treap2.cpp
deleted file mode 100644
index 1a435d3..0000000
--- a/datastructures/test/treap2.cpp
+++ /dev/null
@@ -1,41 +0,0 @@
-#include "../treap2.cpp"
-
-void test(int n) {
-	Treap treap;
-	vector<ll> dumb;
-	for (int i = 0; i < n; i++) {
-		assert(treap.getSize(treap.root) == ssize(dumb));
-		int j = util::randint(ssize(dumb) + 1);
-		ll x = util::randint();
-		treap.insert(j, x);
-		dumb.insert(begin(dumb) + j, x);
-	}
-	for (int i = 0; i < 5*n; i++) {
-		assert(treap.getSize(treap.root) == ssize(dumb));
-		{
-			int j = util::randint(ssize(dumb));
-			treap.remove(j);
-			dumb.erase(begin(dumb) + j);
-		}
-		{
-			int j = util::randint(ssize(dumb) + 1);
-			ll x = util::randint();
-			treap.insert(j, x);
-			dumb.insert(begin(dumb) + j, x);
-		}
-	}
-	for (int i = 0; i < n; i++) {
-		assert(treap.getSize(treap.root) == ssize(dumb));
-		int j = util::randint(ssize(dumb));
-		treap.remove(j);
-		dumb.erase(begin(dumb) + j);
-	}
-	assert(treap.root < 0);
-	assert(empty(dumb));
-}
-
-int main() {
-	test(1000);
-	test(1);
-	test(0);
-}
diff --git a/datastructures/test/waveletTree.cpp b/datastructures/test/waveletTree.cpp
deleted file mode 100644
index c5da1d2..0000000
--- a/datastructures/test/waveletTree.cpp
+++ /dev/null
@@ -1,38 +0,0 @@
-#include "../waveletTree.cpp"
-
-void test(int n) {
-	vector<ll> values(n);
-	for (ll &x: values) x = util::randint();
-	vector<ll> backup = values;
-	WaveletTree wave(values);
-	assert(values == backup);
-	for (int i = 0; i < n; i++) {
-		int l = util::randint(n+1);
-		int r = util::randint(n+1);
-		if (l > r) swap(l, r);
-		ll bound = util::randint();
-		int res = 0;
-		for (ll x: values | views::take(r) | views::drop(l)) {
-			if (x < bound) res++;
-		}
-		assert(wave.countSmaller(l, r, bound) == res);
-	}
-	for (int i = 0; 5*i < n; i++) {
-		int l = util::randint(n);
-		int m = util::randint(n);
-		int r = util::randint(n);
-		if (l > m) swap(l, m);
-		if (m > r) swap(m, r);
-		if (l > m) swap(l, m);
-		r++;
-		int k = m-l;
-		vector<ll> part(values.begin()+l, values.begin()+r);
-		ranges::nth_element(part, part.begin() + k);
-		assert(wave.kth(l, r, k) == part[k]);
-	}
-}
-
-int main() {
-	test(1000);
-	test(1);
-}