summaryrefslogtreecommitdiff
path: root/test/other
diff options
context:
space:
mode:
Diffstat (limited to 'test/other')
-rw-r--r--test/other/compiletime.cpp2
-rw-r--r--test/other/divideAndConquer.cpp103
-rw-r--r--test/other/fastIO.cpp32
-rw-r--r--test/other/fastIO.in2
-rw-r--r--test/other/josephus2.cpp42
-rw-r--r--test/other/josephusK.cpp43
-rw-r--r--test/other/knuth.cpp103
-rw-r--r--test/other/sos.cpp50
-rw-r--r--test/other/split.cpp24
9 files changed, 401 insertions, 0 deletions
diff --git a/test/other/compiletime.cpp b/test/other/compiletime.cpp
new file mode 100644
index 0000000..591669d
--- /dev/null
+++ b/test/other/compiletime.cpp
@@ -0,0 +1,2 @@
+#include <other/compiletime.cpp>
+int main() {} \ No newline at end of file
diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp
new file mode 100644
index 0000000..a6fda9d
--- /dev/null
+++ b/test/other/divideAndConquer.cpp
@@ -0,0 +1,103 @@
+#include "../util.h"
+constexpr ll inf = LL::INF;
+#include <other/divideAndConquer.cpp>
+
+vector<vector<ll>> gen(int n) {
+ vector<vector<ll>> res(n, vector<ll>(n));
+ ll mi = 0;
+ for (ll a = n-1; a >= 0; a--) {
+ for (ll c = n-1; c >= a; c--) {
+ for (ll b = a; b <= c; b++) {
+ for (ll d = c; d < n; d++) {
+ res[a][c] = min(res[a][c], res[a][d] + res[b][c] - res[b][d]);
+ }
+ }
+ res[a][c] -= Random::integer<ll>(0, 1000);
+ mi = min(mi, res[a][c]);
+ }
+ }
+ for (auto& v : res) for (auto& x : v) x -= mi;
+
+ for (ll a = 0; a < n; a++) {
+ for (ll b = a; b < n; b++) {
+ for (ll c = b; c < n; c++) {
+ for (ll d = c; d < n; d++) {
+ if (res[a][d] < 0 || res[a][d] + res[b][c] < res[a][c] + res[b][d]) {
+ cerr << "invalid C array!" << FAIL;
+ }
+ }
+ }
+ }
+ }
+ return res;
+}
+
+vector<vector<ll>> genQuick(int n) {
+ vector<vector<ll>> res(n, vector<ll>(n));
+ for (ll a = n-1; a >= 0; a--) {
+ for (ll c = n-1; c >= a; c--) {
+ res[a][c] = (c-a) * (c - a) + Random::integer<ll>(0, 2);
+ }
+ }
+ return res;
+}
+
+/*ll naive(int n, int m) {
+ vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+ state[0][0] = 0;
+ for (int i = 1; i <= m; i++) {
+ for (int j = 1; j <= n; j++) {
+ for (int k = 1; k <= j; k++) {
+ state[i][j] = min(state[i][j], state[i-1][k-1] + C[k-1][j-1]);
+ }
+ }
+ }
+ return state[m][n];
+}*/
+
+vector<ll> naive(int n) {
+ vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+ state[0][0] = 0;
+ vector<ll> res(n+1, inf);
+ for (int i = 1; i <= n; i++) {
+ for (int j = 1; j <= n; j++) {
+ for (int k = 1; k <= j; k++) {
+ state[i][j] = min(state[i][j], state[i-1][k-1] + C[k-1][j-1]);
+ }
+ }
+ res[i] = state[i][n];
+ }
+ return res;
+}
+
+void stress_test() {
+ ll tests = 0;
+ for (ll i = 0; i < 1000; i++) {
+ auto n = Random::integer(10, 20);
+ C = gen(n);
+ auto expected = naive(n);
+ for (ll m = 1; m <= n; m++) {
+ auto got = calc(n, m);
+ if (got != expected[m]) cerr << "got: " << got << ", expected: " << expected[m] << FAIL;
+ tests++;
+ }
+ }
+ cerr << "tested random queries: " << tests << endl;
+}
+
+constexpr int N = 10'000;
+void performance_test() {
+ timer t;
+ C = genQuick(N);
+ t.start();
+ auto hash = calc(N, 32);
+ t.stop();
+ if (t.time > 50) 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/other/fastIO.cpp b/test/other/fastIO.cpp
new file mode 100644
index 0000000..765ddba
--- /dev/null
+++ b/test/other/fastIO.cpp
@@ -0,0 +1,32 @@
+#include "../util.h"
+#include <other/fastIO.cpp>
+
+int main() {
+ if (freopen("other/fastIO.in", "r", stdin) == nullptr) cerr << "fastIO.in not found" << FAIL;
+ vector<int> got(5);
+ vector<int> expected = {4, 7, 3, 6, 9};
+ for (int& x : got) fastscan(x);
+ if (got != expected) cerr << "failed fastscan" << FAIL;
+
+ if (freopen("other/fastIO.out", "w", stdout) == nullptr) cerr << "fastIO.out not writebale" << FAIL;
+ fastprint(0);
+ putchar('\n');
+ fastprint(-1);
+ putchar(' ');
+ fastprint(-8321648);
+ putchar(' ');
+ fastprint(1);
+ putchar(' ');
+ fastprint(42387);
+ putchar('\n');
+ fclose(stdout);
+
+ stringstream buffer;
+ {
+ ifstream tmp("other/fastIO.out");
+ buffer << tmp.rdbuf();
+ }
+ if (buffer.str() != "0\n-1 -8321648 1 42387\n") cerr << "failed fastprint" << FAIL;
+ cerr << "done" << endl;
+}
+
diff --git a/test/other/fastIO.in b/test/other/fastIO.in
new file mode 100644
index 0000000..45594a4
--- /dev/null
+++ b/test/other/fastIO.in
@@ -0,0 +1,2 @@
+4 7
+3 6 9 \ No newline at end of file
diff --git a/test/other/josephus2.cpp b/test/other/josephus2.cpp
new file mode 100644
index 0000000..d28fe0d
--- /dev/null
+++ b/test/other/josephus2.cpp
@@ -0,0 +1,42 @@
+#include "../util.h"
+#include <other/josephus2.cpp>
+
+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)) {
+ state.erase(state.begin() + i);
+ }
+ return state[0];
+}
+
+void stress_test() {
+ ll tests = 0;
+ for (ll i = 1; i < 2'000; i++) {
+ auto got = rotateLeft(i);
+ auto expected = naive<1>(i, 2);
+ if (got != expected) cerr << "error: " << i << FAIL;
+ tests++;
+ }
+ cerr << "tested queries: " << tests << endl;
+}
+
+constexpr int N = 1'000'000'000;
+void performance_test() {
+ timer t;
+ hash_t hash = 0;
+ t.start();
+ for (ll i = 0; i < N; i++) {
+ hash += rotateLeft(1'000'000'000'000'000'000ll + i);
+ }
+ t.stop();
+ if (t.time > 500) 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/other/josephusK.cpp b/test/other/josephusK.cpp
new file mode 100644
index 0000000..e837640
--- /dev/null
+++ b/test/other/josephusK.cpp
@@ -0,0 +1,43 @@
+#include "../util.h"
+#include <other/josephus2.cpp>
+#include <other/josephusK.cpp>
+
+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)) {
+ state.erase(state.begin() + i);
+ }
+ return state[0];
+}
+
+void stress_test() {
+ ll tests = 0;
+ for (ll i = 1; i < 500; i++) {
+ for (ll j = 1; j <= i; j++) {
+ auto got = josephus(i, j);
+ auto expected = naive<0>(i, j);
+ if (got != expected) cerr << "error: " << i << FAIL;
+ tests++;
+ }
+ }
+ cerr << "tested queries: " << tests << endl;
+}
+
+constexpr int N = 10'000'000;
+void performance_test() {
+ timer t;
+ hash_t hash = 0;
+ t.start();
+ hash += josephus(N, N/2);
+ t.stop();
+ if (t.time > 500) 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/other/knuth.cpp b/test/other/knuth.cpp
new file mode 100644
index 0000000..d469ceb
--- /dev/null
+++ b/test/other/knuth.cpp
@@ -0,0 +1,103 @@
+#include "../util.h"
+constexpr ll inf = LL::INF;
+#include <other/knuth.cpp>
+
+vector<vector<ll>> gen(int n) {
+ vector<vector<ll>> res(n, vector<ll>(n));
+ ll mi = 0;
+ for (ll a = n-1; a >= 0; a--) {
+ for (ll c = n-1; c >= a; c--) {
+ for (ll b = a; b <= c; b++) {
+ for (ll d = c; d < n; d++) {
+ res[a][c] = min(res[a][c], res[a][d] + res[b][c] - res[b][d]);
+ }
+ }
+ res[a][c] -= Random::integer<ll>(0, 1000);
+ mi = min(mi, res[a][c]);
+ }
+ }
+ for (auto& v : res) for (auto& x : v) x -= mi;
+
+ for (ll a = 0; a < n; a++) {
+ for (ll b = a; b < n; b++) {
+ for (ll c = b; c < n; c++) {
+ for (ll d = c; d < n; d++) {
+ if (res[a][d] < 0 || res[a][d] + res[b][c] < res[a][c] + res[b][d]) {
+ cerr << "invalid C array!" << FAIL;
+ }
+ }
+ }
+ }
+ }
+ return res;
+}
+
+vector<vector<ll>> genQuick(int n) {
+ vector<vector<ll>> res(n, vector<ll>(n));
+ for (ll a = n-1; a >= 0; a--) {
+ for (ll c = n-1; c >= a; c--) {
+ res[a][c] = (c-a) * (c - a) + Random::integer<ll>(0, 2);
+ }
+ }
+ return res;
+}
+
+/*ll naive(int n, int m, const vector<vector<ll>>& C) {
+ vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+ state[0][0] = 0;
+ for (int i = 1; i <= m; i++) {
+ for (int j = 1; j <= n; j++) {
+ for (int k = 1; k <= j; k++) {
+ state[i][j] = min(state[i][j], state[i-1][k-1] + C[k-1][j-1]);
+ }
+ }
+ }
+ return state[m][n];
+}*/
+
+vector<ll> naive(int n, const vector<vector<ll>>& C) {
+ vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+ state[0][0] = 0;
+ vector<ll> res(n+1, inf);
+ for (int i = 1; i <= n; i++) {
+ for (int j = 1; j <= n; j++) {
+ for (int k = 1; k <= j; k++) {
+ state[i][j] = min(state[i][j], state[i-1][k-1] + C[k-1][j-1]);
+ }
+ }
+ res[i] = state[i][n];
+ }
+ return res;
+}
+
+void stress_test() {
+ ll tests = 0;
+ for (ll i = 0; i < 1000; i++) {
+ auto n = Random::integer(10, 20);
+ auto C = gen(n);
+ auto expected = naive(n, C);
+ for (ll m = 1; m <= n; m++) {
+ auto got = calc(n, m, C);
+ if (got != expected[m]) cerr << "got: " << got << ", expected: " << expected[m] << FAIL;
+ tests++;
+ }
+ }
+ cerr << "tested random queries: " << tests << endl;
+}
+
+constexpr int N = 5000;
+void performance_test() {
+ timer t;
+ auto C = genQuick(N);
+ t.start();
+ auto hash = calc(N, N/2, C);
+ t.stop();
+ if (t.time > 500) 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/other/sos.cpp b/test/other/sos.cpp
new file mode 100644
index 0000000..f3a6109
--- /dev/null
+++ b/test/other/sos.cpp
@@ -0,0 +1,50 @@
+#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();
+ performance_test();
+}
+
diff --git a/test/other/split.cpp b/test/other/split.cpp
new file mode 100644
index 0000000..e0f5ee1
--- /dev/null
+++ b/test/other/split.cpp
@@ -0,0 +1,24 @@
+#include "../util.h"
+#include <other/split.cpp>
+
+vector<string> split2(string_view s, string_view delim) {
+ vector<string> res;
+ while (!s.empty()) {
+ auto end = s.find_first_of(delim);
+ if (end != 0) res.emplace_back(s.substr(0, end));
+ if (end == string_view::npos) break;
+ s.remove_prefix(end + 1);
+ }
+ return res;
+}
+
+int main() {
+ auto in = "+" + Random::string(100, "abcdef+-*") + "-";
+
+ auto expected = split2(in, "+-*");
+ auto got = split(in, "+-*");
+
+ if (got != expected) cerr << "error" << FAIL;
+ cerr << "done" << endl;
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 19:07:47 +0000