diff options
131 files changed, 336 insertions, 261 deletions
diff --git a/content/datastructures/LCT.cpp b/content/datastructures/LCT.cpp index c1dd278..e88c8d3 100644 --- a/content/datastructures/LCT.cpp +++ b/content/datastructures/LCT.cpp @@ -53,8 +53,7 @@ struct LCT { if (right) right->revert ^= 1; } nodeValue = joinValueDelta(nodeValue, delta); - subTreeValue = joinValueDelta(subTreeValue, - _update(delta, size)); + subTreeValue = getSubtreeValue(); if (left) left->delta = joinDeltas(left->delta, delta); if (right) right->delta = joinDeltas(right->delta, delta); delta = updateDefault; @@ -68,8 +67,8 @@ struct LCT { subTreeValue = joinValueDelta(nodeValue, delta); size = 1; if (left) { - subTreeValue = _query(subTreeValue, - left->getSubtreeValue()); + subTreeValue = _query(left->getSubtreeValue(), + subTreeValue); size += left->size; } if (right) { diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index eeff156..b42f089 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -1,6 +1,6 @@ vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten. -auto bitonicTSP() { +auto bitonicTSP() { // n >= 2 vector<double> dp(ssize(dist), HUGE_VAL); vector<int> pre(ssize(dist)); // nur für Tour dp[0] = 0; dp[1] = 2 * dist[0][1]; pre[1] = 0; diff --git a/content/graph/bronKerbosch.cpp b/content/graph/bronKerbosch.cpp index cf07c88..144707a 100644 --- a/content/graph/bronKerbosch.cpp +++ b/content/graph/bronKerbosch.cpp @@ -9,7 +9,7 @@ void bronKerboschRec(bits R, bits P, bits X) { if (P.none() && X.none()) { cliques.push_back(R); } else { - int q = min(P._Find_first(), X._Find_first()); + int q = (P | X)._Find_first(); bits cands = P & ~adj[q]; for (int i = 0; i < ssize(adj); i++) if (cands[i]) { R[i] = 1; diff --git a/content/math/math.tex b/content/math/math.tex index 943beef..bcb4275 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -414,7 +414,8 @@ so gilt \sourcecode{math/binomial3.cpp}
%\end{algorithm}
-\paragraph{\textsc{Catalan}-Zahlen}
+\paragraph{\textsc{Catalan}-Zahlen:}
+$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$
\begin{itemize}
\item Die \textsc{Catalan}-Zahl $C_n$ gibt an:
\begin{itemize}
@@ -429,18 +430,19 @@ so gilt \[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} C_{n-1} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\]
\begin{itemize}
- \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
- \item Formel $2$ und $3$ erlauben Berechnung in \runtime{n}
+ \item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n}
\end{itemize}
\paragraph{\textsc{Catalan}-Convolution}
\begin{itemize}
- \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $(^k$ beginnen.
+ \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen.
\end{itemize}
\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =
\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} C_{n-1}\]
-\paragraph{\textsc{Euler}-Zahlen}
+\paragraph{\textsc{Euler}-Zahlen:}
+$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$
+
Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
@@ -452,11 +454,13 @@ Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergä \left(\sum_{i=0}^\infty (-1)^i \binom{n+1}{i} x^i\right)
\]
-\paragraph{\textsc{Stirling}-Zahlen 1. Art}
+\paragraph{\textsc{Stirling}-Zahlen 1. Art:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$
+
Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigenen Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.
\[\stirlingI{0}{0} = 1 \qquad
-\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
+\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad
\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]
\[
\stirlingI{n}{k}
@@ -464,7 +468,9 @@ Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eige = n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{i+1}x^i\right)^k
\]
-\paragraph{\textsc{Stirling}-Zahlen 2. Art}
+\paragraph{\textsc{Stirling}-Zahlen 2. Art:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$
+
Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen.
Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
@@ -479,7 +485,9 @@ Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht. = n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{(i+1)!}x^i\right)^k
\]
-\paragraph{\textsc{Bell}-Zahlen}
+\paragraph{\textsc{Bell}-Zahlen:}
+$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$
+
Anzahl der Partitionen von $\{1, \ldots, n\}$.
Wie \textsc{Stirling}-Zahlen 2. Art ohne Limit durch $k$.
\[B_1 = 1 \qquad
@@ -489,12 +497,20 @@ B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k} \qquad
B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]
-\paragraph{Partitions}
+\paragraph{$\boldsymbol{k}$ Partitions:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$
+
Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
-Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
+Die Anzahl der Partitionen von $n$ mit größtem Elementen $k$.
\begin{align*}
p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\
+\end{align*}
+
+\paragraph{Partitions:}
+$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$
+
+\begin{align*}
p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg] \\
p(n)&=[x^n] \left(\sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}\right)^{-1}
\sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{\frac{2n}{3}}\right)
diff --git a/content/math/piLehmer.cpp b/content/math/piLehmer.cpp index 17df85e..adef16d 100644 --- a/content/math/piLehmer.cpp +++ b/content/math/piLehmer.cpp @@ -6,7 +6,7 @@ ll memoC[N]; void init() {
primeSieve(); // @\sourceref{math/primeSieve.cpp}@
- for (ll i = 0; i < N; i++) {
+ for (ll i = 1; i < N; i++) {
memoC[i] = memoC[i - 1];
if (isPrime(i)) memoC[i]++;
}
diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp index 3d8aa11..cfac7b9 100644 --- a/content/math/transforms/seriesOperations.cpp +++ b/content/math/transforms/seriesOperations.cpp @@ -1,4 +1,4 @@ -vector<ll> poly_inv(const vector<ll>& a, int n) { +vector<ll> poly_inv(const vector<ll>& a, int n) { // a[0] == 1 vector<ll> q = {powMod(a[0], mod-2, mod)}; for (int len = 1; len < n; len *= 2){ vector<ll> a2 = a, q2 = q; @@ -35,13 +35,13 @@ vector<ll> poly_integr(vector<ll> a) { return a; } -vector<ll> poly_log(vector<ll> a, int n) { +vector<ll> poly_log(vector<ll> a, int n) { // a[0] == 1 a = mul(poly_deriv(a), poly_inv(a, n)); a.resize(n-1); return poly_integr(a); } -vector<ll> poly_exp(vector<ll> a, int n) { +vector<ll> poly_exp(vector<ll> a, int n) { // a[0] == 0 vector<ll> q = {1}; for (int len = 1; len < n; len *= 2) { vector<ll> p = poly_log(q, 2*len); diff --git a/content/other/other.tex b/content/other/other.tex index 9661d89..d8726d4 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -151,7 +151,7 @@ Das Komplement eines Vertex-Cover ist ein Independent Set.
$\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover.
- \item \textbf{Bipartiter Graph:}
+ \item \textbf{Bipartiter Graph (Satz von \textsc{König}):}
Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching.
Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$.
@@ -186,15 +186,19 @@ \item \textbf{\textsc{Bertrand}sches Postulat:}
Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$.
- \item \textbf{Satz von \textsc{Kirchhoff}:}
+ \item \textbf{Satz von \textsc{Kirchhoff} (Anzahl Spannbäume):}
Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten.
- Sei $A$ die Adjazenzmatrix von $G$.
+ Sei $A$ die Adjazenzmatrix von~$G$.
Dabei ist $a_{ij}$ die Anzahl der Kanten zwischen Knoten $i$ und $j$.
- Sei $B$ eine Diagonalmatrix, $b_{ii}$ sei der Grad von Knoten $i$.
+ Sei $B$ eine Diagonalmatrix mit $b_{ii}$ Grad von Knoten $i$.
Definiere $R = B - A$.
- Alle Kofaktoren von $R$ sind gleich und die Anzahl der Spannbäume von $G$.
+ Entferne $k$-te Zeile und $k$-te Spalte ($k$ beliebig) und berechne Betrag der Determinante.
+ Das Ergebnis ist die Anzahl der Spannbäume von $G$.
\newline
- Entferne letzte Zeile und Spalte und berechne Betrag der Determinante.
+ Funktioniert auch für gerichtete Graphen: $b_{ii}$ ist der Outdegree und man
+ berechnet die Determinante nach Entfernen der $k$-ten Zeile und Spalte.
+ Das Ergebnis ist die Anzahl an gerichteten Spannbäumen mit Wurzel $k$,
+ sodass jeder Knoten einen Pfad zu $k$ hat.
\item \textbf{\textsc{Dilworth}'s Theorem:}
Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset).
@@ -205,10 +209,15 @@ Es gilt: Die Größe der längsten Antikette gleicht der Größe der kleinsten Partition.
$\Rightarrow$ \emph{Weite} des Poset.
\newline
- Berechnung: Maximales Matching in bipartitem Graphen.
+ Berechnung der minimalen Partition: Maximales Matching in bipartitem Graphen.
Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.
Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.
- Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Antikette zu finden.
+ Wenn $u_x$ mit $v_y$ gematched wird, sind $x$ und $y$ in derselben Kette.
+ \newline
+ Berechnung der maximalen Antikette: Verwende Satz von König, um ein
+ minimales Vertexcover des bipartiten Graphen zu finden.
+ Ersetze $u_x, v_x$ durch $x$ und erhalte so minimales Vertexcover vom Poset.
+ Das Komplement davon ist eine maximale Antikette.
\item \textbf{\textsc{Tur\'an}'s Theorem:}
Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist:
diff --git a/content/string/trie.cpp b/content/string/trie.cpp index db39c43..64d7beb 100644 --- a/content/string/trie.cpp +++ b/content/string/trie.cpp @@ -10,13 +10,14 @@ vector<node> trie = {node()}; int traverse(const vector<int>& word, int x) { int id = 0; for (int c : word) { - if (id < 0 || (trie[id].words == 0 && x <= 0)) return -1; + if (trie[id].words == 0 && x <= 0) return -1; trie[id].words += x; if (trie[id].nxt[c] < 0 && x > 0) { trie[id].nxt[c] = ssize(trie); trie.emplace_back(); } id = trie[id].nxt[c]; + if (id < 0) return -1; } trie[id].words += x; trie[id].ends += x; @@ -26,7 +27,6 @@ int traverse(const vector<int>& word, int x) { int insert(const vector<int>& word) { return traverse(word, 1); } - bool erase(const vector<int>& word) { int id = traverse(word, 0); if (id < 0 || trie[id].ends <= 0) return false; diff --git a/test/GNUmakefile b/test/GNUmakefile index e7470a3..cc1b4f5 100644 --- a/test/GNUmakefile +++ b/test/GNUmakefile @@ -2,8 +2,10 @@ 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) +test: $(TESTS:=.ok) $(TESTS:=.san.ok) missing: @find ../content -name '*.cpp' | sed 's|^../content/||' \ @@ -13,22 +15,25 @@ missing: @rm missing.tmp clean: - rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.d) + rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.san.ok) $(TESTS:=.d) rm -rf awk/ %.ok: %.test - timeout --foreground --verbose 60 prlimit -s$$((1<<32)) ./$< + 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 $*.d' -MF $@ $< + $(CXX) -M -MP -MT '$*.test $*.san.test $*.d' -MF $@ $< .PHONY: test clean .SECONDARY: $(TESTS:=.test) $(addprefix awk/,$(AWK)) diff --git a/test/datastructures/LCT.cpp b/test/datastructures/LCT.cpp index 68a952c..e120b6e 100644 --- a/test/datastructures/LCT.cpp +++ b/test/datastructures/LCT.cpp @@ -194,5 +194,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp index 02e50f4..cc57d73 100644 --- a/test/datastructures/dynamicConvexHull.cpp +++ b/test/datastructures/dynamicConvexHull.cpp @@ -63,5 +63,5 @@ int main() { stress_test(100); stress_test(1'000); stress_test(1'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/fenwickTree.cpp b/test/datastructures/fenwickTree.cpp index f2a490a..f3c0274 100644 --- a/test/datastructures/fenwickTree.cpp +++ b/test/datastructures/fenwickTree.cpp @@ -54,5 +54,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp index bc0753f..180bd24 100644 --- a/test/datastructures/fenwickTree2.cpp +++ b/test/datastructures/fenwickTree2.cpp @@ -56,5 +56,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp index 16db945..2e7431b 100644 --- a/test/datastructures/lazyPropagation.cpp +++ b/test/datastructures/lazyPropagation.cpp @@ -113,6 +113,8 @@ void performance_test_binary_search() { int main() { stress_test(); stress_test_binary_search(); - performance_test(); - performance_test_binary_search(); + if (!sanitize) { + performance_test(); + performance_test_binary_search(); + } } diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp index 1639b3d..30d5b58 100644 --- a/test/datastructures/lichao.cpp +++ b/test/datastructures/lichao.cpp @@ -71,5 +71,5 @@ int main() { stress_test(100); stress_test(1'000); stress_test(1'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 98d74f8..1c147e3 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -128,5 +128,5 @@ int main() { stress_test_independent(100); stress_test_independent(1'000); stress_test_independent(1'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/segmentTree.cpp b/test/datastructures/segmentTree.cpp index 2473724..166dfd2 100644 --- a/test/datastructures/segmentTree.cpp +++ b/test/datastructures/segmentTree.cpp @@ -115,8 +115,8 @@ void performance_test2() { int main() { cerr << "point update + range query:" << endl; stress_test1(); - performance_test1(); + if (!sanitize) performance_test1(); cerr << "range update + point query" << endl; stress_test2(); - performance_test2(); + if (!sanitize) performance_test2(); } diff --git a/test/datastructures/sparseTable.cpp b/test/datastructures/sparseTable.cpp index 843e962..078f336 100644 --- a/test/datastructures/sparseTable.cpp +++ b/test/datastructures/sparseTable.cpp @@ -47,5 +47,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/sparseTableDisjoint.cpp b/test/datastructures/sparseTableDisjoint.cpp index 258f4db..d3f42ba 100644 --- a/test/datastructures/sparseTableDisjoint.cpp +++ b/test/datastructures/sparseTableDisjoint.cpp @@ -44,5 +44,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp index d93e0f4..4f0fe03 100644 --- a/test/datastructures/treap.cpp +++ b/test/datastructures/treap.cpp @@ -81,5 +81,5 @@ int main() { stress_test(10000, 10); stress_test(1000, 100); stress_test(100, 10000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/unionFind.cpp b/test/datastructures/unionFind.cpp index 4783f6b..ced2355 100644 --- a/test/datastructures/unionFind.cpp +++ b/test/datastructures/unionFind.cpp @@ -121,5 +121,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/datastructures/waveletTree.cpp b/test/datastructures/waveletTree.cpp index e70d57b..06b3e03 100644 --- a/test/datastructures/waveletTree.cpp +++ b/test/datastructures/waveletTree.cpp @@ -71,5 +71,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/geometry/antipodalPoints.cpp b/test/geometry/antipodalPoints.cpp index 013f43c..ec2006e 100644 --- a/test/geometry/antipodalPoints.cpp +++ b/test/geometry/antipodalPoints.cpp @@ -66,5 +66,5 @@ void performance_test() { int main() { stress_test(100); stress_test(1'000'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/geometry/closestPair.cpp b/test/geometry/closestPair.cpp index 4e558dc..a8e1382 100644 --- a/test/geometry/closestPair.cpp +++ b/test/geometry/closestPair.cpp @@ -65,5 +65,5 @@ void performance_test() { int main() { stress_test(100); stress_test(1'000'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/geometry/closestPair.double.cpp b/test/geometry/closestPair.double.cpp index 9ef039f..14ccd0d 100644 --- a/test/geometry/closestPair.double.cpp +++ b/test/geometry/closestPair.double.cpp @@ -62,5 +62,5 @@ void performance_test() { int main() { stress_test(100); stress_test(1'000'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/geometry/convexHull.cpp b/test/geometry/convexHull.cpp index 0ca52a2..ee858f9 100644 --- a/test/geometry/convexHull.cpp +++ b/test/geometry/convexHull.cpp @@ -75,5 +75,5 @@ void performance_test() { int main() { stress_test(100); stress_test(1'000'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp index b824ad8..51df879 100644 --- a/test/geometry/delaunay.cpp +++ b/test/geometry/delaunay.cpp @@ -68,9 +68,9 @@ bool inOutCirc(pt a, pt b, pt c, pt p) { } -void stress_test(ll range) { +void stress_test(ll LIM, ll range) { ll queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer<int>(3, 30); auto ps = Random::points<lll>(n, -range, range); bool skip = true; @@ -136,8 +136,14 @@ void performance_test() { } int main() { - stress_test(10); - stress_test(10'000); - stress_test(1'000'000'000); - performance_test(); + if (!sanitize) { + stress_test(100'000, 10); + stress_test(100'000, 10'000); + stress_test(100'000, 1'000'000'000); + performance_test(); + } else { + stress_test(10'000, 10); + stress_test(10'000, 10'000); + stress_test(10'000, 1'000'000'000); + } } diff --git a/test/geometry/polygon.cpp b/test/geometry/polygon.cpp index 29d3251..1d9f828 100644 --- a/test/geometry/polygon.cpp +++ b/test/geometry/polygon.cpp @@ -26,9 +26,9 @@ double distToSegment(pt a, pt b, pt p) { #include <geometry/polygon.cpp> #include "../geometry.h" -void test_area(ll range) { +void test_area(ll LIM, ll range) { int queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(3, 30); auto ps = Random::polygon(n, range); ps.push_back(ps[0]); @@ -49,9 +49,9 @@ bool ptLess(pt a, pt b) { return imag(a) < imag(b); } -void test_windingNumber(ll range) { +void test_windingNumber(ll LIM, ll range) { int queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(3, 8); auto ps = Random::polygon(n, range); ps.push_back(ps[0]); @@ -62,7 +62,7 @@ void test_windingNumber(ll range) { ll expected = 0; bool onBorder = false; for (int j = 0; j < n; j++) { - int cur = details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]); + int cur = details::lineSegmentIntersection(p, {real(p)+1, 1'000'000'007}, ps[j], ps[j+1]); if (ptLess(ps[j], ps[j+1])) expected -= cur; else expected += cur; onBorder |= pointOnSegment(ps[j], ps[j+1], p); @@ -79,9 +79,9 @@ void test_windingNumber(ll range) { cerr << "tested windingNumber: " << queries << endl; } -void test_inside(ll range) { +void test_inside(ll LIM, ll range) { int queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(3, 30); auto ps = Random::polygon(n, range); ps.push_back(ps[0]); @@ -92,7 +92,7 @@ void test_inside(ll range) { ll count = 0; bool onBorder = false; for (int j = 0; j < n; j++) { - count += details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]); + count += details::lineSegmentIntersection(p, {real(p)+1, 1'000'000'007}, ps[j], ps[j+1]); onBorder |= pointOnSegment(ps[j], ps[j+1], p); } bool expected = (count % 2) && !onBorder; @@ -105,9 +105,9 @@ void test_inside(ll range) { cerr << "tested inside: " << queries << endl; } -void test_insideConvex(ll range) { +void test_insideConvex(ll LIM, ll range) { int queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(3, 30); auto ps = Random::convex(n, range); @@ -145,9 +145,9 @@ bool insideOrOnConvex(pt p, const vector<pt>& hull) { return cross(hull[l], hull[r], p) >= 0; } -void test_minkowski(ll range) { +void test_minkowski(ll LIM, ll range) { int queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(3, 30); auto A = Random::convex(n, range); int m = Random::integer(3, 30); @@ -192,10 +192,10 @@ double naive_dist(const vector<pt>& ps, const vector<pt>& qs) { return res; } -void test_dist(ll range) { +void test_dist(ll LIM, ll range) { int queries = 0; int pos = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(3, 10); auto A = Random::convex(n, range / 3); int m = Random::integer(3, 10); @@ -215,9 +215,9 @@ void test_dist(ll range) { cerr << "tested dist: " << queries << " (" << pos << ")" << endl; } -void test_extremal(ll range) { +void test_extremal(ll LIM, ll range) { int queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(3, 30); auto ps = Random::convex(n, range); ps.push_back(ps[0]); @@ -238,9 +238,9 @@ void test_extremal(ll range) { cerr << "tested extremal: " << queries << endl; } -void test_intersect(ll range) { +void test_intersect(ll LIM, ll range) { int queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(3, 10); auto ps = Random::convex(n, range); ps.push_back(ps[0]); @@ -277,20 +277,21 @@ void test_intersect(ll range) { } int main() { - test_area(100); - test_area(1'000'000'000); - test_windingNumber(100); - test_windingNumber(1'000'000'000); - test_inside(100); - test_inside(1'000'000'000); - test_insideConvex(100); - test_insideConvex(1'000'000'000); - test_minkowski(100); - test_minkowski(500'000'000); - test_dist(100); - test_dist(1'000'000'000); - test_extremal(100); - test_extremal(1'000'000'000); - test_intersect(100); - test_intersect(1'000'000'000); + ll LIM = sanitize ? 4'000 : 100'000; + test_area(LIM, 100); + test_area(LIM, 1'000'000'000); + test_windingNumber(LIM, 100); + test_windingNumber(LIM, 1'000'000'000); + test_inside(LIM, 100); + test_inside(LIM, 1'000'000'000); + test_insideConvex(LIM, 100); + test_insideConvex(LIM, 1'000'000'000); + test_minkowski(LIM, 100); + test_minkowski(LIM, 500'000'000); + test_dist(LIM, 100); + test_dist(LIM, 1'000'000'000); + test_extremal(LIM, 100); + test_extremal(LIM, 1'000'000'000); + test_intersect(LIM, 100); + test_intersect(LIM, 1'000'000'000); } diff --git a/test/geometry/segmentIntersection.cpp b/test/geometry/segmentIntersection.cpp index 5271563..f48fb8a 100644 --- a/test/geometry/segmentIntersection.cpp +++ b/test/geometry/segmentIntersection.cpp @@ -84,5 +84,5 @@ void performance_test() { int main() { stress_test(100); stress_test(1'000'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/geometry/sortAround.cpp b/test/geometry/sortAround.cpp index 42ea86b..895a6d6 100644 --- a/test/geometry/sortAround.cpp +++ b/test/geometry/sortAround.cpp @@ -79,5 +79,5 @@ int main() { test_tiny(); stress_test(100); stress_test(1'000'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp index e969364..fd6326c 100644 --- a/test/graph/2sat.cpp +++ b/test/graph/2sat.cpp @@ -122,5 +122,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/LCA_sparse.cpp b/test/graph/LCA_sparse.cpp index f6eb345..f5b023f 100644 --- a/test/graph/LCA_sparse.cpp +++ b/test/graph/LCA_sparse.cpp @@ -59,5 +59,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/TSP.cpp b/test/graph/TSP.cpp index 8a67409..3b1ce94 100644 --- a/test/graph/TSP.cpp +++ b/test/graph/TSP.cpp @@ -57,11 +57,11 @@ void performance_test() { hash_t hash = 0; for (int x : got) hash += x; - if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + if (t.time > 1500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/articulationPoints.bcc.cpp b/test/graph/articulationPoints.bcc.cpp index f112338..927ceb4 100644 --- a/test/graph/articulationPoints.bcc.cpp +++ b/test/graph/articulationPoints.bcc.cpp @@ -42,9 +42,9 @@ vector<vector<int>> naiveBCC(int m) { return res; } -void stress_test_bcc() { +void stress_test_bcc(int LIM) { ll queries = 0; - for (int tries = 0; tries < 200'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer<int>(1, 30); int m = Random::integer<int>(0, max<int>(1, min<int>(300, n*(n-1) / 2 + 1))); Graph<NoData, 0, 1> g(n); @@ -74,5 +74,6 @@ void stress_test_bcc() { } int main() { - stress_test_bcc(); + stress_test_bcc(20'000); + if (!sanitize) stress_test_bcc(200'000); } diff --git a/test/graph/articulationPoints.cpp b/test/graph/articulationPoints.cpp index c06f3a3..6960f73 100644 --- a/test/graph/articulationPoints.cpp +++ b/test/graph/articulationPoints.cpp @@ -81,5 +81,5 @@ void performance_test() { int main() { stress_test_art(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/bellmannFord.cpp b/test/graph/bellmannFord.cpp index 92f1fef..dd697f7 100644 --- a/test/graph/bellmannFord.cpp +++ b/test/graph/bellmannFord.cpp @@ -9,9 +9,9 @@ namespace floydWarshall { #include <graph/floydWarshall.cpp> } -void stress_test() { +void stress_test(int LIM) { ll queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; 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))); vector<ll> potential = Random::integers<ll>(n, 0, 1'000'000'000'000ll); @@ -65,6 +65,7 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(10'000); + if (!sanitize) stress_test(100'000); + if (!sanitize) performance_test(); } diff --git a/test/graph/bitonicTSP.cpp b/test/graph/bitonicTSP.cpp.todo index 7c448a2..9d6b77d 100644 --- a/test/graph/bitonicTSP.cpp +++ b/test/graph/bitonicTSP.cpp.todo @@ -9,17 +9,25 @@ namespace expected { void stress_test() { ll queries = 0; for (int tries = 0; tries < 200'000; tries++) { - int n = Random::integer<int>(1, 30); + int n = Random::integer<int>(2, 30); vector<vector<double>> dist(n); for (auto& v : dist) v = Random::reals<double>(n, 0, 1e18); + auto eval = [&](const vector<int>& order) { + double res = 0; + for (int i = 0; i < n; i++) res += dist[order[i]][order[i+1]]; + return res; + }; + got::dist = dist; expected::dist = dist; - auto got = got::bitonicTSP(); - auto expected = got::bitonicTSP(); + auto got = eval(got::bitonicTSP()); + auto expected = eval(expected::bitonicTSP()); + std::cout << got << std::endl; + std::cout << expected << std::endl; if (got != expected) cerr << "error" << FAIL; queries += n; } @@ -45,5 +53,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/bitonicTSPsimple.cpp b/test/graph/bitonicTSPsimple.cpp.todo index c79a0ef..7e0a80b 100644 --- a/test/graph/bitonicTSPsimple.cpp +++ b/test/graph/bitonicTSPsimple.cpp.todo @@ -9,7 +9,7 @@ namespace expected { void stress_test() { ll queries = 0; for (int tries = 0; tries < 200'000; tries++) { - int n = Random::integer<int>(1, 30); + int n = Random::integer<int>(2, 30); vector<vector<double>> dist(n); for (auto& v : dist) v = Random::reals<double>(n, 0, 1e18); @@ -18,7 +18,7 @@ void stress_test() { expected::dist = dist; auto got = got::bitonicTSP(); - auto expected = got::bitonicTSP(); + auto expected = expected::bitonicTSP(); if (got != expected) cerr << "error" << FAIL; queries += n; @@ -45,5 +45,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/blossom.cpp b/test/graph/blossom.cpp index 0add7e1..56d3132 100644 --- a/test/graph/blossom.cpp +++ b/test/graph/blossom.cpp @@ -72,5 +72,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/bronKerbosch.cpp b/test/graph/bronKerbosch.cpp index e0cac22..8c0a200 100644 --- a/test/graph/bronKerbosch.cpp +++ b/test/graph/bronKerbosch.cpp @@ -69,5 +69,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/centroid.cpp b/test/graph/centroid.cpp index 633c3f1..d231c3e 100644 --- a/test/graph/centroid.cpp +++ b/test/graph/centroid.cpp @@ -73,5 +73,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp index 96dc4be..ef087e3 100644 --- a/test/graph/connect.cpp +++ b/test/graph/connect.cpp @@ -45,9 +45,9 @@ struct Naive { } }; -void stress_test() { +void stress_test(int lim) { ll queries = 0; - for (int tries = 0; tries < 2'000; tries++) { + for (int tries = 0; tries < lim; tries++) { int n = Random::integer<int>(2, 30); int m = Random::integer<int>(30, 300); @@ -135,6 +135,6 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(sanitize ? 1'000 : 2'000); + if (!sanitize) performance_test(); } diff --git a/test/graph/cycleCounting.cpp b/test/graph/cycleCounting.cpp index 82caf16..bfe313e 100644 --- a/test/graph/cycleCounting.cpp +++ b/test/graph/cycleCounting.cpp @@ -71,5 +71,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/dijkstra.cpp b/test/graph/dijkstra.cpp index 18420ac..d79e700 100644 --- a/test/graph/dijkstra.cpp +++ b/test/graph/dijkstra.cpp @@ -7,9 +7,9 @@ struct edge { }; #include <graph/bellmannFord.cpp> -void stress_test() { +void stress_test(int LIM) { ll queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; 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))); @@ -59,6 +59,7 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(10'000); + if (!sanitize) stress_test(100'000); + if (!sanitize) performance_test(); } diff --git a/test/graph/dinitzScaling.cpp b/test/graph/dinitzScaling.cpp index c06d486..0ab9718 100644 --- a/test/graph/dinitzScaling.cpp +++ b/test/graph/dinitzScaling.cpp @@ -57,5 +57,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/euler.cpp b/test/graph/euler.cpp index 353cff2..5314123 100644 --- a/test/graph/euler.cpp +++ b/test/graph/euler.cpp @@ -83,5 +83,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/floydWarshall.cpp b/test/graph/floydWarshall.cpp index 182b99b..819af39 100644 --- a/test/graph/floydWarshall.cpp +++ b/test/graph/floydWarshall.cpp @@ -9,9 +9,9 @@ namespace floydWarshall { #include <graph/floydWarshall.cpp> } -void stress_test() { +void stress_test(int LIM) { ll queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; 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))); vector<ll> potential = Random::integers<ll>(n, 0, 1'000'000'000'000ll); @@ -85,6 +85,7 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(10'000); + if (!sanitize) stress_test(100'000); + if (!sanitize) performance_test(); } diff --git a/test/graph/havelHakimi.cpp b/test/graph/havelHakimi.cpp index 9491db2..0752b85 100644 --- a/test/graph/havelHakimi.cpp +++ b/test/graph/havelHakimi.cpp @@ -61,5 +61,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/hld.cpp b/test/graph/hld.cpp index bcd9c8c..bf055f7 100644 --- a/test/graph/hld.cpp +++ b/test/graph/hld.cpp @@ -79,5 +79,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/hopcroftKarp.cpp b/test/graph/hopcroftKarp.cpp index df2cec2..c446c99 100644 --- a/test/graph/hopcroftKarp.cpp +++ b/test/graph/hopcroftKarp.cpp @@ -70,5 +70,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/kruskal.cpp b/test/graph/kruskal.cpp index bc1cce5..157a2f4 100644 --- a/test/graph/kruskal.cpp +++ b/test/graph/kruskal.cpp @@ -86,5 +86,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/kuhn.cpp b/test/graph/kuhn.cpp index 8b7e13b..0a6a9a4 100644 --- a/test/graph/kuhn.cpp +++ b/test/graph/kuhn.cpp @@ -70,5 +70,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/matching.cpp b/test/graph/matching.cpp index 9e3ad85..d737954 100644 --- a/test/graph/matching.cpp +++ b/test/graph/matching.cpp @@ -58,5 +58,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/maxWeightBipartiteMatching.cpp b/test/graph/maxWeightBipartiteMatching.cpp index d245405..be38d8c 100644 --- a/test/graph/maxWeightBipartiteMatching.cpp +++ b/test/graph/maxWeightBipartiteMatching.cpp @@ -55,5 +55,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/minCostMaxFlow.cpp b/test/graph/minCostMaxFlow.cpp index 8c92aa7..a070f51 100644 --- a/test/graph/minCostMaxFlow.cpp +++ b/test/graph/minCostMaxFlow.cpp @@ -64,5 +64,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/pushRelabel.cpp b/test/graph/pushRelabel.cpp index 42c2e57..ca50860 100644 --- a/test/graph/pushRelabel.cpp +++ b/test/graph/pushRelabel.cpp @@ -57,5 +57,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp index 93f946b..c7c4608 100644 --- a/test/graph/reroot.cpp +++ b/test/graph/reroot.cpp @@ -55,5 +55,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp index bc52d7e..ebd3af0 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -74,5 +74,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/stoerWagner.cpp b/test/graph/stoerWagner.cpp index e7a1075..3b67aac 100644 --- a/test/graph/stoerWagner.cpp +++ b/test/graph/stoerWagner.cpp @@ -77,5 +77,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/treeIsomorphism.cpp b/test/graph/treeIsomorphism.cpp index 4daa373..1594016 100644 --- a/test/graph/treeIsomorphism.cpp +++ b/test/graph/treeIsomorphism.cpp @@ -122,5 +122,5 @@ int main() { stress_test_eq(); test_tiny(); stress_test_neq(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp index 0bd71d9..556ba7b 100644 --- a/test/graph/virtualTree.cpp +++ b/test/graph/virtualTree.cpp @@ -91,5 +91,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/berlekampMassey.cpp b/test/math/berlekampMassey.cpp index a9d5709..93832b0 100644 --- a/test/math/berlekampMassey.cpp +++ b/test/math/berlekampMassey.cpp @@ -63,6 +63,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/bigint.cpp b/test/math/bigint.cpp index 538d0dc..2d75343 100644 --- a/test/math/bigint.cpp +++ b/test/math/bigint.cpp @@ -35,9 +35,9 @@ struct modInt { constexpr ll MOD = 1'394'633'899; constexpr ll POOL = 8; -void stress_test() { +void stress_test(int LIM) { int queries = 0; - for (int tries = 0; tries < 1000; tries++) { + for (int tries = 0; tries < LIM; tries++) { vector<modInt<MOD>> expectedPool(POOL); vector<bigint> gotPool(POOL); for (int i = 0; i < POOL; i++) { @@ -117,6 +117,7 @@ void stress_test() { } int main() { - stress_test(); + stress_test(100); + if (!sanitize) stress_test(1000); } diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp index 1694589..2ba3525 100644 --- a/test/math/cycleDetection.cpp +++ b/test/math/cycleDetection.cpp @@ -41,6 +41,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/discreteLogarithm.cpp b/test/math/discreteLogarithm.cpp index 0f9eecf..6e87e59 100644 --- a/test/math/discreteLogarithm.cpp +++ b/test/math/discreteLogarithm.cpp @@ -59,6 +59,6 @@ int main() { stress_test([](ll p){return sqrtl(p);}); stress_test([](ll p){return min<ll>(10, p - 1);}); stress_test([](ll p){return min<ll>(p - 1, sqrtl(p) + 100);}); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/discreteNthRoot.cpp b/test/math/discreteNthRoot.cpp index d595e6d..e64293c 100644 --- a/test/math/discreteNthRoot.cpp +++ b/test/math/discreteNthRoot.cpp @@ -73,6 +73,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/divSum.cpp b/test/math/divSum.cpp index 1f82387..a366e53 100644 --- a/test/math/divSum.cpp +++ b/test/math/divSum.cpp @@ -43,6 +43,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/divisors.cpp b/test/math/divisors.cpp index 2402d2a..4cc7e70 100644 --- a/test/math/divisors.cpp +++ b/test/math/divisors.cpp @@ -60,6 +60,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/extendedEuclid.cpp b/test/math/extendedEuclid.cpp index 597f722..07e4882 100644 --- a/test/math/extendedEuclid.cpp +++ b/test/math/extendedEuclid.cpp @@ -32,8 +32,10 @@ void stress_test() { queries++; } cerr << "tested random queries: " << queries << endl; - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms" << endl; + if (!sanitize) { + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; + } } int main() { diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp index eb8f641..21a5736 100644 --- a/test/math/gauss.cpp +++ b/test/math/gauss.cpp @@ -114,5 +114,5 @@ void performance_test() { int main() { test_tiny(); stress_test_inv(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/goldenSectionSearch.cpp b/test/math/goldenSectionSearch.cpp index 565a21c..ff2d067 100644 --- a/test/math/goldenSectionSearch.cpp +++ b/test/math/goldenSectionSearch.cpp @@ -69,6 +69,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/inversions.cpp b/test/math/inversions.cpp index fc825e4..86d87d0 100644 --- a/test/math/inversions.cpp +++ b/test/math/inversions.cpp @@ -37,6 +37,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp index 7d1b0d7..ab1c62e 100644 --- a/test/math/inversionsMerge.cpp +++ b/test/math/inversionsMerge.cpp @@ -41,6 +41,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/kthperm.cpp b/test/math/kthperm.cpp index 1b3e803..ca95699 100644 --- a/test/math/kthperm.cpp +++ b/test/math/kthperm.cpp @@ -1,9 +1,9 @@ #include "../util.h" #include <math/kthperm.cpp> -void stress_test() { +void stress_test(int LIM) { ll queries = 0; - for (ll i = 0; i < 10'000; i++) { + for (int i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); vector<ll> expected(n); iota(begin(expected), end(expected), 0); @@ -31,7 +31,8 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(1'000); + if (!sanitize) stress_test(10'000); + if (!sanitize) performance_test(); } diff --git a/test/math/legendre.cpp b/test/math/legendre.cpp index f210b57..44f88c1 100644 --- a/test/math/legendre.cpp +++ b/test/math/legendre.cpp @@ -38,6 +38,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp index 376a067..d8967a0 100644 --- a/test/math/lgsFp.cpp +++ b/test/math/lgsFp.cpp @@ -108,5 +108,5 @@ void performance_test() { int main() { test_square(); stress_test_inv(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/linearCongruence.cpp b/test/math/linearCongruence.cpp index ba8eeac..fa01a06 100644 --- a/test/math/linearCongruence.cpp +++ b/test/math/linearCongruence.cpp @@ -48,6 +48,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index 79607ac..a2ac01d 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -54,6 +54,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/linearRecurrenceNTT.cpp b/test/math/linearRecurrenceNTT.cpp index 922d965..f7615d6 100644 --- a/test/math/linearRecurrenceNTT.cpp +++ b/test/math/linearRecurrenceNTT.cpp @@ -55,6 +55,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/linearRecurrenceOld.cpp b/test/math/linearRecurrenceOld.cpp index 70609f0..b3d1611 100644 --- a/test/math/linearRecurrenceOld.cpp +++ b/test/math/linearRecurrenceOld.cpp @@ -49,6 +49,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/linearSieve.cpp b/test/math/linearSieve.cpp index 527e729..1a5286f 100644 --- a/test/math/linearSieve.cpp +++ b/test/math/linearSieve.cpp @@ -59,8 +59,10 @@ void performance_test() { sieve(); hash_t hash = ssize(primes); t.stop(); - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; + if (!sanitize) { + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; + } } int main() { diff --git a/test/math/longestIncreasingSubsequence.cpp b/test/math/longestIncreasingSubsequence.cpp index befee75..5bc3936 100644 --- a/test/math/longestIncreasingSubsequence.cpp +++ b/test/math/longestIncreasingSubsequence.cpp @@ -30,9 +30,9 @@ vector<int> naive(const vector<ll>& a) { return res; } -void stress_test() { +void stress_test(ll LIM) { ll queries = 0; - for (ll i = 0; i < 10'000; i++) { + for (ll i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 12); auto a = Random::integers<ll>(n, -10, 10); auto expected = naive<true>(a); @@ -40,7 +40,7 @@ void stress_test() { if (got != expected) cerr << "error: strict" << FAIL; queries += n; } - for (ll i = 0; i < 10'000; i++) { + for (ll i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 12); auto a = Random::integers<ll>(n, -10, 10); auto expected = naive<false>(a); @@ -70,6 +70,7 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(1'000); + if (!sanitize) stress_test(10'000); + if (!sanitize) performance_test(); } diff --git a/test/math/matrixPower.cpp b/test/math/matrixPower.cpp index 169ff06..083dded 100644 --- a/test/math/matrixPower.cpp +++ b/test/math/matrixPower.cpp @@ -111,6 +111,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/millerRabin.base32.cpp b/test/math/millerRabin.base32.cpp index 8c2c79a..e9a4b57 100644 --- a/test/math/millerRabin.base32.cpp +++ b/test/math/millerRabin.base32.cpp @@ -132,6 +132,6 @@ void performance_test() { int main() { extra_tests(); stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/millerRabin.cpp b/test/math/millerRabin.cpp index 725b744..e7feba1 100644 --- a/test/math/millerRabin.cpp +++ b/test/math/millerRabin.cpp @@ -124,6 +124,6 @@ void performance_test() { int main() { extra_tests(); stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/minMod.cpp b/test/math/minMod.cpp index e49da11..39affb4 100644 --- a/test/math/minMod.cpp +++ b/test/math/minMod.cpp @@ -86,7 +86,7 @@ void performance_test_firstVal() { int main() { stress_test_minMod(); stress_test_firstVal(); - performance_test_minMod(); - performance_test_firstVal(); + if (!sanitize) performance_test_minMod(); + if (!sanitize) performance_test_firstVal(); } diff --git a/test/math/modMulIterativ.cpp b/test/math/modMulIterativ.cpp index 4f794c5..7783026 100644 --- a/test/math/modMulIterativ.cpp +++ b/test/math/modMulIterativ.cpp @@ -14,7 +14,7 @@ void stress_test() { k++; expected = (expected + a) % n; } while (k < 100); - queries += n; + queries++; } cerr << "tested queries: " << queries << endl; } @@ -28,7 +28,7 @@ void stress_test_large() { ll expected = (lll)a * b % n; auto got = mulMod(a, b, n); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - queries += n; + queries++; } cerr << "tested queries: " << queries << endl; } @@ -52,6 +52,6 @@ void performance_test() { int main() { stress_test(); stress_test_large(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/modPowIterativ.cpp b/test/math/modPowIterativ.cpp index 2cf0eb4..29ea4c5 100644 --- a/test/math/modPowIterativ.cpp +++ b/test/math/modPowIterativ.cpp @@ -37,6 +37,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/multInv.cpp b/test/math/multInv.cpp index 93763c5..a6c37a1 100644 --- a/test/math/multInv.cpp +++ b/test/math/multInv.cpp @@ -35,6 +35,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/permIndex.cpp b/test/math/permIndex.cpp index d68ba3a..2f19985 100644 --- a/test/math/permIndex.cpp +++ b/test/math/permIndex.cpp @@ -1,9 +1,9 @@ #include "../util.h" #include <math/permIndex.cpp> -void stress_test() { +void stress_test(int LIM) { ll queries = 0; - for (ll i = 0; i < 10'000; i++) { + for (int i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); vector<ll> cur(n); iota(begin(cur), end(cur), 0); @@ -32,7 +32,8 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(1'000); + if (!sanitize) stress_test(10'000); + if (!sanitize) performance_test(); } diff --git a/test/math/piLegendre.cpp b/test/math/piLegendre.cpp index c3513bf..53c459c 100644 --- a/test/math/piLegendre.cpp +++ b/test/math/piLegendre.cpp @@ -34,7 +34,7 @@ void performance_test() { int main() { lehmer::init(); - performance_test(); + if (!sanitize) performance_test(); stress_test(); } diff --git a/test/math/piLehmer.cpp b/test/math/piLehmer.cpp index d84466f..bfc714f 100644 --- a/test/math/piLehmer.cpp +++ b/test/math/piLehmer.cpp @@ -36,7 +36,8 @@ void performance_test() { } int main() { - performance_test(); + if (!sanitize) performance_test(); + if (sanitize) lehmer::init(); stress_test(); } diff --git a/test/math/primeSieve.cpp b/test/math/primeSieve.cpp index 6bb63f6..52570e2 100644 --- a/test/math/primeSieve.cpp +++ b/test/math/primeSieve.cpp @@ -36,8 +36,10 @@ void performance_test() { primeSieve(); hash_t hash = ssize(primes); t.stop(); - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; + if (!sanitize) { + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; + } } int main() { diff --git a/test/math/recover.cpp b/test/math/recover.cpp index 6f89e5a..9b61653 100644 --- a/test/math/recover.cpp +++ b/test/math/recover.cpp @@ -35,8 +35,10 @@ void stress_test() { } } cerr << "tested random queries: " << queries << endl; - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms" << endl; + if (!sanitize) { + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; + } } int main() { diff --git a/test/math/rho.cpp b/test/math/rho.cpp index 941524b..9943a8c 100644 --- a/test/math/rho.cpp +++ b/test/math/rho.cpp @@ -120,6 +120,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/shortModInv.cpp b/test/math/shortModInv.cpp index 565989c..5e74907 100644 --- a/test/math/shortModInv.cpp +++ b/test/math/shortModInv.cpp @@ -34,6 +34,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/simpson.cpp b/test/math/simpson.cpp index d7cdba3..019caca 100644 --- a/test/math/simpson.cpp +++ b/test/math/simpson.cpp @@ -53,8 +53,10 @@ void stress_test() { queries++; } } - if (t.time > 5000) cerr << "too slow: " << t.time << FAIL; - cerr << "tested random queries: " << queries << " (" << t.time << "ms)" << endl; + if (!sanitize) { + if (t.time > 5000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested random queries: " << queries << " (" << t.time << "ms)" << endl; + } } int main() { diff --git a/test/math/sqrtModCipolla.cpp b/test/math/sqrtModCipolla.cpp index 26d975b..c7be9a4 100644 --- a/test/math/sqrtModCipolla.cpp +++ b/test/math/sqrtModCipolla.cpp @@ -43,6 +43,6 @@ void performance_test() { int main() { stress_test(1'000); stress_test(1'000'000'000); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/andTransform.cpp b/test/math/transforms/andTransform.cpp index fa029f6..eef57bf 100644 --- a/test/math/transforms/andTransform.cpp +++ b/test/math/transforms/andTransform.cpp @@ -33,6 +33,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/bitwiseTransforms.cpp b/test/math/transforms/bitwiseTransforms.cpp index 132740c..79fe120 100644 --- a/test/math/transforms/bitwiseTransforms.cpp +++ b/test/math/transforms/bitwiseTransforms.cpp @@ -33,6 +33,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/fft.cpp b/test/math/transforms/fft.cpp index 66df1bf..aa7ddd2 100644 --- a/test/math/transforms/fft.cpp +++ b/test/math/transforms/fft.cpp @@ -46,6 +46,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/fftMul.cpp b/test/math/transforms/fftMul.cpp index 7887a5e..38e7c73 100644 --- a/test/math/transforms/fftMul.cpp +++ b/test/math/transforms/fftMul.cpp @@ -57,6 +57,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/multiplyBitwise.cpp b/test/math/transforms/multiplyBitwise.cpp index 8b9eb2f..f460204 100644 --- a/test/math/transforms/multiplyBitwise.cpp +++ b/test/math/transforms/multiplyBitwise.cpp @@ -50,6 +50,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/multiplyFFT.cpp b/test/math/transforms/multiplyFFT.cpp index 61040d0..f11ec45 100644 --- a/test/math/transforms/multiplyFFT.cpp +++ b/test/math/transforms/multiplyFFT.cpp @@ -50,6 +50,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/multiplyNTT.cpp b/test/math/transforms/multiplyNTT.cpp index 6424c50..48a1aa3 100644 --- a/test/math/transforms/multiplyNTT.cpp +++ b/test/math/transforms/multiplyNTT.cpp @@ -51,6 +51,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/ntt.cpp b/test/math/transforms/ntt.cpp index cd32073..533d086 100644 --- a/test/math/transforms/ntt.cpp +++ b/test/math/transforms/ntt.cpp @@ -34,6 +34,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/orTransform.cpp b/test/math/transforms/orTransform.cpp index 0ec9155..b1fdfad 100644 --- a/test/math/transforms/orTransform.cpp +++ b/test/math/transforms/orTransform.cpp @@ -33,6 +33,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/math/transforms/seriesOperations.cpp b/test/math/transforms/seriesOperations.cpp index f78541d..1242537 100644 --- a/test/math/transforms/seriesOperations.cpp +++ b/test/math/transforms/seriesOperations.cpp @@ -63,9 +63,9 @@ namespace reference {//checked against yosupo } } -void test_inv() { +void test_inv(ll LIM) { ll queries = 0; - for (ll i = 0; i < 50'000; i++) { + for (ll i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); int m = Random::integer<int>(1, 100); vector<ll> a = Random::integers<ll>(n, 0, mod); @@ -78,9 +78,9 @@ void test_inv() { cerr << "tested inv: " << queries << endl; } -void test_deriv() { +void test_deriv(ll LIM) { ll queries = 0; - for (ll i = 0; i < 50'000; i++) { + for (ll i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); vector<ll> a = Random::integers<ll>(n, 0, mod); @@ -92,9 +92,9 @@ void test_deriv() { cerr << "tested deriv: " << queries << endl; } -void test_integr() { +void test_integr(ll LIM) { ll queries = 0; - for (ll i = 0; i < 50'000; i++) { + for (ll i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); vector<ll> a = Random::integers<ll>(n, 0, mod); @@ -106,9 +106,9 @@ void test_integr() { cerr << "tested integr: " << queries << endl; } -void test_log() { +void test_log(ll LIM) { ll queries = 0; - for (ll i = 0; i < 50'000; i++) { + for (ll i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); int m = Random::integer<int>(1, 100); vector<ll> a = Random::integers<ll>(n, 0, mod); @@ -121,9 +121,9 @@ void test_log() { cerr << "tested log: " << queries << endl; } -void test_exp() { +void test_exp(ll LIM) { ll queries = 0; - for (ll i = 0; i < 50'000; i++) { + for (ll i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); int m = Random::integer<int>(1, 100); vector<ll> a = Random::integers<ll>(n, 0, mod); @@ -137,9 +137,10 @@ void test_exp() { } int main() { - test_inv(); - test_deriv(); - test_integr(); - test_log(); - test_exp(); + ll LIM = sanitize ? 5'000 : 50'000; + test_inv(LIM); + test_deriv(LIM); + test_integr(LIM); + test_log(LIM); + test_exp(LIM); } diff --git a/test/math/transforms/xorTransform.cpp b/test/math/transforms/xorTransform.cpp index 17b0f6f..630331a 100644 --- a/test/math/transforms/xorTransform.cpp +++ b/test/math/transforms/xorTransform.cpp @@ -33,6 +33,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/other/bitOps.cpp b/test/other/bitOps.cpp index 2250521..adaa49a 100644 --- a/test/other/bitOps.cpp +++ b/test/other/bitOps.cpp @@ -27,13 +27,13 @@ void test_subsets() { ll naive(ll x) { vector<ll> bits; - for (ll i = 0; i < 64; i++) { + for (ll i = 0; i < 63; i++) { bits.push_back(x & 1); x >>= 1; } ranges::next_permutation(bits | views::reverse); x = 0; - for (ll i = 0, j = 1; i < 64; i++, j <<= 1) { + for (ll i = 0, j = 1; i < 63; i++, j <<= 1) { if (bits[i] != 0) x |= j; } return x; diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp index 6d1b444..3878758 100644 --- a/test/other/divideAndConquer.cpp +++ b/test/other/divideAndConquer.cpp @@ -98,6 +98,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/other/fastSubsetSum.cpp b/test/other/fastSubsetSum.cpp index c61b1ea..ea40184 100644 --- a/test/other/fastSubsetSum.cpp +++ b/test/other/fastSubsetSum.cpp @@ -44,6 +44,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/other/josephus2.cpp b/test/other/josephus2.cpp index f2c0440..074b481 100644 --- a/test/other/josephus2.cpp +++ b/test/other/josephus2.cpp @@ -37,6 +37,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/other/josephusK.cpp b/test/other/josephusK.cpp index 1a5aa9d..dab291b 100644 --- a/test/other/josephusK.cpp +++ b/test/other/josephusK.cpp @@ -38,6 +38,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/other/knuth.cpp b/test/other/knuth.cpp index aaf5059..3d6cb9b 100644 --- a/test/other/knuth.cpp +++ b/test/other/knuth.cpp @@ -98,6 +98,6 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/other/pbs.cpp b/test/other/pbs.cpp index e1dfea0..4a8da2e 100644 --- a/test/other/pbs.cpp +++ b/test/other/pbs.cpp @@ -93,11 +93,11 @@ void performance_test() { t.stop(); ll hash = accumulate(begin(ans), end(ans), 0LL); - if (t.time > 700) cerr << "too slow: " << t.time << FAIL; + if (t.time > 900) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/ahoCorasick.cpp b/test/string/ahoCorasick.cpp index c3361d6..3203855 100644 --- a/test/string/ahoCorasick.cpp +++ b/test/string/ahoCorasick.cpp @@ -72,5 +72,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/deBruijn.cpp b/test/string/deBruijn.cpp index eb82b59..6bbbad9 100644 --- a/test/string/deBruijn.cpp +++ b/test/string/deBruijn.cpp @@ -39,5 +39,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/duval.cpp b/test/string/duval.cpp index 5ebc96c..88e2fb7 100644 --- a/test/string/duval.cpp +++ b/test/string/duval.cpp @@ -79,7 +79,7 @@ void performance_test_minrotation() { int main() { stress_test_duval(); - performance_test_duval(); + if (!sanitize) performance_test_duval(); stress_test_minrotation(); - performance_test_minrotation(); + if (!sanitize) performance_test_minrotation(); } diff --git a/test/string/kmp.cpp b/test/string/kmp.cpp index 2364efd..8ebeb64 100644 --- a/test/string/kmp.cpp +++ b/test/string/kmp.cpp @@ -78,8 +78,8 @@ void performance_test_kmp() { int main() { cerr << "preprocessing:" << endl; stress_test_preprocessing(); - performance_test_preprocessing(); + if (!sanitize) performance_test_preprocessing(); cerr << "kmp:" << endl; stress_test_kmp(); - performance_test_kmp(); + if (!sanitize) performance_test_kmp(); } diff --git a/test/string/longestCommonSubsequence.cpp b/test/string/longestCommonSubsequence.cpp index 128c3c1..8c32d61 100644 --- a/test/string/longestCommonSubsequence.cpp +++ b/test/string/longestCommonSubsequence.cpp @@ -51,5 +51,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/lyndon.cpp b/test/string/lyndon.cpp index 6710973..154ba66 100644 --- a/test/string/lyndon.cpp +++ b/test/string/lyndon.cpp @@ -57,5 +57,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/manacher.cpp b/test/string/manacher.cpp index 803154b..ada0486 100644 --- a/test/string/manacher.cpp +++ b/test/string/manacher.cpp @@ -45,5 +45,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/rollingHash.cpp b/test/string/rollingHash.cpp index a9dace5..d19a153 100644 --- a/test/string/rollingHash.cpp +++ b/test/string/rollingHash.cpp @@ -37,13 +37,13 @@ void testTiny() { cerr << "tiny: ok" << endl; } -void testSmall() { +void testSmall(int depth) { set<decltype(getHash(""))> got; ll expected = 0; auto dfs = [&](auto&& self, string pref)->void { expected++; got.insert(getHash(pref)); - if(ssize(pref) >= 5) return; + if(ssize(pref) >= depth) return; for (char c = 'a'; c <= 'z'; c++) { self(self, pref + c); } @@ -86,7 +86,7 @@ void performance_test() { int main() { testThueMorse(); testTiny(); - testSmall(); + testSmall(sanitize ? 4 : 5); stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/rollingHashCf.cpp b/test/string/rollingHashCf.cpp index f7ce357..d0f90aa 100644 --- a/test/string/rollingHashCf.cpp +++ b/test/string/rollingHashCf.cpp @@ -39,13 +39,13 @@ void testTiny() { cerr << "tiny: ok" << endl; } -void testSmall() { +void testSmall(int depth) { set<decltype(getHash(""))> got; ll expected = 0; auto dfs = [&](auto&& self, string pref)->void { expected++; got.insert(getHash(pref)); - if(ssize(pref) >= 5) return; + if(ssize(pref) >= depth) return; for (char c = 'a'; c <= 'z'; c++) { self(self, pref + c); } @@ -88,7 +88,7 @@ void performance_test() { int main() { testThueMorse(); testTiny(); - testSmall(); + testSmall(sanitize ? 4 : 5); stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/suffixArray.cpp b/test/string/suffixArray.cpp index a1db190..37049f6 100644 --- a/test/string/suffixArray.cpp +++ b/test/string/suffixArray.cpp @@ -57,5 +57,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/suffixAutomaton.cpp b/test/string/suffixAutomaton.cpp index cab555e..dacbb83 100644 --- a/test/string/suffixAutomaton.cpp +++ b/test/string/suffixAutomaton.cpp @@ -58,5 +58,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/suffixTree.cpp b/test/string/suffixTree.cpp index 69c24fe..6f3d912 100644 --- a/test/string/suffixTree.cpp +++ b/test/string/suffixTree.cpp @@ -46,5 +46,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/trie.cpp b/test/string/trie.cpp index 45d89cf..ea4a774 100644 --- a/test/string/trie.cpp +++ b/test/string/trie.cpp @@ -30,7 +30,8 @@ void stress_test() { constexpr int N = 10'000; void performance_test() { timer t; - trie = {node()}; + trie.clear(); + trie.emplace_back(); hash_t hash = 0; for (int tries = 0; tries < N; tries++) { { @@ -54,5 +55,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/string/z.cpp b/test/string/z.cpp index 3c76939..a11984a 100644 --- a/test/string/z.cpp +++ b/test/string/z.cpp @@ -37,5 +37,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/util.h b/test/util.h index e0d9b57..880ff04 100644 --- a/test/util.h +++ b/test/util.h @@ -1,6 +1,12 @@ #include <bits/stdc++.h> using namespace std; +#ifdef SANITIZE + constexpr bool sanitize = true; +#else + constexpr bool sanitize = false; +#endif + using ll = long long; using lll = __int128; using ld = long double; @@ -10,6 +16,7 @@ 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); @@ -17,6 +24,7 @@ T _lg_check(T n) { } #define __lg _lg_check +#endif namespace details { template<typename T = ll> |