From bbec09408867e82fb9dd9b242e6d99014f9534b6 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 5 Aug 2024 20:10:57 +0200 Subject: more tests --- content/datastructures/dynamicConvexHull.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content/datastructures/dynamicConvexHull.cpp') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index d669847..dfcfe0b 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -4,7 +4,7 @@ struct Line { bool operator<(ll x) const {return p < x;} }; -struct HullDynamic : multiset> { +struct HullDynamic : multiset> { // max über Geraden // (for doubles, use inf = 1/.0, div(a,b) = a/b) ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} -- cgit v1.2.3 From 19436370fb48bc0a5e356d1ba713dc39b1a35d3a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 6 Aug 2024 16:54:13 +0200 Subject: upper case INF --- content/datastructures/dynamicConvexHull.cpp | 2 +- content/datastructures/lazyPropagation.cpp | 2 +- content/datastructures/lichao.cpp | 4 ++-- content/geometry/hpi.cpp | 2 +- content/other/divideAndConquer.cpp | 4 ++-- content/other/knuth.cpp | 2 +- tcr.pdf | Bin 691129 -> 691160 bytes test/datastructures/dynamicConvexHull.lichao.cpp | 1 - test/datastructures/lazyPropagation.cpp | 2 +- test/datastructures/lichao.cpp | 4 ++-- test/other/divideAndConquer.cpp | 8 ++++---- test/other/knuth.cpp | 8 ++++---- 12 files changed, 19 insertions(+), 20 deletions(-) (limited to 'content/datastructures/dynamicConvexHull.cpp') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index dfcfe0b..27ec898 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -5,7 +5,7 @@ struct Line { }; struct HullDynamic : multiset> { // max über Geraden - // (for doubles, use inf = 1/.0, div(a,b) = a/b) + // (for doubles, use INF = 1/.0, div(a,b) = a/b) ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} bool isect(iterator x, iterator y) { diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp index 441590e..ab91364 100644 --- a/content/datastructures/lazyPropagation.cpp +++ b/content/datastructures/lazyPropagation.cpp @@ -2,7 +2,7 @@ struct SegTree { using T = ll; using U = ll; int n; static constexpr T E = 0; // Neutral element for combine - static constexpr U UF = inf; // Unused value by updates + static constexpr U UF = INF; // Unused value by updates vector tree; int h; vector lazy; diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp index 646ad68..1318ca7 100644 --- a/content/datastructures/lichao.cpp +++ b/content/datastructures/lichao.cpp @@ -8,7 +8,7 @@ struct Fun { // Default: Linear function. Change as needed. // Default: Computes min. Change lines with comment for max. struct Lichao { - static constexpr Fun id = {0, inf}; // {0, -inf} + static constexpr Fun id = {0, INF}; // {0, -INF} int n, cap; vector seg; Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {} @@ -36,7 +36,7 @@ struct Lichao { } ll _query(int x) { - ll ans = inf; // -inf + ll ans = INF; // -INF for (int i = x + cap; i > 0; i /= 2) { ans = min(ans, seg[i](x)); // max } diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index 3509e0e..bd3ab1e 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -1,4 +1,4 @@ -constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP +constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP bool left(pt p) {return real(p) < 0 || (real(p) == 0 && imag(p) < 0);} diff --git a/content/other/divideAndConquer.cpp b/content/other/divideAndConquer.cpp index 830dc7f..9bd5f0c 100644 --- a/content/other/divideAndConquer.cpp +++ b/content/other/divideAndConquer.cpp @@ -5,7 +5,7 @@ void rec(int i, int j0, int j1, int m0, int m1) { if (j1 < j0) return; int jmid = (j0 + j1) / 2; - dp[i][jmid] = inf; + dp[i][jmid] = INF; int bestk = m0; for (int k = m0; k < min(jmid, m1 + 1); ++k) { if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) { @@ -18,7 +18,7 @@ void rec(int i, int j0, int j1, int m0, int m1) { } ll calc(int n, int m) { - dp = vector>(m, vector(n, inf)); + dp = vector>(m, vector(n, INF)); for (int i = 0; i < n; i++) dp[0][i] = C[0][i]; for (int i = 1; i < m; i++) { rec(i, 0, n - 1, 0, n - 1); diff --git a/content/other/knuth.cpp b/content/other/knuth.cpp index 1d513c8..aa54924 100644 --- a/content/other/knuth.cpp +++ b/content/other/knuth.cpp @@ -1,5 +1,5 @@ ll calc(int n, int m, const vector>& C) { - vector> dp(m, vector(n, inf)); + vector> dp(m, vector(n, INF)); vector> opt(m, vector(n + 1, n - 1)); for (int i = 0; i < n; i++) dp[0][i] = C[0][i]; diff --git a/tcr.pdf b/tcr.pdf index 1b58dc4..649aa24 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp index 6ab55f0..d50ca60 100644 --- a/test/datastructures/dynamicConvexHull.lichao.cpp +++ b/test/datastructures/dynamicConvexHull.lichao.cpp @@ -1,6 +1,5 @@ #include "../util.h" constexpr ll INF = LL::INF; -constexpr ll inf = LL::INF; #include #include diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp index 7002061..feb07f0 100644 --- a/test/datastructures/lazyPropagation.cpp +++ b/test/datastructures/lazyPropagation.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll INF = LL::INF; #include constexpr int N = 1000'000; diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp index c8a56a3..f4b797b 100644 --- a/test/datastructures/lichao.cpp +++ b/test/datastructures/lichao.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll INF = LL::INF; #include void stress_test(ll range) { @@ -9,7 +9,7 @@ void stress_test(ll range) { xs = Random::distinct(n, -range, range); sort(all(xs)); - vector naive(n, inf); + vector naive(n, INF); Lichao tree; for (int operations = 0; operations < 1000; operations++) { diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp index a6fda9d..6d1b444 100644 --- a/test/other/divideAndConquer.cpp +++ b/test/other/divideAndConquer.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll INF = LL::INF; #include vector> gen(int n) { @@ -43,7 +43,7 @@ vector> genQuick(int n) { } /*ll naive(int n, int m) { - vector> state(m+1, vector(n+1, inf)); + vector> state(m+1, vector(n+1, INF)); state[0][0] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { @@ -56,9 +56,9 @@ vector> genQuick(int n) { }*/ vector naive(int n) { - vector> state(n+1, vector(n+1, inf)); + vector> state(n+1, vector(n+1, INF)); state[0][0] = 0; - vector res(n+1, inf); + vector 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++) { diff --git a/test/other/knuth.cpp b/test/other/knuth.cpp index d469ceb..3462c0a 100644 --- a/test/other/knuth.cpp +++ b/test/other/knuth.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll iINFnf = LL::INF; #include vector> gen(int n) { @@ -43,7 +43,7 @@ vector> genQuick(int n) { } /*ll naive(int n, int m, const vector>& C) { - vector> state(m+1, vector(n+1, inf)); + vector> state(m+1, vector(n+1, INF)); state[0][0] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { @@ -56,9 +56,9 @@ vector> genQuick(int n) { }*/ vector naive(int n, const vector>& C) { - vector> state(n+1, vector(n+1, inf)); + vector> state(n+1, vector(n+1, INF)); state[0][0] = 0; - vector res(n+1, inf); + vector 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++) { -- cgit v1.2.3 From f32a00178f0d3b2152a6fc1dc492c987aaede85f Mon Sep 17 00:00:00 2001 From: MZuenni Date: Tue, 13 Aug 2024 17:14:17 +0200 Subject: small improvements --- content/datastructures/dynamicConvexHull.cpp | 16 ++++++++-------- content/datastructures/pbds.cpp | 4 ++-- content/geometry/convexHull.cpp | 4 ++-- content/geometry/hpi.cpp | 2 +- content/graph/bitonicTSP.cpp | 2 +- content/graph/bitonicTSPsimple.cpp | 2 +- content/graph/pushRelabel.cpp | 2 +- tcr.pdf | Bin 691284 -> 691101 bytes test/datastructures/fenwickTree2.cpp | 2 +- test/geometry/delaunay.cpp | 6 +++--- test/math/gauss.cpp | 2 +- test/math/inversionsMerge.cpp | 2 +- 12 files changed, 22 insertions(+), 22 deletions(-) (limited to 'content/datastructures/dynamicConvexHull.cpp') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index 27ec898..abae1d7 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -1,22 +1,22 @@ struct Line { - mutable ll m, b, p; + mutable ll m, c, p; bool operator<(const Line& o) const {return m < o.m;} bool operator<(ll x) const {return p < x;} }; struct HullDynamic : multiset> { // max über Geraden - // (for doubles, use INF = 1/.0, div(a,b) = a/b) - ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} + // (for doubles, use INF = 1/.0, div(a,c) = a/c) + ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);} bool isect(iterator x, iterator y) { if (y == end()) {x->p = INF; return false;} - if (x->m == y->m) x->p = x->b > y->b ? INF : -INF; - else x->p = div(y->b - x->b, x->m - y->m); + if (x->m == y->m) x->p = x->c > y->c ? INF : -INF; + else x->p = div(y->c - x->c, x->m - y->m); return x->p >= y->p; } - void add(ll m, ll b) { - auto x = insert({m, b, 0}); + void add(ll m, ll c) { + auto x = insert({m, c, 0}); while (isect(x, next(x))) erase(next(x)); if (x != begin()) { x--; @@ -31,6 +31,6 @@ struct HullDynamic : multiset> { // max über Geraden ll query(ll x) { auto l = *lower_bound(x); - return l.m * x + l.b; + return l.m * x + l.c; } }; diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp index f0889a2..de0ace6 100644 --- a/content/datastructures/pbds.cpp +++ b/content/datastructures/pbds.cpp @@ -6,11 +6,11 @@ using Tree = tree, rb_tree_tag, // T.order_of_key(x): number of elements strictly less than x // *T.find_by_order(k): k-th element +constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd template struct chash { - static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd size_t operator()(T o) const { - return __builtin_bswap64(hash()(o) * C); + return __builtin_bswap64(hash()(o) * RNG); }}; template using hashMap = gp_hash_table>; diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp index 6d89e05..1173924 100644 --- a/content/geometry/convexHull.cpp +++ b/content/geometry/convexHull.cpp @@ -11,8 +11,8 @@ vector convexHull(vector pts){ while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--; h[k++] = *it; }}; - half(all(pts), 1);// Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle. + half(all(pts), 1); // Untere Hülle. + half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. h.resize(k); return h; } diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index bd3ab1e..c58a6e7 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -1,4 +1,4 @@ -constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP +constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP bool left(pt p) {return real(p) < 0 || (real(p) == 0 && imag(p) < 0);} diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index 6470232..eee5082 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -27,5 +27,5 @@ auto bitonicTSP() { (lt.back() == 1 ? lt : ut).push_back(0); reverse(all(lt)); lt.insert(lt.end(), all(ut)); - return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position. + return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp index 8b6e6c5..cacfb9c 100644 --- a/content/graph/bitonicTSPsimple.cpp +++ b/content/graph/bitonicTSPsimple.cpp @@ -23,5 +23,5 @@ auto bitonicTSP() { rl.push_back(v); p2 = v; }} lr.insert(lr.end(), rl.rbegin(), rl.rend()); - return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position. + return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp index 73a9eae..ec36026 100644 --- a/content/graph/pushRelabel.cpp +++ b/content/graph/pushRelabel.cpp @@ -29,7 +29,7 @@ ll maxFlow(int s, int t) { cur.assign(n, 0); H.assign(n, 0); H[s] = n; - ec[t] = 1;//never set t to active... + ec[t] = 1; //never set t to active... vector co(2*n); co[0] = n - 1; for (Edge& e : adj[s]) addFlow(e, e.c); diff --git a/tcr.pdf b/tcr.pdf index b096438..57691c5 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp index aa99576..89d5b0f 100644 --- a/test/datastructures/fenwickTree2.cpp +++ b/test/datastructures/fenwickTree2.cpp @@ -9,7 +9,7 @@ void stress_test() { ll queries = 0; for (int tries = 0; tries < 100; tries++) { int n = Random::integer(10, 100); - vector naive(n);// = Random::integers(n, -1000, 1000); + vector naive = Random::integers(n, -1000, 1000); init(naive); for (int operations = 0; operations < 1000; operations++) { { diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp index 7f8ec30..5740b95 100644 --- a/test/geometry/delaunay.cpp +++ b/test/geometry/delaunay.cpp @@ -16,11 +16,11 @@ vector convexHull(vector pts){ vector h(2 * sz(pts)); auto half = [&](auto begin, auto end, int t) { for (auto it = begin; it != end; it++) { - while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points! + while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points! h[k++] = *it; }}; - half(all(pts), 1);// Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle. + half(all(pts), 1); // Untere Hülle. + half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. h.resize(k); return h; } diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp index 37bacce..6e4759d 100644 --- a/test/math/gauss.cpp +++ b/test/math/gauss.cpp @@ -14,7 +14,7 @@ vector> inverseMat(const vector>& m) { mat[i].resize(2*n); mat[i][n+i] = 1; } - gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs... + gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs... vector> res(m); for (int i = 0; i < n; i++) { res[i] = vector(mat[i].begin() + n, mat[i].end()); diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp index 85ab0d2..acdc555 100644 --- a/test/math/inversionsMerge.cpp +++ b/test/math/inversionsMerge.cpp @@ -16,7 +16,7 @@ void stress_test() { for (ll i = 0; i < 100'000; i++) { int n = Random::integer(1, 100); vector v(n); - for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer(0, 10000);//values must be unique ): + for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer(0, 10000); //values must be unique ): shuffle(all(v), Random::rng); ll expected = naive(v); ll got = mergeSort(v); -- cgit v1.2.3 From 39190436d167414b5853730e91a173fa2affea6a Mon Sep 17 00:00:00 2001 From: MZuenni Date: Tue, 13 Aug 2024 17:15:57 +0200 Subject: small improvements --- content/datastructures/dynamicConvexHull.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content/datastructures/dynamicConvexHull.cpp') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index abae1d7..63e0e13 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -6,7 +6,7 @@ struct Line { struct HullDynamic : multiset> { // max über Geraden // (for doubles, use INF = 1/.0, div(a,c) = a/c) - ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);} + ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);} bool isect(iterator x, iterator y) { if (y == end()) {x->p = INF; return false;} -- cgit v1.2.3