diff options
Diffstat (limited to 'test/math')
33 files changed, 114 insertions, 172 deletions
diff --git a/test/math/berlekampMassey.cpp b/test/math/berlekampMassey.cpp index c7e83fc..93832b0 100644 --- a/test/math/berlekampMassey.cpp +++ b/test/math/berlekampMassey.cpp @@ -12,10 +12,10 @@ struct RandomRecurence { } ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); @@ -60,7 +60,7 @@ void performance_test() { cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } - + int main() { stress_test(); if (!sanitize) performance_test(); diff --git a/test/math/bigint.cpp b/test/math/bigint.cpp index 53e18dd..2d75343 100644 --- a/test/math/bigint.cpp +++ b/test/math/bigint.cpp @@ -9,7 +9,7 @@ struct modInt { stringstream a; a << x; string b = a.str(); - for (ll i = b[0] == '-' ? 1 : 0; i < sz(b); i++) { + for (ll i = b[0] == '-' ? 1 : 0; i < ssize(b); i++) { value *= 10; value += b[i] - '0'; value %= MOD; @@ -115,7 +115,7 @@ void stress_test(int LIM) { } cerr << "tested random queries: " << queries << endl; } - + int main() { stress_test(100); if (!sanitize) stress_test(1000); diff --git a/test/math/binomial0.cpp b/test/math/binomial0.cpp index 00c04d4..17a5f91 100644 --- a/test/math/binomial0.cpp +++ b/test/math/binomial0.cpp @@ -4,17 +4,16 @@ constexpr ll mod = 1'394'633'899; #include <math/binomial0.cpp> - void stress_test() { vector<ll> last = {1}; ll queries = 0; for (ll i = 0; i < 10'000; i++) { for (ll j = 0; j <= i; j++) { - ll got = calc_binom(i, j); + ll got = binom(i, j); ll expected = last[j]; - if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial1.cpp b/test/math/binomial1.cpp index f6fe20b..3a7b291 100644 --- a/test/math/binomial1.cpp +++ b/test/math/binomial1.cpp @@ -7,11 +7,11 @@ void stress_test() { ll queries = 0; for (ll i = 0; i <= 61; i++) { for (ll j = 0; j <= i; j++) { - ll got = calc_binom(i, j); + ll got = binom(i, j); ll expected = last[j]; - if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial2.cpp b/test/math/binomial2.cpp index b55c8af..ce6a07c 100644 --- a/test/math/binomial2.cpp +++ b/test/math/binomial2.cpp @@ -8,11 +8,11 @@ void stress_test() { ll queries = 0; for (ll i = 0; i <= 1000; i++) { for (ll j = 0; j <= i; j++) { - ll got = calc_binom(i, j); + ll got = binom(i, j); ll expected = last[j]; - if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial3.cpp b/test/math/binomial3.cpp index 4a99689..eaca24e 100644 --- a/test/math/binomial3.cpp +++ b/test/math/binomial3.cpp @@ -11,11 +11,11 @@ void stress_test() { ll queries = 0; for (ll i = 0; i < mod; i++) { for (ll j = 0; j <= i; j++) { - ll got = calc_binom(i, j, mod); + ll got = binom(i, j, mod); ll expected = last[j]; - if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp index 09480b1..2ba3525 100644 --- a/test/math/cycleDetection.cpp +++ b/test/math/cycleDetection.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/cycleDetection.cpp> pair<ll, ll> naive(ll x0, function<ll(ll)> f) { diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp index 167aa62..21a5736 100644 --- a/test/math/gauss.cpp +++ b/test/math/gauss.cpp @@ -7,10 +7,10 @@ vector<vector<double>> mat; #include <math/gauss.cpp> vector<vector<double>> inverseMat(const vector<vector<double>>& m) { - int n = sz(m); + int n = ssize(m); mat = m; for (int i = 0; i < n; i++) { - if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + if (ssize(mat[i]) != n) cerr << "error: no square matrix" << FAIL; mat[i].resize(2*n); mat[i][n+i] = 1; } @@ -27,10 +27,10 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) { } vector<vector<double>> mul(const vector<vector<double>>& a, const vector<vector<double>>& b) { - int n = sz(a); - int m = sz(b[0]); - int x = sz(b); - if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + int n = ssize(a); + int m = ssize(b[0]); + int x = ssize(b); + if (ssize(a[0]) != ssize(b)) cerr << "error: wrong dimensions" << FAIL; vector<vector<double>> res(n, vector<double>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { @@ -48,21 +48,21 @@ void test_tiny() { {0, 5, 6, 7}, {0, 0, 8, 9}, }; - if (gauss(sz(mat)) != UNIQUE) cerr << "error: 1" << FAIL; + if (gauss(ssize(mat)) != UNIQUE) cerr << "error: 1" << FAIL; mat = { {-1, 1, 0, -1}, { 2, 6, 0, 10}, { 1, -2, 0, 0}, }; - if (gauss(sz(mat)) != MULTIPLE) cerr << "error: 2" << FAIL; + if (gauss(ssize(mat)) != MULTIPLE) cerr << "error: 2" << FAIL; mat = { {-1, 1, 0, -1}, { 2, 6, 0, 10}, { 1, -2, 0, 1}, }; - if (gauss(sz(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL; + if (gauss(ssize(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL; } void stress_test_inv() { diff --git a/test/math/inversions.cpp b/test/math/inversions.cpp index 42ab343..86d87d0 100644 --- a/test/math/inversions.cpp +++ b/test/math/inversions.cpp @@ -1,10 +1,9 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/inversions.cpp> ll naive(const vector<ll>& v) { ll res = 0; - for (ll i = 0; i < sz(v); i++) { + for (ll i = 0; i < ssize(v); i++) { for (ll j = 0; j < i; j++) { if (v[j] > v[i]) res++; } diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp index 2492af4..ab1c62e 100644 --- a/test/math/inversionsMerge.cpp +++ b/test/math/inversionsMerge.cpp @@ -3,7 +3,7 @@ ll naive(const vector<ll>& v) { ll res = 0; - for (ll i = 0; i < sz(v); i++) { + for (ll i = 0; i < ssize(v); i++) { for (ll j = 0; j < i; j++) { if (v[j] > v[i]) res++; } @@ -17,7 +17,7 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> v(n); for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ): - shuffle(all(v), Random::rng); + ranges::shuffle(v, Random::rng); ll expected = naive(v); ll got = mergeSort(v); if (got != expected) { diff --git a/test/math/kthperm.cpp b/test/math/kthperm.cpp index 1bf8db3..ca95699 100644 --- a/test/math/kthperm.cpp +++ b/test/math/kthperm.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/kthperm.cpp> void stress_test(int LIM) { @@ -7,13 +6,13 @@ void stress_test(int LIM) { for (int i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); vector<ll> expected(n); - iota(all(expected), 0); + iota(begin(expected), end(expected), 0); ll k = 0; do { auto got = kthperm(n, k); if (got != expected) cerr << "error" << FAIL; k++; - } while (k < 100 && next_permutation(all(expected))); + } while (k < 100 && ranges::next_permutation(expected).found); queries += n; } cerr << "tested queries: " << queries << endl; diff --git a/test/math/kthperm_permIndex.cpp b/test/math/kthperm_permIndex.cpp index d84524e..5e05c73 100644 --- a/test/math/kthperm_permIndex.cpp +++ b/test/math/kthperm_permIndex.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/kthperm.cpp> #include <math/permIndex.cpp> diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp index 6db586a..d8967a0 100644 --- a/test/math/lgsFp.cpp +++ b/test/math/lgsFp.cpp @@ -1,6 +1,5 @@ #include "../util.h" #include <math/shortModInv.cpp> -vector<vector<ll>> mat; constexpr ll mod = 1'000'000'007; namespace lgs { #include <math/lgsFp.cpp> @@ -8,30 +7,26 @@ namespace lgs { vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) { - int n = sz(m); - mat = m; + int n = ssize(m); + vector<vector<ll>> mat = m; for (int i = 0; i < n; i++) { - if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + if (ssize(mat[i]) != n) cerr << "error: no square matrix" << FAIL; mat[i].resize(2*n); mat[i][n+i] = 1; } - lgs::gauss(sz(mat), sz(mat[0])); - vector<vector<ll>> res(m); + vector<int> pivots = lgs::gauss(mat); for (int i = 0; i < n; i++) { - res[i] = vector<ll>(mat[i].begin() + n, mat[i].end()); - for (int j = 0; j < n; j++) { - if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL; - if (j == i && mat[i][j] != 1) cerr << "error: not full rank?" << FAIL; - } + if (pivots[i] != i) cerr << "error: not full rank?" << FAIL; + mat[i].erase(begin(mat[i]), begin(mat[i]) + n); } - return res; + return mat; } vector<vector<ll>> mul(const vector<vector<ll>>& a, const vector<vector<ll>>& b) { - int n = sz(a); - int m = sz(b[0]); - int x = sz(b); - if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + int n = ssize(a); + int m = ssize(b[0]); + int x = ssize(b); + if (ssize(a[0]) != ssize(b)) cerr << "error: wrong dimensions" << FAIL; vector<vector<ll>> res(n, vector<ll>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { @@ -53,18 +48,17 @@ void test_square() { vector<vector<ll>> m(n); for (auto& v : m) v = Random::integers<ll>(n, 0, mod); - mat = m; - lgs::gauss(sz(mat), sz(mat[0])); + lgs::gauss(m); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { - hash += mat[i][j]; + hash += m[i][j]; } } queries += n; } - cerr << "tested sqaures: " << queries << " (hash: " << hash << ")" << endl;; + cerr << "tested squares: " << queries << " (hash: " << hash << ")" << endl;; } void stress_test_inv() { @@ -82,8 +76,7 @@ void stress_test_inv() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { - if (i == j && prod[i][j] != 1) cerr << "error: not inverted" << FAIL; - if (i != j && prod[i][j] != 0) cerr << "error: not inverted" << FAIL; + if (prod[i][j] != (i == j)) cerr << "error: not inverted" << FAIL; } } @@ -98,15 +91,14 @@ void performance_test() { vector<vector<ll>> m(N); for (auto& v : m) v = Random::integers<ll>(N, 0, mod); - mat = m; t.start(); - lgs::gauss(sz(mat), sz(mat[0])); + lgs::gauss(m); t.stop(); hash_t hash = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { - hash += mat[i][j]; + hash += m[i][j]; } } if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index 977221e..a2ac01d 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -6,16 +6,15 @@ vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { return mulSlow(a, b); } - struct RandomRecurence { vector<ll> f, c, cache; RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearRecurrenceNTT.cpp b/test/math/linearRecurrenceNTT.cpp index ca7e29e..f7615d6 100644 --- a/test/math/linearRecurrenceNTT.cpp +++ b/test/math/linearRecurrenceNTT.cpp @@ -12,10 +12,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearRecurrenceOld.cpp b/test/math/linearRecurrenceOld.cpp index 6435d5a..b3d1611 100644 --- a/test/math/linearRecurrenceOld.cpp +++ b/test/math/linearRecurrenceOld.cpp @@ -6,10 +6,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearSieve.cpp b/test/math/linearSieve.cpp index fbed4b5..1a5286f 100644 --- a/test/math/linearSieve.cpp +++ b/test/math/linearSieve.cpp @@ -57,7 +57,7 @@ void performance_test() { timer t; t.start(); sieve(); - hash_t hash = sz(primes); + hash_t hash = ssize(primes); t.stop(); if (!sanitize) { if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/math/longestIncreasingSubsequence.cpp b/test/math/longestIncreasingSubsequence.cpp index d08cf57..5bc3936 100644 --- a/test/math/longestIncreasingSubsequence.cpp +++ b/test/math/longestIncreasingSubsequence.cpp @@ -9,7 +9,7 @@ constexpr ll INF = LL::INF; template<bool STRICT> bool isLis(const vector<ll>& a, const vector<int>& lis) { - for (int i = 1; i < sz(lis); i++) { + for (int i = 1; i < ssize(lis); i++) { if (lis[i-1] >= lis[i]) return false; if (a[lis[i-1]] > a[lis[i]]) return false; if (STRICT && a[lis[i-1]] == a[lis[i]]) return false; @@ -20,12 +20,12 @@ bool isLis(const vector<ll>& a, const vector<int>& lis) { template<bool STRICT> vector<int> naive(const vector<ll>& a) { vector<int> res; - for (ll i = 1; i < (1ll << sz(a)); i++) { + for (ll i = 1; i < (1ll << ssize(a)); i++) { vector<int> tmp; - for (ll j = 0; j < sz(a); j++) { + for (ll j = 0; j < ssize(a); j++) { if (((i >> j) & 1) != 0) tmp.push_back(j); } - if (sz(tmp) >= sz(res) && isLis<STRICT>(a, tmp)) res = tmp; + if (ssize(tmp) >= ssize(res) && isLis<STRICT>(a, tmp)) res = tmp; } return res; } @@ -56,10 +56,9 @@ void performance_test() { timer t; auto a = Random::integers<ll>(N, -10'000, 10'000); auto b = Random::integers<ll>(N, -10'000, 10'000); - sort(all(b)); + ranges::sort(b); auto c = Random::integers<ll>(N, -10'000, 10'000); - sort(all(c)); - reverse(all(c)); + ranges::sort(c | views::reverse); hash_t hash = 0; t.start(); hash += lis(a).size(); diff --git a/test/math/matrixPower.cpp b/test/math/matrixPower.cpp index b1d6783..083dded 100644 --- a/test/math/matrixPower.cpp +++ b/test/math/matrixPower.cpp @@ -7,15 +7,15 @@ struct mat { mat(int dim = 0, int diag = 1) : m(dim, vector<ll>(dim)) { for (int i = 0; i < dim; i++) m[i][i] = diag; } - mat(const vector<ll> c) : m(sz(c), vector<ll>(sz(c))) { + mat(const vector<ll> c) : m(ssize(c), vector<ll>(ssize(c))) { m[0] = c; - for (ll i = 1; i < sz(c); i++) { + for (ll i = 1; i < ssize(c); i++) { m[i][i-1] = 1; } } mat operator*(const mat& o) const { - int dim = sz(m); + int dim = ssize(m); mat res(dim, 0); for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { @@ -29,7 +29,7 @@ struct mat { } vector<ll> operator*(const vector<ll>& o) const { - int dim = sz(m); + int dim = ssize(m); vector<ll> res(dim); for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { @@ -48,10 +48,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); @@ -67,13 +67,13 @@ void stress_test() { RandomRecurence f(n); precalc(mat(f.c)); auto tmp = f.f; - reverse(all(tmp)); + ranges::reverse(tmp); for (int j = 0; j < 100; j++) { ll k = Random::integer<ll>(0, 1000); vector<ll> got = calc(k, tmp); - vector<ll> expected(sz(f.f)); + vector<ll> expected(ssize(f.f)); for (ll l = 0; l < n; l++) expected[n - 1 - l] = f(k + l); if (got != expected) cerr << "error" << FAIL; @@ -89,7 +89,7 @@ void performance_test() { timer t; RandomRecurence f(N); auto tmp = f.f; - reverse(all(tmp)); + ranges::reverse(tmp); t.start(); precalc(mat(f.c)); diff --git a/test/math/millerRabin.base32.cpp b/test/math/millerRabin.base32.cpp index 069f125..e9a4b57 100644 --- a/test/math/millerRabin.base32.cpp +++ b/test/math/millerRabin.base32.cpp @@ -95,7 +95,7 @@ void extra_tests() { t.start(); auto got = isPrime(x); t.stop(); - bool expected = sz(factors) == 1 && factors.begin()->second == 1; + bool expected = ssize(factors) == 1 && factors.begin()->second == 1; if (got != expected) cerr << "error: " << x << FAIL; } if (t.time > 10) cerr << "too slow" << FAIL; diff --git a/test/math/millerRabin.cpp b/test/math/millerRabin.cpp index 18fad40..e7feba1 100644 --- a/test/math/millerRabin.cpp +++ b/test/math/millerRabin.cpp @@ -87,7 +87,7 @@ void extra_tests() { t.start(); auto got = isPrime(x); t.stop(); - bool expected = sz(factors) == 1 && factors.begin()->second == 1; + bool expected = ssize(factors) == 1 && factors.begin()->second == 1; if (got != expected) cerr << "error: " << x << FAIL; } if (t.time > 10) cerr << "too slow" << FAIL; diff --git a/test/math/modExp.cpp b/test/math/modExp.cpp deleted file mode 100644 index 4d2b4b2..0000000 --- a/test/math/modExp.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include "../util.h" -#include <math/modExp.cpp> - -void stress_test() { - ll queries = 0; - for (ll i = 0; i < 10'000; i++) { - int a = Random::integer<int>(1, 100); - int n = Random::integer<int>(2, 100); - ll expected = 1; - ll k = 0; - do { - auto got = powMod(a, k, n); - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - k++; - expected = (expected * a) % n; - } while (k < 100); - queries += n; - } - cerr << "tested queries: " << queries << endl; -} - -constexpr int N = 1'000'000; -void performance_test() { - timer t; - hash_t hash = 0; - for (int operations = 0; operations < N; operations++) { - ll a = Random::integer<ll>(0, 1'000'000'000); - ll b = Random::integer<ll>(0, 1'000'000'000); - ll n = Random::integer<ll>(2, 1'000'000'000); - t.start(); - hash += powMod(a, b, n); - t.stop(); - } - if (t.time > 750) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; -} - -int main() { - stress_test(); - if (!sanitize) performance_test(); -} - diff --git a/test/math/permIndex.cpp b/test/math/permIndex.cpp index 8dcfd6b..2f19985 100644 --- a/test/math/permIndex.cpp +++ b/test/math/permIndex.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/permIndex.cpp> void stress_test(int LIM) { @@ -7,13 +6,13 @@ void stress_test(int LIM) { for (int i = 0; i < LIM; i++) { int n = Random::integer<int>(1, 100); vector<ll> cur(n); - iota(all(cur), 0); + iota(begin(cur), end(cur), 0); ll expected = 0; do { auto got = permIndex(cur); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; expected++; - } while (expected < 100 && next_permutation(all(cur))); + } while (expected < 100 && ranges::next_permutation(cur).found); queries += n; } cerr << "tested queries: " << queries << endl; @@ -23,7 +22,7 @@ constexpr int N = 500'000; void performance_test() { timer t; vector<ll> cur(N); - iota(all(cur), 0); + iota(begin(cur), end(cur), 0); reverse(cur.end() - 10, cur.end()); t.start(); auto hash = permIndex(cur); diff --git a/test/math/polynomial.cpp b/test/math/polynomial.cpp index f4a9486..adf3773 100644 --- a/test/math/polynomial.cpp +++ b/test/math/polynomial.cpp @@ -11,7 +11,7 @@ poly randomPoly(int deg) { ll eval(const vector<ll>& p, ll x) { ll res = 0; - for (ll i = 0, j = 1; i < sz(p); i++, j = (j * x) % mod) { + for (ll i = 0, j = 1; i < ssize(p); i++, j = (j * x) % mod) { res += j * p[i]; res %= mod; } @@ -50,7 +50,7 @@ void test_add() { auto c = a; c += b; - if (sz(c) > sz(a) && sz(c) > sz(b)) cerr << "error: wrong degree" << FAIL; + if (ssize(c) > ssize(a) && ssize(c) > ssize(b)) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + m + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -74,7 +74,7 @@ void test_mul() { auto b = randomPoly(m); auto c = a * b; - if (sz(c) > sz(a) + sz(b) - 1) cerr << "error: wrong degree" << FAIL; + if (ssize(c) > ssize(a) + ssize(b) - 1) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + m + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -97,8 +97,8 @@ void test_shift() { auto a = randomPoly(n); auto b = a << m; - if (sz(b) > sz(a)) cerr << sz(a) << " " << sz(b) << endl; - if (sz(b) > sz(a)) cerr << "error: wrong degree" << FAIL; + if (ssize(b) > ssize(a)) cerr << ssize(a) << " " << ssize(b) << endl; + if (ssize(b) > ssize(a)) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -126,8 +126,8 @@ void test_divmod() { auto b = randomPoly(m); auto [div, rem] = a.divmod(b); - if (sz(rem) > sz(b)) cerr << "error: wrong degree (rem)" << FAIL; - if (sz(div) > 1 + max<ll>(0, sz(a) - sz(b))) cerr << "error: wrong degree (div)" << FAIL; + if (ssize(rem) > ssize(b)) cerr << "error: wrong degree (rem)" << FAIL; + if (ssize(div) > 1 + max<ll>(0, ssize(a) - ssize(b))) cerr << "error: wrong degree (div)" << FAIL; for (int i = 0; i <= n + m; i++) { ll x = Random::integer<ll>(0, mod); @@ -142,7 +142,7 @@ void test_divmod() { } cerr << "tested divmod: " << queries << endl; } - + int main() { test_eval(); test_add(); diff --git a/test/math/primeSieve.cpp b/test/math/primeSieve.cpp index a675f6a..52570e2 100644 --- a/test/math/primeSieve.cpp +++ b/test/math/primeSieve.cpp @@ -18,7 +18,7 @@ void stress_test() { if (got) found.push_back(i); queries++; } - primes.resize(sz(found)); + primes.resize(ssize(found)); if (primes != found) cerr << "error: primes" << FAIL; for (int i = 0; i < 1'000'000; i++) { ll x = Random::integer<ll>(2, N); @@ -34,7 +34,7 @@ void performance_test() { timer t; t.start(); primeSieve(); - hash_t hash = sz(primes); + hash_t hash = ssize(primes); t.stop(); if (!sanitize) { if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/math/primitiveRoot.cpp b/test/math/primitiveRoot.cpp index cd0b388..6ad7429 100644 --- a/test/math/primitiveRoot.cpp +++ b/test/math/primitiveRoot.cpp @@ -63,7 +63,7 @@ void stress_test2() { map<ll, int> facts; factor(x, facts); if (x % 2 == 0) facts.erase(facts.find(2)); - bool expected = sz(facts) == 1; + bool expected = ssize(facts) == 1; if (x % 4 == 0) expected = false; if (x == 2 || x == 4) expected = true; diff --git a/test/math/shortModInv.cpp b/test/math/shortModInv.cpp index 0e91900..5e74907 100644 --- a/test/math/shortModInv.cpp +++ b/test/math/shortModInv.cpp @@ -7,7 +7,7 @@ void stress_test() { ll n = Random::integer<ll>(2, 1'000'000'000); ll x = 0; do { - x = Random::integer<ll>(0, n); + x = Random::integer<ll>(0, 1'000'000'000); } while (gcd(x, n) != 1); ll y = multInv(x, n); ll got = (x*y) % n; diff --git a/test/math/transforms/fft.cpp b/test/math/transforms/fft.cpp index 35f7e15..aa7ddd2 100644 --- a/test/math/transforms/fft.cpp +++ b/test/math/transforms/fft.cpp @@ -2,14 +2,14 @@ #include <math/transforms/fft.cpp> vector<cplx> to_cplx(const vector<ll>& in) { - vector<cplx> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = in[i]; + vector<cplx> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = in[i]; return res; } vector<ll> from_cplx(const vector<cplx>& in) { - vector<ll> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + vector<ll> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = llround(real(in[i])); return res; } diff --git a/test/math/transforms/fftMul.cpp b/test/math/transforms/fftMul.cpp index 72fd4d8..38e7c73 100644 --- a/test/math/transforms/fftMul.cpp +++ b/test/math/transforms/fftMul.cpp @@ -5,21 +5,21 @@ #include <math/transforms/fftMul.cpp> vector<ll> from_cplx(const vector<cplx>& in) { - vector<ll> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + vector<ll> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = llround(real(in[i])); return res; } vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyBitwise.cpp b/test/math/transforms/multiplyBitwise.cpp index e89ba4e..f460204 100644 --- a/test/math/transforms/multiplyBitwise.cpp +++ b/test/math/transforms/multiplyBitwise.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) <= i && sz(b) <= i) { + if (ssize(a) <= i && ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i&j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyFFT.cpp b/test/math/transforms/multiplyFFT.cpp index a54020c..f11ec45 100644 --- a/test/math/transforms/multiplyFFT.cpp +++ b/test/math/transforms/multiplyFFT.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyNTT.cpp b/test/math/transforms/multiplyNTT.cpp index 90c606a..48a1aa3 100644 --- a/test/math/transforms/multiplyNTT.cpp +++ b/test/math/transforms/multiplyNTT.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; res[i+j] %= mod; } diff --git a/test/math/transforms/seriesOperations.cpp b/test/math/transforms/seriesOperations.cpp index 29c91c7..1242537 100644 --- a/test/math/transforms/seriesOperations.cpp +++ b/test/math/transforms/seriesOperations.cpp @@ -24,7 +24,7 @@ namespace reference {//checked against yosupo } vector<ll> poly_deriv(vector<ll> a){ - for(int i = 0; i < sz(a)-1; i++) + for(int i = 0; i < ssize(a)-1; i++) a[i] = a[i+1] * (i+1) % mod; a.pop_back(); return a; @@ -32,8 +32,8 @@ namespace reference {//checked against yosupo vector<ll> poly_integr(vector<ll> a){ if(a.empty()) return {0}; - a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); - for(int i = sz(a)-2; i > 0; i--) + a.push_back(a.back() * powMod(ssize(a), mod-2, mod) % mod); + for(int i = ssize(a)-2; i > 0; i--) a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; a[0] = 0; return a; @@ -51,7 +51,7 @@ namespace reference {//checked against yosupo for(int len = 1; len < n; len *= 2){ vector<ll> p = poly_log(q, 2*len); for(int i = 0; i < 2*len; i++) - p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; + p[i] = (mod - p[i] + (i < ssize(a) ? a[i] : 0)) % mod; vector<ll> q2 = q; q2.resize(2*len); ntt(p), ntt(q2); |