From 1880ccb6d85c6eb79e724593457877bab431951c Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 16 Nov 2024 21:17:29 +0100 Subject: get rid of all() and sz() --- content/datastructures/lichao.cpp | 5 +- content/datastructures/monotonicConvexHull.cpp | 9 ++-- content/datastructures/persistent.cpp | 36 +++++++------- content/datastructures/sparseTable.cpp | 4 +- content/datastructures/sparseTableDisjoint.cpp | 2 +- content/datastructures/treap.cpp | 2 +- content/geometry/antipodalPoints.cpp | 8 +-- content/geometry/closestPair.cpp | 15 +++--- content/geometry/convexHull.cpp | 22 ++++----- content/geometry/delaunay.cpp | 12 ++--- content/geometry/geometry.tex | 1 + content/geometry/linesAndSegments.cpp | 4 +- content/geometry/polygon.cpp | 26 +++++----- content/geometry/segmentIntersection.cpp | 4 +- content/geometry/sortAround.cpp | 2 +- content/graph/LCA_sparse.cpp | 8 +-- content/graph/TSP.cpp | 4 +- content/graph/articulationPoints.cpp | 10 ++-- content/graph/bitonicTSP.cpp | 12 ++--- content/graph/bitonicTSPsimple.cpp | 14 +++--- content/graph/blossom.cpp | 14 +++--- content/graph/bronKerbosch.cpp | 4 +- content/graph/centroid.cpp | 2 +- content/graph/cycleCounting.cpp | 16 +++--- content/graph/dijkstra.cpp | 4 +- content/graph/dinic.cpp | 10 ++-- content/graph/dinicScaling.cpp | 10 ++-- content/graph/euler.cpp | 6 +-- content/graph/floydWarshall.cpp | 12 ++--- content/graph/havelHakimi.cpp | 6 +-- content/graph/hld.cpp | 2 +- content/graph/hopcroftKarp.cpp | 4 +- content/graph/kruskal.cpp | 2 +- content/graph/kuhn.cpp | 2 +- content/graph/matching.cpp | 10 ++-- content/graph/maxWeightBipartiteMatching.cpp | 4 +- content/graph/minCostMaxFlow.cpp | 12 ++--- content/graph/pushRelabel.cpp | 10 ++-- content/graph/reroot.cpp | 6 +-- content/graph/scc.cpp | 8 +-- content/graph/stoerWagner.cpp | 8 +-- content/graph/treeIsomorphism.cpp | 4 +- content/graph/virtualTree.cpp | 10 ++-- content/math/berlekampMassey.cpp | 2 +- content/math/bigint.cpp | 63 ++++++++++++------------ content/math/discreteLogarithm.cpp | 4 +- content/math/gauss.cpp | 4 +- content/math/inversions.cpp | 2 +- content/math/inversionsMerge.cpp | 14 +++--- content/math/lgsFp.cpp | 2 +- content/math/linearRecurrence.cpp | 8 +-- content/math/linearRecurrenceOld.cpp | 8 +-- content/math/longestIncreasingSubsequence.cpp | 4 +- content/math/matrixPower.cpp | 2 +- content/math/permIndex.cpp | 4 +- content/math/piLegendre.cpp | 2 +- content/math/polynomial.cpp | 2 +- content/math/transforms/andTransform.cpp | 2 +- content/math/transforms/bitwiseTransforms.cpp | 2 +- content/math/transforms/fft.cpp | 2 +- content/math/transforms/fftMul.cpp | 6 +-- content/math/transforms/multiplyBitwise.cpp | 2 +- content/math/transforms/multiplyFFT.cpp | 4 +- content/math/transforms/multiplyNTT.cpp | 2 +- content/math/transforms/ntt.cpp | 2 +- content/math/transforms/orTransform.cpp | 2 +- content/math/transforms/seriesOperations.cpp | 8 +-- content/math/transforms/xorTransform.cpp | 2 +- content/other/fastSubsetSum.cpp | 10 ++-- content/other/pbs.cpp | 2 +- content/other/sos.cpp | 4 +- content/string/ahoCorasick.cpp | 11 +++-- content/string/deBruijn.cpp | 2 +- content/string/duval.cpp | 6 +-- content/string/kmp.cpp | 8 +-- content/string/longestCommonSubsequence.cpp | 8 +-- content/string/lyndon.cpp | 2 +- content/string/manacher.cpp | 6 +-- content/string/suffixArray.cpp | 14 +++--- content/string/suffixAutomaton.cpp | 12 ++--- content/string/suffixTree.cpp | 10 ++-- content/string/trie.cpp | 4 +- content/string/z.cpp | 2 +- content/template/template.cpp | 12 ++--- test/datastructures/LCT.cpp | 8 +-- test/datastructures/dynamicConvexHull.lichao.cpp | 2 +- test/datastructures/lichao.cpp | 4 +- test/datastructures/monotonicConvexHull.cpp | 16 +++--- test/datastructures/persistentArray.cpp | 10 ++-- test/datastructures/segmentTree.cpp | 6 +-- test/datastructures/treap.cpp | 6 +-- test/datastructures/waveletTree.cpp | 4 +- test/geometry.h | 4 +- test/geometry/antipodalPoints.cpp | 8 +-- test/geometry/circle.cpp | 12 ++--- test/geometry/closestPair.cpp | 2 +- test/geometry/closestPair.double.cpp | 2 +- test/geometry/convexHull.cpp | 4 +- test/geometry/delaunay.cpp | 37 +++++++------- test/geometry/formulas.cpp | 2 +- test/geometry/hpi.cpp | 48 +++++++++--------- test/geometry/polygon.cpp | 22 ++++----- test/geometry/segmentIntersection.cpp | 2 +- test/geometry/sortAround.cpp | 6 +-- test/graph/TSP.cpp | 8 +-- test/graph/articulationPoints.bcc.cpp | 18 +++---- test/graph/articulationPoints.bridges.cpp | 12 ++--- test/graph/articulationPoints.cpp | 10 ++-- test/graph/bronKerbosch.cpp | 10 ++-- test/graph/centroid.cpp | 12 ++--- test/graph/connect.cpp | 10 ++-- test/graph/cycleCounting.cpp | 6 +-- test/graph/euler.cpp | 10 ++-- test/graph/floydWarshall.cpp | 4 +- test/graph/havelHakimi.cpp | 12 ++--- test/graph/reroot.cpp | 2 +- test/graph/stoerWagner.cpp | 4 +- test/graph/treeIsomorphism.cpp | 8 +-- test/graph/virtualTree.cpp | 8 +-- test/math/berlekampMassey.cpp | 8 +-- test/math/bigint.cpp | 4 +- test/math/binomial0.cpp | 2 +- test/math/binomial1.cpp | 2 +- test/math/binomial2.cpp | 2 +- test/math/binomial3.cpp | 2 +- test/math/gauss.cpp | 18 +++---- test/math/inversions.cpp | 2 +- test/math/inversionsMerge.cpp | 4 +- test/math/kthperm.cpp | 4 +- test/math/lgsFp.cpp | 12 ++--- test/math/linearRecurrence.cpp | 6 +-- test/math/linearRecurrenceNTT.cpp | 6 +-- test/math/linearRecurrenceOld.cpp | 6 +-- test/math/linearSieve.cpp | 2 +- test/math/longestIncreasingSubsequence.cpp | 13 +++-- test/math/matrixPower.cpp | 20 ++++---- test/math/millerRabin.base32.cpp | 2 +- test/math/millerRabin.cpp | 2 +- test/math/permIndex.cpp | 6 +-- test/math/polynomial.cpp | 16 +++--- test/math/primeSieve.cpp | 4 +- test/math/primitiveRoot.cpp | 2 +- test/math/transforms/fft.cpp | 8 +-- test/math/transforms/fftMul.cpp | 10 ++-- test/math/transforms/multiplyBitwise.cpp | 6 +-- test/math/transforms/multiplyFFT.cpp | 6 +-- test/math/transforms/multiplyNTT.cpp | 6 +-- test/math/transforms/seriesOperations.cpp | 8 +-- test/other/bitOps.cpp | 6 +-- test/other/josephus2.cpp | 4 +- test/other/josephusK.cpp | 4 +- test/other/pbs.cpp | 6 +-- test/other/sos.cpp | 4 +- test/string/deBruijn.cpp | 10 ++-- test/string/duval.cpp | 12 ++--- test/string/kmp.cpp | 4 +- test/string/longestCommonSubsequence.cpp | 12 ++--- test/string/lyndon.cpp | 12 ++--- test/string/manacher.cpp | 10 ++-- test/string/rollingHash.cpp | 20 ++++---- test/string/rollingHashCf.cpp | 20 ++++---- test/string/suffixArray.cpp | 10 ++-- test/string/suffixAutomaton.cpp | 8 +-- test/string/suffixTree.cpp | 8 +-- test/string/z.cpp | 6 +-- test/util.h | 25 +++++----- 166 files changed, 665 insertions(+), 678 deletions(-) diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp index c20c61d..bdbf5f9 100644 --- a/content/datastructures/lichao.cpp +++ b/content/datastructures/lichao.cpp @@ -1,5 +1,6 @@ vector xs; // IMPORTANT: Initialize before constructing! -int findX(int i) { return lower_bound(all(xs), i) - begin(xs); } +int findX(int i) { + return ranges::lower_bound(xs, i) - begin(xs); } struct Fun { // Default: Linear function. Change as needed. ll m, c; @@ -11,7 +12,7 @@ struct Lichao { 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) {} + Lichao() : n(ssize(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {} void _insert(Fun f, int l, int r, int i) { while (i < 2 * cap) { diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index 2bdeccf..295acc4 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -12,15 +12,14 @@ struct Envelope { } void add(ll m, ll b) { - while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) { - ls.pop_back(); - } + while (ssize(ls) > 1 + && bad(ls.end()[-2], ls.back(), {m,b})) ls.pop_back(); ls.push_back({m, b}); - ptr = min(ptr, (int)sz(ls) - 1); + ptr = min(ptr, (int)ssize(ls) - 1); } ll query(ll x) { - while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + while (ptr < ssize(ls)-1 && ls[ptr+1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); } }; diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp index f26680d..9f38806 100644 --- a/content/datastructures/persistent.cpp +++ b/content/datastructures/persistent.cpp @@ -1,18 +1,18 @@ -template -struct persistent { - int& time; - vector> data; - - persistent(int& time, T value = {}) - : time(time), data(1, {2*time, value}) {} - - T get(int t) { - return prev(upper_bound(all(data),pair{2*t+1, T{}}))->second; - } - - int set(T value) { - time++; - data.push_back({2*time, value}); - return time; - } -}; +template +struct persistent { + int& time; + vector> data; + + persistent(int& time, T value = {}) + : time(time), data(1, {2*time, value}) {} + + T get(int t) { + return prev(ranges::upper_bound(data,pair{2*t+1, T{}}))->second; + } + + int set(T value) { + time++; + data.push_back({2*time, value}); + return time; + } +}; diff --git a/content/datastructures/sparseTable.cpp b/content/datastructures/sparseTable.cpp index 5e84236..44989ab 100644 --- a/content/datastructures/sparseTable.cpp +++ b/content/datastructures/sparseTable.cpp @@ -7,10 +7,10 @@ struct SparseTable { } void init(vector &vec) { - int n = sz(vec); + int n = ssize(vec); a = vec.data(); st.assign(__lg(n) + 1, vector(n)); - iota(all(st[0]), 0); + iota(begin(st[0]), end(st[0]), 0); for (int j = 0; (2 << j) <= n; j++) { for (int i = 0; i + (2 << j) <= n; i++) { st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]); diff --git a/content/datastructures/sparseTableDisjoint.cpp b/content/datastructures/sparseTableDisjoint.cpp index 39c7caa..bcf6b2e 100644 --- a/content/datastructures/sparseTableDisjoint.cpp +++ b/content/datastructures/sparseTableDisjoint.cpp @@ -8,7 +8,7 @@ struct DisjointST { } void init(vector &vec) { - int n = sz(vec); + int n = ssize(vec); a = vec.data(); dst.assign(__lg(n) + 1, vector(n + 1, neutral)); for (int h = 0, l = 1; l <= n; h++, l *= 2) { diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp index c5a60e9..bddfdb4 100644 --- a/content/datastructures/treap.cpp +++ b/content/datastructures/treap.cpp @@ -66,7 +66,7 @@ struct Treap { void insert(int i, ll val) { // and i = val auto [left, right] = split(root, i); treap.emplace_back(val); - left = merge(left, sz(treap) - 1); + left = merge(left, ssize(treap) - 1); root = merge(left, right); } diff --git a/content/geometry/antipodalPoints.cpp b/content/geometry/antipodalPoints.cpp index 110cc74..b34b175 100644 --- a/content/geometry/antipodalPoints.cpp +++ b/content/geometry/antipodalPoints.cpp @@ -1,12 +1,12 @@ vector> antipodalPoints(vector& h) { - if (sz(h) < 2) return {}; + if (ssize(h) < 2) return {}; vector> result; for (int i = 0, j = 1; i < j; i++) { while (true) { result.push_back({i, j}); - if (cross(h[(i + 1) % sz(h)] - h[i], - h[(j + 1) % sz(h)] - h[j]) <= 0) break; - j = (j + 1) % sz(h); + if (cross(h[(i + 1) % ssize(h)] - h[i], + h[(j + 1) % ssize(h)] - h[j]) <= 0) break; + j = (j + 1) % ssize(h); }} return result; } diff --git a/content/geometry/closestPair.cpp b/content/geometry/closestPair.cpp index 9b115f3..bbefa67 100644 --- a/content/geometry/closestPair.cpp +++ b/content/geometry/closestPair.cpp @@ -4,12 +4,11 @@ ll rec(vector::iterator a, int l, int r) { ll midx = a[m].real(); ll ans = min(rec(a, l, m), rec(a, m, r)); - inplace_merge(a+l, a+m, a+r, [](const pt& x, const pt& y) { - return x.imag() < y.imag(); - }); + ranges::inplace_merge(a+l, a+m, a+r, {}, + [](pt x) { return imag(x); }); pt tmp[8]; - fill(all(tmp), a[l]); + ranges::fill(tmp, a[l]); for (int i = l + 1, next = 0; i < r; i++) { if (ll x = a[i].real() - midx; x * x < ans) { for (pt& p : tmp) ans = min(ans, norm(p - a[i])); @@ -19,9 +18,7 @@ ll rec(vector::iterator a, int l, int r) { return ans; } -ll shortestDist(vector a) { // sz(pts) > 1 - sort(all(a), [](const pt& x, const pt& y) { - return x.real() < y.real(); - }); - return rec(a.begin(), 0, sz(a)); +ll shortestDist(vector a) { // size(pts) > 1 + ranges::sort(a, {}, [](pt x) { return real(x); }); + return rec(a.begin(), 0, ssize(a)); } diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp index 1173924..03c6343 100644 --- a/content/geometry/convexHull.cpp +++ b/content/geometry/convexHull.cpp @@ -1,18 +1,16 @@ vector convexHull(vector pts){ - sort(all(pts), [](const pt& a, const pt& b){ - return real(a) == real(b) ? imag(a) < imag(b) - : real(a) < real(b); - }); - pts.erase(unique(all(pts)), pts.end()); + ranges::sort(pts, {}, + [](pt x) { return pair{real(x), imag(x)}; }); + pts.erase(begin(ranges::unique(pts)), end(pts)); int k = 0; - 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--; - h[k++] = *it; + vector h(2 * ssize(pts)); + auto half = [&](auto &&v, int t) { + for (auto x: v) { + while (k > t && cross(h[k-2], h[k-1], x) <= 0) k--; + h[k++] = x; }}; - half(all(pts), 1); // Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. + half(pts, 1); // Untere Hülle. + half(pts | views::reverse | views::drop(1), k); // Obere Hülle h.resize(k); return h; } diff --git a/content/geometry/delaunay.cpp b/content/geometry/delaunay.cpp index 5672b57..9ae9061 100644 --- a/content/geometry/delaunay.cpp +++ b/content/geometry/delaunay.cpp @@ -99,12 +99,10 @@ pair rec(IT l, IT r) { } vector delaunay(vector pts) { - if (sz(pts) <= 2) return {}; - sort(all(pts), [](const pt& a, const pt& b) { - if (real(a) != real(b)) return real(a) < real(b); - return imag(a) < imag(b); - }); - QuadEdge* r = rec(all(pts)).first; + if (ssize(pts) <= 2) return {}; + ranges::sort(pts, {}, + [](pt x) { return pair{real(x), imag(x)}; }); + QuadEdge* r = rec(begin(pts), end(pts)).first; vector edges = {r}; while (cross(r->onext->dest(), r->dest(), r->orig) < 0) r = r->onext; auto add = [&](QuadEdge* e){ @@ -118,7 +116,7 @@ vector delaunay(vector pts) { }; add(r); pts.clear(); - for (int i = 0; i < sz(edges); i++) { + for (int i = 0; i < ssize(edges); i++) { if (!edges[i]->used) add(edges[i]); } return pts; diff --git a/content/geometry/geometry.tex b/content/geometry/geometry.tex index 976fb4d..9290de4 100644 --- a/content/geometry/geometry.tex +++ b/content/geometry/geometry.tex @@ -18,6 +18,7 @@ \end{itemize} \sourcecode{geometry/convexHull.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{Rotating calipers} \begin{methods} diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp index db34179..985ee24 100644 --- a/content/geometry/linesAndSegments.cpp +++ b/content/geometry/linesAndSegments.cpp @@ -28,9 +28,7 @@ pt projectToLine(pt a, pt b, pt p) { // sortiert alle Punkte pts auf einer Linie entsprechend dir void sortLine(pt dir, vector& pts) { // (2d und 3d) - sort(all(pts), [&](pt a, pt b){ - return dot(dir, a) < dot(dir, b); - }); + ranges::sort(pts, {}, [&](pt x) { return dot(dir, x); }); } // Liegt p auf der Strecke a-b? (nutze < für inberhalb) diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index b9ecebb..626162a 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -2,7 +2,7 @@ // Punkte gegen den Uhrzeigersinn: positiv, sonst negativ. double area(const vector& poly) { //poly[0] == poly.back() ll res = 0; - for (int i = 0; i + 1 < sz(poly); i++) + for (int i = 0; i + 1 < ssize(poly); i++) res += cross(poly[i], poly[i + 1]); return 0.5 * res; } @@ -13,7 +13,7 @@ double area(const vector& poly) { //poly[0] == poly.back() // selbstschneidenden Polygonen (definitions Sache) ll windingNumber(pt p, const vector& poly) { ll res = 0; - for (int i = 0; i + 1 < sz(poly); i++) { + for (int i = 0; i + 1 < ssize(poly); i++) { pt a = poly[i], b = poly[i + 1]; if (real(a) > real(b)) swap(a, b); if (real(a) <= real(p) && real(p) < real(b) && @@ -27,7 +27,7 @@ ll windingNumber(pt p, const vector& poly) { // Ändere Zeile 32 falls rand zählt, poly[0] == poly.back() bool inside(pt p, const vector& poly) { bool in = false; - for (int i = 0; i + 1 < sz(poly); i++) { + for (int i = 0; i + 1 < ssize(poly); i++) { pt a = poly[i], b = poly[i + 1]; if (pointOnSegment(a, b, p)) return false; if (real(a) > real(b)) swap(a,b); @@ -41,7 +41,7 @@ bool inside(pt p, const vector& poly) { // convex hull without duplicates, h[0] != h.back() // apply comments if border counts as inside bool insideConvex(pt p, const vector& hull) { - int l = 0, r = sz(hull) - 1; + int l = 0, r = ssize(hull) - 1; if (cross(hull[0], hull[r], p) >= 0) return false; // > 0 while (l + 1 < r) { int m = (l + r) / 2; @@ -52,11 +52,9 @@ bool insideConvex(pt p, const vector& hull) { } void rotateMin(vector& hull) { - auto mi = min_element(all(hull), [](const pt& a, const pt& b){ - return real(a) == real(b) ? imag(a) < imag(b) - : real(a) < real(b); - }); - rotate(hull.begin(), mi, hull.end()); + auto mi = ranges::min_element(hull, {}, + [](pt a) { return pair{real(a), imag(a)}; }); + ranges::rotate(hull, mi); } // convex hulls without duplicates, h[0] != h.back() @@ -68,7 +66,7 @@ vector minkowski(vector ps, vector qs) { ps.push_back(ps[1]); qs.push_back(qs[1]); vector res; - for (ll i = 0, j = 0; i + 2 < sz(ps) || j + 2 < sz(qs);) { + for (ll i = 0, j = 0; i + 2 < ssize(ps) || j + 2 < ssize(qs);) { res.push_back(ps[i] + qs[j]); auto c = cross(ps[i + 1] - ps[i], qs[j + 1] - qs[j]); if(c >= 0) i++; @@ -84,7 +82,7 @@ double dist(const vector& ps, vector qs) { p.push_back(p[0]); double res = INF; bool intersect = true; - for (ll i = 0; i + 1 < sz(p); i++) { + for (ll i = 0; i + 1 < ssize(p); i++) { intersect &= cross(p[i], p[i+1]) >= 0; res = min(res, distToSegment(p[i], p[i+1], 0)); } @@ -99,7 +97,7 @@ bool left(pt of, pt p) { return cross(p, of) < 0 || // returns index of corner where dot(dir, corner) is maximized int extremal(const vector& hull, pt dir) { dir *= pt(0, 1); - int l = 0, r = sz(hull) - 1; + int l = 0, r = ssize(hull) - 1; while (l + 1 < r) { int m = (l + r) / 2; pt dm = hull[m+1]-hull[m]; @@ -111,7 +109,7 @@ int extremal(const vector& hull, pt dir) { if (cross(dir, dm) < 0) l = m; else r = m; }} - return r % (sz(hull) - 1); + return r % (ssize(hull) - 1); } // convex hulls without duplicates, hull[0] == hull.back() and @@ -127,7 +125,7 @@ vector intersectLine(const vector& hull, pt a, pt b) { if (cross(hull[endA], a, b) > 0 || cross(hull[endB], a, b) < 0) return {}; - int n = sz(hull) - 1; + int n = ssize(hull) - 1; vector res; for (auto _ : {0, 1}) { int l = endA, r = endB; diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp index afc01b2..9fdbdb8 100644 --- a/content/geometry/segmentIntersection.cpp +++ b/content/geometry/segmentIntersection.cpp @@ -39,10 +39,10 @@ pair intersect(vector& segs) { events.push_back({s.a, s.id, 1}); events.push_back({s.b, s.id, -1}); } - sort(all(events)); + ranges::sort(events, less{}); set q; - vector::iterator> where(sz(segs)); + vector::iterator> where(ssize(segs)); for (auto e : events) { int id = e.id; if (e.type > 0) { diff --git a/content/geometry/sortAround.cpp b/content/geometry/sortAround.cpp index 9b09808..7e9d1de 100644 --- a/content/geometry/sortAround.cpp +++ b/content/geometry/sortAround.cpp @@ -3,7 +3,7 @@ bool left(pt p) { return real(p) < 0 || // counter clockwise, starting with "11:59" void sortAround(pt p, vector& ps) { - sort(all(ps), [&](const pt& a, const pt& b){ + ranges::sort(ps, [&](const pt& a, const pt& b){ if (left(a - p) != left(b - p)) return left(a - p) > left(b - p); return cross(p, a, b) > 0; diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp index e391948..22a9082 100644 --- a/content/graph/LCA_sparse.cpp +++ b/content/graph/LCA_sparse.cpp @@ -5,9 +5,9 @@ struct LCA { SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@ void init(vector>& adj, int root) { - depth.assign(2 * sz(adj), 0); - visited.assign(2 * sz(adj), -1); - first.assign(sz(adj), 2 * sz(adj)); + depth.assign(2 * ssize(adj), 0); + visited.assign(2 * ssize(adj), -1); + first.assign(ssize(adj), 2 * ssize(adj)); idx = 0; dfs(adj, root); st.init(depth); @@ -18,7 +18,7 @@ struct LCA { first[v] = min(idx, first[v]), idx++; for (int u : adj[v]) { - if (first[u] == 2 * sz(adj)) { + if (first[u] == 2 * ssize(adj)) { dfs(adj, u, d + 1); visited[idx] = v, depth[idx] = d, idx++; }}} diff --git a/content/graph/TSP.cpp b/content/graph/TSP.cpp index 6223858..4d2479c 100644 --- a/content/graph/TSP.cpp +++ b/content/graph/TSP.cpp @@ -1,7 +1,7 @@ vector> dist; // Entfernung zwischen je zwei Punkten. auto TSP() { - int n = sz(dist), m = 1 << n; + int n = ssize(dist), m = 1 << n; vector> dp(n, vector(m, edge{INF, -1})); for (int c = 0; c < n; c++) @@ -21,7 +21,7 @@ auto TSP() { vector tour = {0}; int v = 0; - while (tour.back() != 0 || sz(tour) == 1) + while (tour.back() != 0 || ssize(tour) == 1) tour.push_back(dp[tour.back()] [(v |= (1 << tour.back()))].to); // Enthält Knoten 0 zweimal. An erster und letzter Position. diff --git a/content/graph/articulationPoints.cpp b/content/graph/articulationPoints.cpp index 25ff67e..60970e6 100644 --- a/content/graph/articulationPoints.cpp +++ b/content/graph/articulationPoints.cpp @@ -14,14 +14,14 @@ int dfs(int v, int from = -1) { if (num[e.to] < me) st.push_back(e); } else { if (v == root) rootCount++; - int si = sz(st); + int si = ssize(st); int up = dfs(e.to, e.id); top = min(top, up); if (up >= me) isArt[v] = true; if (up > me) bridges.push_back(e); if (up <= me) st.push_back(e); if (up == me) { - bcc.emplace_back(si + all(st)); + bcc.emplace_back(begin(st) + si, end(st)); st.resize(si); }}} return top; @@ -29,12 +29,12 @@ int dfs(int v, int from = -1) { void find() { counter = 0; - num.assign(sz(adj), 0); - isArt.assign(sz(adj), false); + num.assign(ssize(adj), 0); + isArt.assign(ssize(adj), false); bridges.clear(); st.clear(); bcc.clear(); - for (int v = 0; v < sz(adj); v++) { + for (int v = 0; v < ssize(adj); v++) { if (!num[v]) { root = v; rootCount = 0; diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index a6f4c6e..eeff156 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -1,10 +1,10 @@ vector> dist; // Initialisiere mit Entfernungen zwischen Punkten. auto bitonicTSP() { - vector dp(sz(dist), HUGE_VAL); - vector pre(sz(dist)); // nur für Tour + vector dp(ssize(dist), HUGE_VAL); + vector pre(ssize(dist)); // nur für Tour dp[0] = 0; dp[1] = 2 * dist[0][1]; pre[1] = 0; - for (unsigned int i = 2; i < sz(dist); i++) { + for (unsigned int i = 2; i < ssize(dist); i++) { double link = 0; for (int j = i - 2; j >= 0; j--) { link += dist[j + 1][j + 2]; @@ -15,7 +15,7 @@ auto bitonicTSP() { }}} // return dp.back(); // Länge der Tour - int j, n = sz(dist) - 1; + int j, n = ssize(dist) - 1; vector ut, lt = {n, n - 1}; do { j = pre[n]; @@ -25,7 +25,7 @@ auto bitonicTSP() { } } while(n = j + 1, j > 0); (lt.back() == 1 ? lt : ut).push_back(0); - reverse(all(lt)); - lt.insert(lt.end(), all(ut)); + ranges::reverse(lt); + lt.insert(end(lt), begin(ut), end(ut)); 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 cacfb9c..b6d72d8 100644 --- a/content/graph/bitonicTSPsimple.cpp +++ b/content/graph/bitonicTSPsimple.cpp @@ -3,7 +3,7 @@ vector> dp; double get(int p1, int p2) { int v = max(p1, p2) + 1; - if (v == sz(dist)) return dist[p1][v - 1] + dist[p2][v - 1]; + if (v == ssize(dist)) return dist[p1][v - 1] + dist[p2][v - 1]; if (dp[p1][p2] >= 0.0) return dp[p1][p2]; double tryLR = dist[p1][v] + get(v, p2); double tryRL = dist[p2][v] + get(p1, v); @@ -11,17 +11,19 @@ double get(int p1, int p2) { } auto bitonicTSP() { - dp = vector>(sz(dist), - vector(sz(dist), -1)); + dp = vector>(ssize(dist), + vector(ssize(dist), -1)); get(0, 0); - // return dp[0][0]; // Länger der Tour + // return dp[0][0]; // Länge der Tour vector lr = {0}, rl = {0}; - for (int p1 = 0, p2 = 0, v; (v = max(p1, p2)+1) < sz(dist);) { + for (int p1 = 0, p2 = 0, v; + (v = max(p1, p2)+1) < ssize(dist);) { if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { lr.push_back(v); p1 = v; } else { 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. + // Enthält Knoten 0 zweimal. An erster und letzter Position. + return lr; } diff --git a/content/graph/blossom.cpp b/content/graph/blossom.cpp index 7bd494a..3c9bd31 100644 --- a/content/graph/blossom.cpp +++ b/content/graph/blossom.cpp @@ -32,7 +32,7 @@ struct GM { auto h = label[r] = label[s] = {~x, y}; int join; while (true) { - if (s != sz(adj)) swap(r, s); + if (s != ssize(adj)) swap(r, s); r = findFirst(label[pairs[r]].first); if (label[r] == h) { join = r; @@ -48,13 +48,13 @@ struct GM { }}} bool augment(int v) { - label[v] = {sz(adj), -1}; - first[v] = sz(adj); + label[v] = {ssize(adj), -1}; + first[v] = ssize(adj); head = tail = 0; for (que[tail++] = v; head < tail;) { int x = que[head++]; for (int y : adj[x]) { - if (pairs[y] == sz(adj) && y != v) { + if (pairs[y] == ssize(adj) && y != v) { pairs[y] = x; rematch(x, y); return true; @@ -70,12 +70,12 @@ struct GM { int match() { int matching = head = tail = 0; - for (int v = 0; v < sz(adj); v++) { - if (pairs[v] < sz(adj) || !augment(v)) continue; + for (int v = 0; v < ssize(adj); v++) { + if (pairs[v] < ssize(adj) || !augment(v)) continue; matching++; for (int i = 0; i < tail; i++) label[que[i]] = label[pairs[que[i]]] = {-1, -1}; - label[sz(adj)] = {-1, -1}; + label[ssize(adj)] = {-1, -1}; } return matching; } diff --git a/content/graph/bronKerbosch.cpp b/content/graph/bronKerbosch.cpp index 0cfcc5f..cf07c88 100644 --- a/content/graph/bronKerbosch.cpp +++ b/content/graph/bronKerbosch.cpp @@ -11,7 +11,7 @@ void bronKerboschRec(bits R, bits P, bits X) { } else { int q = min(P._Find_first(), X._Find_first()); bits cands = P & ~adj[q]; - for (int i = 0; i < sz(adj); i++) if (cands[i]) { + for (int i = 0; i < ssize(adj); i++) if (cands[i]) { R[i] = 1; bronKerboschRec(R, P & adj[i], X & adj[i]); R[i] = P[i] = 0; @@ -20,5 +20,5 @@ void bronKerboschRec(bits R, bits P, bits X) { void bronKerbosch() { cliques.clear(); - bronKerboschRec({}, {(1ull << sz(adj)) - 1}, {}); + bronKerboschRec({}, {(1ull << ssize(adj)) - 1}, {}); } diff --git a/content/graph/centroid.cpp b/content/graph/centroid.cpp index 820945b..3cd5519 100644 --- a/content/graph/centroid.cpp +++ b/content/graph/centroid.cpp @@ -15,7 +15,7 @@ pair dfs_cent(int v, int from, int n) { } pair find_centroid(int root = 0) { - s.resize(sz(adj)); + s.resize(ssize(adj)); dfs_sz(root); return dfs_cent(root, -1, s[root]); } diff --git a/content/graph/cycleCounting.cpp b/content/graph/cycleCounting.cpp index 471d399..65bf1a0 100644 --- a/content/graph/cycleCounting.cpp +++ b/content/graph/cycleCounting.cpp @@ -9,8 +9,8 @@ struct cycles { cycles(int n) : adj(n), seen(n), paths(n) {} void addEdge(int u, int v) { - adj[u].push_back({v, sz(edges)}); - adj[v].push_back({u, sz(edges)}); + adj[u].push_back({v, ssize(edges)}); + adj[v].push_back({u, ssize(edges)}); edges.push_back({u, v}); } @@ -38,8 +38,8 @@ struct cycles { bool isCycle(cycle cur) { // cycle must be constrcuted from base if (cur.none()) return false; - init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ - for (int i = 0; i < sz(edges); i++) { + init(ssize(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ + for (int i = 0; i < ssize(edges); i++) { if (cur[i]) { cur[i] = false; if (findSet(edges[i].first) == @@ -50,12 +50,12 @@ struct cycles { } int count() { - for (int i = 0; i < sz(adj); i++) findBase(i); - assert(sz(base) < 30); + for (int i = 0; i < ssize(adj); i++) findBase(i); + assert(ssize(base) < 30); int res = 0; - for (int i = 1; i < (1 << sz(base)); i++) { + for (int i = 1; i < (1 << ssize(base)); i++) { cycle cur; - for (int j = 0; j < sz(base); j++) + for (int j = 0; j < ssize(base); j++) if (((i >> j) & 1) != 0) cur ^= base[j]; if (isCycle(cur)) res++; } diff --git a/content/graph/dijkstra.cpp b/content/graph/dijkstra.cpp index 61c636d..4c1c9d8 100644 --- a/content/graph/dijkstra.cpp +++ b/content/graph/dijkstra.cpp @@ -2,8 +2,8 @@ using path = pair; //dist, destination auto dijkstra(const vector>& adj, int start) { priority_queue, greater> pq; - vector dist(sz(adj), INF); - vector prev(sz(adj), -1); + vector dist(ssize(adj), INF); + vector prev(ssize(adj), -1); dist[start] = 0; pq.emplace(0, start); while (!pq.empty()) { diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp index 2e58a2d..c8c34a8 100644 --- a/content/graph/dinic.cpp +++ b/content/graph/dinic.cpp @@ -8,12 +8,12 @@ int s, t; vector pt, dist; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u]) - 1, 0, 0}); } bool bfs() { - dist.assign(sz(adj), -1); + dist.assign(ssize(adj), -1); dist[s] = 0; queue q({s}); while (!q.empty() && dist[t] < 0) { @@ -28,7 +28,7 @@ bool bfs() { ll dfs(int v, ll flow = INF) { if (v == t || flow == 0) return flow; - for (; pt[v] < sz(adj[v]); pt[v]++) { + for (; pt[v] < ssize(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; ll cur = dfs(e.to, min(e.c - e.f, flow)); @@ -44,7 +44,7 @@ ll maxFlow(int source, int target) { s = source, t = target; ll flow = 0; while (bfs()) { - pt.assign(sz(adj), 0); + pt.assign(ssize(adj), 0); ll cur; do { cur = dfs(s); diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp index 0974b78..0082c05 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinicScaling.cpp @@ -8,12 +8,12 @@ int s, t; vector pt, dist; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u]) - 1, 0, 0}); } bool bfs(ll lim) { - dist.assign(sz(adj), -1); + dist.assign(ssize(adj), -1); dist[s] = 0; queue q({s}); while (!q.empty() && dist[t] < 0) { @@ -28,7 +28,7 @@ bool bfs(ll lim) { ll dfs(int v, ll flow) { if (v == t || flow == 0) return flow; - for (; pt[v] < sz(adj[v]); pt[v]++) { + for (; pt[v] < ssize(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; ll cur = dfs(e.to, min(e.c - e.f, flow)); @@ -45,7 +45,7 @@ ll maxFlow(int source, int target) { ll flow = 0; for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { while (bfs(lim)) { - pt.assign(sz(adj), 0); + pt.assign(ssize(adj), 0); ll cur; do { cur = dfs(s, lim); diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp index a5ea192..c506d58 100644 --- a/content/graph/euler.cpp +++ b/content/graph/euler.cpp @@ -3,16 +3,16 @@ vector to, validIdx, cycle; vector used; void addEdge(int u, int v) { - idx[u].push_back(sz(to)); + idx[u].push_back(ssize(to)); to.push_back(v); used.push_back(false); - idx[v].push_back(sz(to)); // für ungerichtet + idx[v].push_back(ssize(to)); // für ungerichtet to.push_back(u); used.push_back(false); } void euler(int v) { // init idx und validIdx - for (;validIdx[v] < sz(idx[v]); validIdx[v]++) { + for (;validIdx[v] < ssize(idx[v]); validIdx[v]++) { if (!used[idx[v][validIdx[v]]]) { int u = to[idx[v][validIdx[v]]]; used[idx[v][validIdx[v]]] = true; diff --git a/content/graph/floydWarshall.cpp b/content/graph/floydWarshall.cpp index df096c2..1a1138d 100644 --- a/content/graph/floydWarshall.cpp +++ b/content/graph/floydWarshall.cpp @@ -2,16 +2,16 @@ vector> dist; // Entfernung zwischen je zwei Punkten. vector> next; void floydWarshall() { - next.assign(sz(dist), vector(sz(dist), -1)); - for (int i = 0; i < sz(dist); i++) { - for (int j = 0; j < sz(dist); j++) { + next.assign(ssize(dist), vector(ssize(dist), -1)); + for (int i = 0; i < ssize(dist); i++) { + for (int j = 0; j < ssize(dist); j++) { if (dist[i][j] < INF) { next[i][j] = j; }}} - for (int k = 0; k < sz(dist); k++) { - for (int i = 0; i < sz(dist); i++) { - for (int j = 0; j < sz(dist); j++) { + for (int k = 0; k < ssize(dist); k++) { + for (int i = 0; i < ssize(dist); i++) { + for (int j = 0; j < ssize(dist); j++) { // only needed if dist can be negative if (dist[i][k] == INF || dist[k][j] == INF) continue; if (dist[i][j] > dist[i][k] + dist[k][j]) { diff --git a/content/graph/havelHakimi.cpp b/content/graph/havelHakimi.cpp index ac4d67d..9f4c081 100644 --- a/content/graph/havelHakimi.cpp +++ b/content/graph/havelHakimi.cpp @@ -1,12 +1,12 @@ vector> havelHakimi(const vector& deg) { priority_queue> pq; - for (int i = 0; i < sz(deg); i++) { + for (int i = 0; i < ssize(deg); i++) { if (deg[i] > 0) pq.push({deg[i], i}); } - vector> adj(sz(deg)); + vector> adj(ssize(deg)); while (!pq.empty()) { auto [degV, v] = pq.top(); pq.pop(); - if (sz(pq) < degV) return {}; //impossible + if (ssize(pq) < degV) return {}; //impossible vector> todo(degV); for (auto& e : todo) e = pq.top(), pq.pop(); for (auto [degU, u] : todo) { diff --git a/content/graph/hld.cpp b/content/graph/hld.cpp index 65d3f5c..e365b13 100644 --- a/content/graph/hld.cpp +++ b/content/graph/hld.cpp @@ -21,7 +21,7 @@ void dfs_hld(int v = 0, int from = -1) { } void init(int root = 0) { - int n = sz(adj); + int n = ssize(adj); sz.assign(n, 1), nxt.assign(n, root), par.assign(n, -1); in.resize(n), out.resize(n); counter = 0; diff --git a/content/graph/hopcroftKarp.cpp b/content/graph/hopcroftKarp.cpp index 7c0fec5..d07bd3a 100644 --- a/content/graph/hopcroftKarp.cpp +++ b/content/graph/hopcroftKarp.cpp @@ -21,7 +21,7 @@ bool bfs(int l) { } bool dfs(int v) { - for (; ptr[v] < sz(adj[v]); ptr[v]++) { + for (; ptr[v] < ssize(adj[v]); ptr[v]++) { int u = adj[v][ptr[v]]; if (pairs[u] < 0 || (dist[pairs[u]] > dist[v] && dfs(pairs[u]))) { @@ -33,7 +33,7 @@ bool dfs(int v) { int hopcroft_karp(int l) { // l = #Knoten links int ans = 0; - pairs.assign(sz(adj), -1); + pairs.assign(ssize(adj), -1); dist.resize(l); // Greedy Matching, optionale Beschleunigung. for (int v = 0; v < l; v++) for (int u : adj[v]) diff --git a/content/graph/kruskal.cpp b/content/graph/kruskal.cpp index 987d30b..d42800d 100644 --- a/content/graph/kruskal.cpp +++ b/content/graph/kruskal.cpp @@ -1,4 +1,4 @@ -sort(all(edges)); +ranges::sort(edges, less{}); vector mst; ll cost = 0; for (Edge& e : edges) { diff --git a/content/graph/kuhn.cpp b/content/graph/kuhn.cpp index e928387..688c846 100644 --- a/content/graph/kuhn.cpp +++ b/content/graph/kuhn.cpp @@ -12,7 +12,7 @@ bool dfs(int v) { } int kuhn(int l) { // l = #Knoten links. - pairs.assign(sz(adj), -1); + pairs.assign(ssize(adj), -1); int ans = 0; // Greedy Matching. Optionale Beschleunigung. for (int v = 0; v < l; v++) for (int u : adj[v]) diff --git a/content/graph/matching.cpp b/content/graph/matching.cpp index dcaea8c..3619d7c 100644 --- a/content/graph/matching.cpp +++ b/content/graph/matching.cpp @@ -3,19 +3,19 @@ vector> adj, mat; int max_matching() { int ans = 0; - mat.assign(sz(adj), {}); + mat.assign(ssize(adj), {}); for (int _ = 0; _ < I; _++) { - for (int v = 0; v < sz(adj); v++) { - mat[v].assign(sz(adj), 0); + for (int v = 0; v < ssize(adj); v++) { + mat[v].assign(ssize(adj), 0); for (int u : adj[v]) { if (u < v) { mat[v][u] = rand() % (MOD - 1) + 1; mat[u][v] = MOD - mat[v][u]; }}} - gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ + gauss(ssize(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ int rank = 0; for (auto& row : mat) { - if (*max_element(all(row)) != 0) rank++; + if (*ranges::max_element(row) != 0) rank++; } ans = max(ans, rank / 2); } diff --git a/content/graph/maxWeightBipartiteMatching.cpp b/content/graph/maxWeightBipartiteMatching.cpp index a2b0a80..b6f6ddf 100644 --- a/content/graph/maxWeightBipartiteMatching.cpp +++ b/content/graph/maxWeightBipartiteMatching.cpp @@ -45,6 +45,6 @@ double match(int l, int r) { yx[y] = aug[y]; swap(y, xy[aug[y]]); }} - return accumulate(all(lx), 0.0) + - accumulate(all(ly), 0.0); // Wert des Matchings + return accumulate(begin(lx), end(lx), 0.0) + + accumulate(begin(ly), end(ly), 0.0); // Wert des Matchings } diff --git a/content/graph/minCostMaxFlow.cpp b/content/graph/minCostMaxFlow.cpp index 14a222c..fde95f3 100644 --- a/content/graph/minCostMaxFlow.cpp +++ b/content/graph/minCostMaxFlow.cpp @@ -15,16 +15,16 @@ struct MinCostFlow { adj(n), s(source), t(target) {}; void addEdge(int u, int v, ll c, ll cost) { - adj[u].push_back(sz(edges)); + adj[u].push_back(ssize(edges)); edges.push_back({v, c, cost}); - adj[v].push_back(sz(edges)); + adj[v].push_back(ssize(edges)); edges.push_back({u, 0, -cost}); } bool SPFA() { - pref.assign(sz(adj), -1); - dist.assign(sz(adj), INF); - vector inqueue(sz(adj)); + pref.assign(ssize(adj), -1); + dist.assign(ssize(adj), INF); + vector inqueue(ssize(adj)); queue queue; dist[s] = 0; queue.push(s); @@ -59,7 +59,7 @@ struct MinCostFlow { }} void mincostflow() { - con.assign(sz(adj), 0); + con.assign(ssize(adj), 0); maxflow = mincost = 0; while (SPFA()) extend(); } diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp index ec36026..c569df2 100644 --- a/content/graph/pushRelabel.cpp +++ b/content/graph/pushRelabel.cpp @@ -9,8 +9,8 @@ vector ec; vector cur, H; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u])-1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u])-1, 0, 0}); } void addFlow(Edge& e, ll f) { @@ -23,7 +23,7 @@ void addFlow(Edge& e, ll f) { } ll maxFlow(int s, int t) { - int n = sz(adj); + int n = ssize(adj); hs.assign(2*n, {}); ec.assign(n, 0); cur.assign(n, 0); @@ -38,9 +38,9 @@ ll maxFlow(int s, int t) { int v = hs[hi].back(); hs[hi].pop_back(); while (ec[v] > 0) { - if (cur[v] == sz(adj[v])) { + if (cur[v] == ssize(adj[v])) { H[v] = 2*n; - for (int i = 0; i < sz(adj[v]); i++) { + for (int i = 0; i < ssize(adj[v]); i++) { Edge& e = adj[v][i]; if (e.c - e.f > 0 && H[v] > H[e.to] + 1) { diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 379c839..5a9c9d1 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -26,11 +26,11 @@ struct Reroot { pref.push_back(takeChild(v, u, w, dp[u])); } auto suf = pref; - partial_sum(all(pref), pref.begin(), comb); + partial_sum(begin(pref), end(pref), begin(pref), comb); exclusive_scan(suf.rbegin(), suf.rend(), suf.rbegin(), E, comb); - for (int i = 0; i < sz(adj[v]); i++) { + for (int i = 0; i < ssize(adj[v]); i++) { auto [u, w] = adj[v][i]; if (u == from) continue; dp[v] = fin(v, comb(pref[i], suf[i + 1])); @@ -40,7 +40,7 @@ struct Reroot { } auto solve() { - dp.assign(sz(adj), E); + dp.assign(ssize(adj), E); dfs0(0); dfs1(0); return dp; diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp index 32f1099..6887712 100644 --- a/content/graph/scc.cpp +++ b/content/graph/scc.cpp @@ -23,11 +23,11 @@ void visit(int v) { }}} void scc() { - inStack.assign(sz(adj), false); - low.assign(sz(adj), -1); - idx.assign(sz(adj), -1); + inStack.assign(ssize(adj), false); + low.assign(ssize(adj), -1); + idx.assign(ssize(adj), -1); counter = sccCounter = 0; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp index 0a6f653..a122488 100644 --- a/content/graph/stoerWagner.cpp +++ b/content/graph/stoerWagner.cpp @@ -7,7 +7,7 @@ vector> adj, tmp; vector erased; void merge(int u, int v) { - tmp[u].insert(tmp[u].end(), all(tmp[v])); + tmp[u].insert(end(tmp[u]), begin(tmp[v]), end(tmp[v])); tmp[v].clear(); erased[v] = true; for (auto& vec : tmp) { @@ -19,13 +19,13 @@ void merge(int u, int v) { ll stoer_wagner() { ll res = INF; tmp = adj; - erased.assign(sz(tmp), false); - for (int i = 1; i < sz(tmp); i++) { + erased.assign(ssize(tmp), false); + for (int i = 1; i < ssize(tmp); i++) { int s = 0; while (erased[s]) s++; priority_queue> pq; pq.push({0, s}); - vector con(sz(tmp)); + vector con(ssize(tmp)); ll cur = 0; vector> state; while (!pq.empty()) { diff --git a/content/graph/treeIsomorphism.cpp b/content/graph/treeIsomorphism.cpp index 355fefb..8c2ca21 100644 --- a/content/graph/treeIsomorphism.cpp +++ b/content/graph/treeIsomorphism.cpp @@ -7,9 +7,9 @@ int treeLabel(int v, int from = -1) { if (u == from) continue; children.push_back(treeLabel(u, v)); } - sort(all(children)); + ranges::sort(children); if (known.find(children) == known.end()) { - known[children] = sz(known); + known[children] = ssize(known); } return known[children]; } diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp index 153ed0b..81ba001 100644 --- a/content/graph/virtualTree.cpp +++ b/content/graph/virtualTree.cpp @@ -2,14 +2,14 @@ vector in, out; void virtualTree(vector ind) { // indices of used nodes - sort(all(ind), [&](int x, int y) { return in[x] < in[y]; }); - for (int i = 1, n = sz(ind); i < n; i++) { + ranges::sort(ind, {}, [&](int x) { return in[x]; }); + for (int i = 1, n = ssize(ind); i < n; i++) { ind.push_back(lca(ind[i - 1], ind[i])); } - sort(all(ind), [&](int x, int y) { return in[x] < in[y]; }); - ind.erase(unique(all(ind)), ind.end()); + ranges::sort(ind, {}, [&](int x) { return in[x]; }); + ind.erase(begin(ranges::unique(ind)), end(ind)); - int n = sz(ind); + int n = ssize(ind); vector> tree(n); vector st = {0}; for (int i = 1; i < n; i++) { diff --git a/content/math/berlekampMassey.cpp b/content/math/berlekampMassey.cpp index 29e084f..85a1031 100644 --- a/content/math/berlekampMassey.cpp +++ b/content/math/berlekampMassey.cpp @@ -1,6 +1,6 @@ constexpr ll mod = 1'000'000'007; vector BerlekampMassey(const vector& s) { - int n = sz(s), L = 0, m = 0; + int n = ssize(s), L = 0, m = 0; vector C(n), B(n), T; C[0] = B[0] = 1; diff --git a/content/math/bigint.cpp b/content/math/bigint.cpp index 4dad2be..a40f515 100644 --- a/content/math/bigint.cpp +++ b/content/math/bigint.cpp @@ -22,10 +22,11 @@ struct bigint { bigint operator+(const bigint& v) const { if (sign == v.sign) { bigint res = v; - for (ll i = 0, carry = 0; i < max(sz(a), sz(v.a)) || carry; ++i) { - if (i == sz(res.a)) + for (ll i = 0, carry = 0; + i < max(ssize(a), ssize(v.a)) || carry; ++i) { + if (i == ssize(res.a)) res.a.push_back(0); - res.a[i] += carry + (i < sz(a) ? a[i] : 0); + res.a[i] += carry + (i < ssize(a) ? a[i] : 0); carry = res.a[i] >= base; if (carry) res.a[i] -= base; @@ -39,8 +40,8 @@ struct bigint { if (sign == v.sign) { if (abs() >= v.abs()) { bigint res = *this; - for (ll i = 0, carry = 0; i < sz(v.a) || carry; ++i) { - res.a[i] -= carry + (i < sz(v.a) ? v.a[i] : 0); + for (ll i = 0, carry = 0; i < ssize(v.a) || carry; ++i) { + res.a[i] -= carry + (i < ssize(v.a) ? v.a[i] : 0); carry = res.a[i] < 0; if (carry) res.a[i] += base; } @@ -54,8 +55,8 @@ struct bigint { void operator*=(ll v) { if (v < 0) sign = -sign, v = -v; - for (ll i = 0, carry = 0; i < sz(a) || carry; ++i) { - if (i == sz(a)) a.push_back(0); + for (ll i = 0, carry = 0; i < ssize(a) || carry; ++i) { + if (i == ssize(a)) a.push_back(0); ll cur = a[i] * v + carry; carry = cur / base; a[i] = cur % base; @@ -74,12 +75,12 @@ struct bigint { bigint a = a1.abs() * norm; bigint b = b1.abs() * norm; bigint q, r; - q.a.resize(sz(a.a)); - for (ll i = sz(a.a) - 1; i >= 0; i--) { + q.a.resize(ssize(a.a)); + for (ll i = ssize(a.a) - 1; i >= 0; i--) { r *= base; r += a.a[i]; - ll s1 = sz(r.a) <= sz(b.a) ? 0 : r.a[sz(b.a)]; - ll s2 = sz(r.a) <= sz(b.a) - 1 ? 0 : r.a[sz(b.a) - 1]; + ll s1 = ssize(r.a) <= ssize(b.a) ? 0 : r.a[ssize(b.a)]; + ll s2 = ssize(r.a) <= ssize(b.a) - 1 ? 0 : r.a[ssize(b.a) - 1]; ll d = (base * s1 + s2) / b.a.back(); r -= b * d; while (r < 0) r += b, --d; @@ -102,7 +103,7 @@ struct bigint { void operator/=(ll v) { if (v < 0) sign = -sign, v = -v; - for (ll i = sz(a) - 1, rem = 0; i >= 0; --i) { + for (ll i = ssize(a) - 1, rem = 0; i >= 0; --i) { ll cur = a[i] + rem * base; a[i] = cur / v; rem = cur % v; @@ -119,7 +120,7 @@ struct bigint { ll operator%(ll v) const { if (v < 0) v = -v; ll m = 0; - for (ll i = sz(a) - 1; i >= 0; --i) + for (ll i = ssize(a) - 1; i >= 0; --i) m = (a[i] + m * base) % v; return m * sign; } @@ -139,9 +140,9 @@ struct bigint { bool operator<(const bigint& v) const { if (sign != v.sign) return sign < v.sign; - if (sz(a) != sz(v.a)) - return sz(a) * sign < sz(v.a) * v.sign; - for (ll i = sz(a) - 1; i >= 0; i--) + if (ssize(a) != ssize(v.a)) + return ssize(a) * sign < ssize(v.a) * v.sign; + for (ll i = ssize(a) - 1; i >= 0; i--) if (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign; return false; @@ -169,7 +170,7 @@ struct bigint { } bool isZero() const { - return a.empty() || (sz(a) == 1 && a[0] == 0); + return a.empty() || (ssize(a) == 1 && a[0] == 0); } bigint operator-() const { @@ -186,7 +187,7 @@ struct bigint { ll longValue() const { ll res = 0; - for (ll i = sz(a) - 1; i >= 0; i--) + for (ll i = ssize(a) - 1; i >= 0; i--) res = res * base + a[i]; return res * sign; } @@ -195,11 +196,11 @@ struct bigint { sign = 1; a.clear(); ll pos = 0; - while (pos < sz(s) && (s[pos] == '-' || s[pos] == '+')) { + while (pos < ssize(s) && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } - for (ll i = sz(s) - 1; i >= pos; i -= base_digits) { + for (ll i = ssize(s) - 1; i >= pos; i -= base_digits) { ll x = 0; for (ll j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0'; @@ -218,13 +219,13 @@ struct bigint { friend ostream& operator<<(ostream& stream, const bigint& v) { if (v.sign == -1) stream << '-'; stream << (v.a.empty() ? 0 : v.a.back()); - for (ll i = sz(v.a) - 2; i >= 0; --i) + for (ll i = ssize(v.a) - 2; i >= 0; --i) stream << setw(base_digits) << setfill('0') << v.a[i]; return stream; } static vll karatsubaMultiply(const vll& a, const vll& b) { - ll n = sz(a); + ll n = ssize(a); vll res(n + n); if (n <= 32) { for (ll i = 0; i < n; i++) @@ -242,25 +243,25 @@ struct bigint { for (ll i = 0; i < k; i++) a2[i] += a1[i]; for (ll i = 0; i < k; i++) b2[i] += b1[i]; vll r = karatsubaMultiply(a2, b2); - for (ll i = 0; i < sz(a1b1); i++) r[i] -= a1b1[i]; - for (ll i = 0; i < sz(a2b2); i++) r[i] -= a2b2[i]; - for (ll i = 0; i < sz(r); i++) res[i + k] += r[i]; - for (ll i = 0; i < sz(a1b1); i++) res[i] += a1b1[i]; - for (ll i = 0; i < sz(a2b2); i++) res[i + n] += a2b2[i]; + for (ll i = 0; i < ssize(a1b1); i++) r[i] -= a1b1[i]; + for (ll i = 0; i < ssize(a2b2); i++) r[i] -= a2b2[i]; + for (ll i = 0; i < ssize(r); i++) res[i + k] += r[i]; + for (ll i = 0; i < ssize(a1b1); i++) res[i] += a1b1[i]; + for (ll i = 0; i < ssize(a2b2); i++) res[i + n] += a2b2[i]; return res; } bigint operator*(const bigint& v) const { vll ta(a.begin(), a.end()); vll va(v.a.begin(), v.a.end()); - while (sz(ta) < sz(va)) ta.push_back(0); - while (sz(va) < sz(ta)) va.push_back(0); - while (sz(ta) & (sz(ta) - 1)) + while (ssize(ta) < ssize(va)) ta.push_back(0); + while (ssize(va) < ssize(ta)) va.push_back(0); + while (ssize(ta) & (ssize(ta) - 1)) ta.push_back(0), va.push_back(0); vll ra = karatsubaMultiply(ta, va); bigint res; res.sign = sign * v.sign; - for (ll i = 0, carry = 0; i < sz(ra); i++) { + for (ll i = 0, carry = 0; i < ssize(ra); i++) { ll cur = ra[i] + carry; res.a.push_back(cur % base); carry = cur / base; diff --git a/content/math/discreteLogarithm.cpp b/content/math/discreteLogarithm.cpp index 68866e0..844bd27 100644 --- a/content/math/discreteLogarithm.cpp +++ b/content/math/discreteLogarithm.cpp @@ -5,11 +5,11 @@ ll dlog(ll a, ll b, ll m) { //a > 0! vals[i] = {e, i}; } vals.emplace_back(m, 0); - sort(all(vals)); + ranges::sort(vals); ll fact = powMod(a, m - bound - 1, m); for (ll i = 0; i < m; i += bound, b = (b * fact) % m) { - auto it = lower_bound(all(vals), pair{b, 0}); + auto it = ranges::lower_bound(vals, pair{b, 0}); if (it->first == b) { return (i + it->second) % m; }} diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp index d431e52..719f573 100644 --- a/content/math/gauss.cpp +++ b/content/math/gauss.cpp @@ -7,7 +7,7 @@ void takeAll(int n, int line) { for (int i = 0; i < n; i++) { if (i == line) continue; double diff = mat[i][line]; - for (int j = 0; j < sz(mat[i]); j++) { + for (int j = 0; j < ssize(mat[i]); j++) { mat[i][j] -= diff * mat[line][j]; }}} @@ -22,7 +22,7 @@ int gauss(int n) { if (abs(mat[i][i]) > EPS) { normalLine(i); takeAll(n, i); - done[i] = true; + done[i] = true; }} for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung bool allZero = true; diff --git a/content/math/inversions.cpp b/content/math/inversions.cpp index 9e47f9b..289161f 100644 --- a/content/math/inversions.cpp +++ b/content/math/inversions.cpp @@ -1,7 +1,7 @@ ll inversions(const vector& v) { Tree> t; //ordered statistics tree @\sourceref{datastructures/pbds.cpp}@ ll res = 0; - for (ll i = 0; i < sz(v); i++) { + for (ll i = 0; i < ssize(v); i++) { res += i - t.order_of_key({v[i], i}); t.insert({v[i], i}); } diff --git a/content/math/inversionsMerge.cpp b/content/math/inversionsMerge.cpp index 8235b11..50fe37b 100644 --- a/content/math/inversionsMerge.cpp +++ b/content/math/inversionsMerge.cpp @@ -2,26 +2,26 @@ ll merge(vector& v, vector& left, vector& right) { int a = 0, b = 0, i = 0; ll inv = 0; - while (a < sz(left) && b < sz(right)) { + while (a < ssize(left) && b < ssize(right)) { if (left[a] < right[b]) v[i++] = left[a++]; else { - inv += sz(left) - a; + inv += ssize(left) - a; v[i++] = right[b++]; } } - while (a < sz(left)) v[i++] = left[a++]; - while (b < sz(right)) v[i++] = right[b++]; + while (a < ssize(left)) v[i++] = left[a++]; + while (b < ssize(right)) v[i++] = right[b++]; return inv; } ll mergeSort(vector &v) { // Sortiert v und gibt Inversionszahl zurück. - int n = sz(v); + int n = ssize(v); vector left(n / 2), right((n + 1) / 2); for (int i = 0; i < n / 2; i++) left[i] = v[i]; for (int i = n / 2; i < n; i++) right[i - n / 2] = v[i]; ll result = 0; - if (sz(left) > 1) result += mergeSort(left); - if (sz(right) > 1) result += mergeSort(right); + if (ssize(left) > 1) result += mergeSort(left); + if (ssize(right) > 1) result += mergeSort(right); return result + merge(v, left, right); } diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index bf18c86..64e4c09 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -7,7 +7,7 @@ void takeAll(int n, int line, ll p) { for (int i = 0; i < n; i++) { if (i == line) continue; ll diff = mat[i][line]; - for (int j = 0; j < sz(mat[i]); j++) { + for (int j = 0; j < ssize(mat[i]); j++) { mat[i][j] -= (diff * mat[line][j]) % p; mat[i][j] = (mat[i][j] + p) % p; }}} diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp index a8adacd..eb04566 100644 --- a/content/math/linearRecurrence.cpp +++ b/content/math/linearRecurrence.cpp @@ -1,9 +1,9 @@ constexpr ll mod = 998244353; // oder ntt mul @\sourceref{math/transforms/ntt.cpp}@ vector mul(const vector& a, const vector& b) { - vector c(sz(a) + sz(b) - 1); - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + vector c(ssize(a) + ssize(b) - 1); + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { c[i+j] += a[i]*b[j] % mod; }} for (ll& x : c) x %= mod; @@ -11,7 +11,7 @@ vector mul(const vector& a, const vector& b) { } ll kthTerm(const vector& f, const vector& c, ll k) { - int n = sz(c); + int n = ssize(c); vector q(n + 1, 1); for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i]) % mod; vector p = mul(f, q); diff --git a/content/math/linearRecurrenceOld.cpp b/content/math/linearRecurrenceOld.cpp index 2501e64..f67398d 100644 --- a/content/math/linearRecurrenceOld.cpp +++ b/content/math/linearRecurrenceOld.cpp @@ -1,7 +1,7 @@ constexpr ll mod = 1'000'000'007; vector modMul(const vector& a, const vector& b, const vector& c) { - ll n = sz(c); + ll n = ssize(c); vector res(n * 2 + 1); for (int i = 0; i <= n; i++) { //a*b for (int j = 0; j <= n; j++) { @@ -18,8 +18,8 @@ vector modMul(const vector& a, const vector& b, } ll kthTerm(const vector& f, const vector& c, ll k) { - assert(sz(f) == sz(c)); - vector tmp(sz(c) + 1), a(sz(c) + 1); + assert(ssize(f) == ssize(c)); + vector tmp(ssize(c) + 1), a(ssize(c) + 1); tmp[0] = a[1] = 1; //tmp = (x^k) % c for (k++; k > 0; k /= 2) { @@ -28,6 +28,6 @@ ll kthTerm(const vector& f, const vector& c, ll k) { } ll res = 0; - for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod; + for (int i = 0; i < ssize(c); i++) res += (tmp[i+1] * f[i]) % mod; return res % mod; } diff --git a/content/math/longestIncreasingSubsequence.cpp b/content/math/longestIncreasingSubsequence.cpp index fcb63b4..e4863d0 100644 --- a/content/math/longestIncreasingSubsequence.cpp +++ b/content/math/longestIncreasingSubsequence.cpp @@ -1,8 +1,8 @@ vector lis(vector& a) { - int n = sz(a), len = 0; + int n = ssize(a), len = 0; vector dp(n, INF), dp_id(n), prev(n); for (int i = 0; i < n; i++) { - int pos = lower_bound(all(dp), a[i]) - dp.begin(); + int pos = ranges::lower_bound(dp, a[i]) - begin(dp); dp[pos] = a[i]; dp_id[pos] = i; prev[i] = pos ? dp_id[pos - 1] : -1; diff --git a/content/math/matrixPower.cpp b/content/math/matrixPower.cpp index d981e6e..0729c15 100644 --- a/content/math/matrixPower.cpp +++ b/content/math/matrixPower.cpp @@ -1,7 +1,7 @@ vector pows; void precalc(mat m) { - pows = {mat(sz(m.m), 1), m}; + pows = {mat(ssize(m.m), 1), m}; for (int i = 1; i < 60; i++) pows.push_back(pows[i] * pows[i]); } diff --git a/content/math/permIndex.cpp b/content/math/permIndex.cpp index 4cffc12..563b33a 100644 --- a/content/math/permIndex.cpp +++ b/content/math/permIndex.cpp @@ -1,12 +1,12 @@ ll permIndex(vector v) { Tree t; - reverse(all(v)); + ranges::reverse(v); for (ll& x : v) { t.insert(x); x = t.order_of_key(x); } ll res = 0; - for (int i = sz(v); i > 0; i--) { + for (int i = ssize(v); i > 0; i--) { res = res * i + v[i - 1]; } return res; diff --git a/content/math/piLegendre.cpp b/content/math/piLegendre.cpp index 46c8584..6401a4f 100644 --- a/content/math/piLegendre.cpp +++ b/content/math/piLegendre.cpp @@ -16,7 +16,7 @@ ll phi(ll n, ll k) { ll pi(ll n) { if (n < N) { // implement this as O(1) lookup for speedup! - return distance(primes.begin(), upper_bound(all(primes), n)); + return ranges::upper_bound(primes, n) - begin(primes); } else { ll k = pi(sqrtl(n) + 1); return n - phi(n, k) + k; diff --git a/content/math/polynomial.cpp b/content/math/polynomial.cpp index 4698a00..12a4fd7 100644 --- a/content/math/polynomial.cpp +++ b/content/math/polynomial.cpp @@ -4,7 +4,7 @@ struct poly { poly(int deg = 0) : data(1 + deg) {} poly(initializer_list _data) : data(_data) {} - int size() const { return sz(data); } + int size() const { return ssize(data); } void trim() { for (ll& x : data) x = (x % mod + mod) % mod; diff --git a/content/math/transforms/andTransform.cpp b/content/math/transforms/andTransform.cpp index 1fd9f5c..1e9cfc0 100644 --- a/content/math/transforms/andTransform.cpp +++ b/content/math/transforms/andTransform.cpp @@ -1,5 +1,5 @@ void fft(vector& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { for (int j = i; j < i + s; j++) { diff --git a/content/math/transforms/bitwiseTransforms.cpp b/content/math/transforms/bitwiseTransforms.cpp index 28561da..b98ea94 100644 --- a/content/math/transforms/bitwiseTransforms.cpp +++ b/content/math/transforms/bitwiseTransforms.cpp @@ -1,5 +1,5 @@ void bitwiseConv(vector& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { for (int j = i; j < i + s; j++) { diff --git a/content/math/transforms/fft.cpp b/content/math/transforms/fft.cpp index 2bd95b2..1f80e36 100644 --- a/content/math/transforms/fft.cpp +++ b/content/math/transforms/fft.cpp @@ -1,7 +1,7 @@ using cplx = complex; void fft(vector& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int i = 0, j = 1; j < n - 1; ++j) { for (int k = n >> 1; k > (i ^= k); k >>= 1); if (j < i) swap(a[i], a[j]); diff --git a/content/math/transforms/fftMul.cpp b/content/math/transforms/fftMul.cpp index 660ed79..da6a538 100644 --- a/content/math/transforms/fftMul.cpp +++ b/content/math/transforms/fftMul.cpp @@ -1,8 +1,8 @@ vector mul(vector& a, vector& b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); - vector c(all(a)), d(n); + int n = 1 << (__lg(ssize(a) + ssize(b) - 1) + 1); + vector c(begin(a), end(a)), d(n); c.resize(n); - for (int i = 0; i < sz(b); i++) c[i] = {real(c[i]), b[i]}; + for (int i = 0; i < ssize(b); i++) c[i] = {real(c[i]), b[i]}; fft(c); for (int i = 0; i < n; i++) { int j = (n - i) & (n - 1); diff --git a/content/math/transforms/multiplyBitwise.cpp b/content/math/transforms/multiplyBitwise.cpp index f7cf169..5275b8c 100644 --- a/content/math/transforms/multiplyBitwise.cpp +++ b/content/math/transforms/multiplyBitwise.cpp @@ -1,5 +1,5 @@ vector mul(vector a, vector b) { - int n = 1 << (__lg(2 * max(sz(a), sz(b)) - 1)); + int n = 1 << (__lg(2 * max(ssize(a), ssize(b)) - 1)); a.resize(n), b.resize(n); bitwiseConv(a), bitwiseConv(b); for (int i=0; i mul(vector& a, vector& b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); - vector a2(all(a)), b2(all(b)); + int n = 1 << (__lg(ssize(a) + ssize(b) - 1) + 1); + vector a2(begin(a), end(a)), b2(begin(b), end(b)); a2.resize(n), b2.resize(n); fft(a2), fft(b2); for (int i=0; i mul(vector a, vector b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); + int n = 1 << (__lg(ssize(a) + ssize(b) - 1) + 1); a.resize(n), b.resize(n); ntt(a), ntt(b); for (int i=0; i& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); auto b = a; ll r = inv ? powMod(root, mod - 2, mod) : root; diff --git a/content/math/transforms/orTransform.cpp b/content/math/transforms/orTransform.cpp index eb1da44..d0122bf 100644 --- a/content/math/transforms/orTransform.cpp +++ b/content/math/transforms/orTransform.cpp @@ -1,5 +1,5 @@ void fft(vector& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { for (int j = i; j < i + s; j++) { diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp index b405698..3d8aa11 100644 --- a/content/math/transforms/seriesOperations.cpp +++ b/content/math/transforms/seriesOperations.cpp @@ -17,7 +17,7 @@ vector poly_inv(const vector& a, int n) { } vector poly_deriv(vector a) { - for (int i = 1; i < sz(a); i++) + for (int i = 1; i < ssize(a); i++) a[i-1] = a[i] * i % mod; a.pop_back(); return a; @@ -25,11 +25,11 @@ vector poly_deriv(vector a) { vector poly_integr(vector a) { static vector inv = {0, 1}; - for (static int i = 2; i <= sz(a); i++) + for (static int i = 2; i <= ssize(a); i++) inv.push_back(mod - mod / i * inv[mod % i] % mod); a.push_back(0); - for (int i = sz(a) - 1; i > 0; i--) + for (int i = ssize(a) - 1; i > 0; i--) a[i] = a[i-1] * inv[i] % mod; a[0] = 0; return a; @@ -46,7 +46,7 @@ vector poly_exp(vector a, int n) { for (int len = 1; len < n; len *= 2) { vector 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 q2 = q; q2.resize(2*len); ntt(p), ntt(q2); diff --git a/content/math/transforms/xorTransform.cpp b/content/math/transforms/xorTransform.cpp index f9d1d82..075aac3 100644 --- a/content/math/transforms/xorTransform.cpp +++ b/content/math/transforms/xorTransform.cpp @@ -1,5 +1,5 @@ void fft(vector& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { for (int j = i; j < i + s; j++) { diff --git a/content/other/fastSubsetSum.cpp b/content/other/fastSubsetSum.cpp index 84396f6..38a84b6 100644 --- a/content/other/fastSubsetSum.cpp +++ b/content/other/fastSubsetSum.cpp @@ -1,11 +1,11 @@ int fastSubsetSum(vector w, int t){ int a = 0, b = 0; - while(b < sz(w) && a + w[b] <= t) a += w[b++]; - if(b == sz(w)) return a; - int m = *max_element(all(w)); + while(b < ssize(w) && a + w[b] <= t) a += w[b++]; + if(b == ssize(w)) return a; + int m = *ranges::max_element(w); vector dp(2*m, -1), old; dp[m+a-t] = b; - for(int i = b; i < sz(w); i++){ + for(int i = b; i < ssize(w); i++){ old = dp; for(int j = 0; j < m; j++){ dp[j+w[i]] = max(dp[j+w[i]], old[j]); @@ -18,4 +18,4 @@ int fastSubsetSum(vector w, int t){ } for(a = t; dp[m+a-t] < 0; a--); return a; -} \ No newline at end of file +} diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index f4db2fd..e6bfeac 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -7,7 +7,7 @@ while (true) { focus.emplace_back((low[i] + high[i]) / 2, i); }} if (focus.empty()) break; - sort(all(focus)); + ranges::sort(focus); // reset simulation for (int step = 0; auto [mid, i] : focus) { diff --git a/content/other/sos.cpp b/content/other/sos.cpp index 01bc44c..892a47c 100644 --- a/content/other/sos.cpp +++ b/content/other/sos.cpp @@ -1,6 +1,6 @@ vector res(in); -for (int i = 1; i < sz(res); i *= 2) { - for (int mask = 0; mask < sz(res); mask++){ +for (int i = 1; i < ssize(res); i *= 2) { + for (int mask = 0; mask < ssize(res); mask++){ if (mask & i) { res[mask] += res[mask ^ i]; }}} diff --git a/content/string/ahoCorasick.cpp b/content/string/ahoCorasick.cpp index c65e20a..d738961 100644 --- a/content/string/ahoCorasick.cpp +++ b/content/string/ahoCorasick.cpp @@ -4,7 +4,8 @@ struct AhoCorasick { int suffix = 0, ch, cnt = 0; array nxt = {}; - vert(int p, int c): suffix(-p), ch(c) { fill(all(nxt), -1); } + vert(int p, int c): + suffix(-p), ch(c) { ranges::fill(nxt, -1); } }; vector aho = {{0, -1}}; @@ -13,7 +14,7 @@ struct AhoCorasick { for (auto c : s) { int idx = c - OFFSET; if (aho[v].nxt[idx] == -1) { - aho[v].nxt[idx] = sz(aho); + aho[v].nxt[idx] = ssize(aho); aho.emplace_back(v, idx); } v = aho[v].nxt[idx]; @@ -37,9 +38,9 @@ struct AhoCorasick { vector> adj; vector dp; void buildGraph() { - adj.resize(sz(aho)); - dp.assign(sz(aho), 0); - for (int i = 1; i < sz(aho); i++) { + adj.resize(ssize(aho)); + dp.assign(ssize(aho), 0); + for (int i = 1; i < ssize(aho); i++) { adj[getSuffix(i)].push_back(i); }} diff --git a/content/string/deBruijn.cpp b/content/string/deBruijn.cpp index e829137..545dde7 100644 --- a/content/string/deBruijn.cpp +++ b/content/string/deBruijn.cpp @@ -1,7 +1,7 @@ string deBruijn(int n, char mi = '0', char ma = '1') { string res, c(1, mi); do { - if (n % sz(c) == 0) res += c; + if (n % ssize(c) == 0) res += c; } while(next(c, n, mi, ma)); return res; } diff --git a/content/string/duval.cpp b/content/string/duval.cpp index 253bae1..de94ebd 100644 --- a/content/string/duval.cpp +++ b/content/string/duval.cpp @@ -1,8 +1,8 @@ vector> duval(const string& s) { vector> res; - for (int i = 0; i < sz(s);) { + for (int i = 0; i < ssize(s);) { int j = i + 1, k = i; - for (; j < sz(s) && s[k] <= s[j]; j++) { + for (; j < ssize(s) && s[k] <= s[j]; j++) { if (s[k] < s[j]) k = i; else k++; } @@ -15,5 +15,5 @@ vector> duval(const string& s) { int minrotation(const string& s) { auto parts = duval(s+s); for (auto [l, r] : parts) { - if (r >= sz(s)) return l; + if (r >= ssize(s)) return l; }} diff --git a/content/string/kmp.cpp b/content/string/kmp.cpp index 421479e..a354aa7 100644 --- a/content/string/kmp.cpp +++ b/content/string/kmp.cpp @@ -1,7 +1,7 @@ vector kmpPreprocessing(const string& sub) { - vector b(sz(sub) + 1); + vector b(ssize(sub) + 1); b[0] = -1; - for (int i = 0, j = -1; i < sz(sub);) { + for (int i = 0, j = -1; i < ssize(sub);) { while (j >= 0 && sub[i] != sub[j]) j = b[j]; b[++i] = ++j; } @@ -9,10 +9,10 @@ vector kmpPreprocessing(const string& sub) { } vector kmpSearch(const string& s, const string& sub) { vector result, pre = kmpPreprocessing(sub); - for (int i = 0, j = 0; i < sz(s);) { + for (int i = 0, j = 0; i < ssize(s);) { while (j >= 0 && s[i] != sub[j]) j = pre[j]; i++; j++; - if (j == sz(sub)) { + if (j == ssize(sub)) { result.push_back(i - j); j = pre[j]; }} diff --git a/content/string/longestCommonSubsequence.cpp b/content/string/longestCommonSubsequence.cpp index 6c9ea44..14ca62c 100644 --- a/content/string/longestCommonSubsequence.cpp +++ b/content/string/longestCommonSubsequence.cpp @@ -1,12 +1,12 @@ string lcss(const string& a, const string& b) { - vector> m(sz(a) + 1, vector(sz(b) + 1)); - for (int i = sz(a) - 1; i >= 0; i--) { - for (int j = sz(b) - 1; j >= 0; j--) { + vector> m(ssize(a) + 1, vector(ssize(b) + 1)); + for (int i = ssize(a) - 1; i >= 0; i--) { + for (int j = ssize(b) - 1; j >= 0; j--) { if (a[i] == b[j]) m[i][j] = 1 + m[i+1][j+1]; else m[i][j] = max(m[i+1][j], m[i][j+1]); }} // Für die Länge: return m[0][0]; string res; - for (int j = 0, i = 0; j < sz(b) && i < sz(a);) { + for (int j = 0, i = 0; j < ssize(b) && i < ssize(a);) { if (a[i] == b[j]) res += a[i++], j++; else if (m[i][j+1] > m[i+1][j]) j++; else i++; diff --git a/content/string/lyndon.cpp b/content/string/lyndon.cpp index e44379b..cb477d4 100644 --- a/content/string/lyndon.cpp +++ b/content/string/lyndon.cpp @@ -1,5 +1,5 @@ bool next(string& s, int maxLen, char mi = '0', char ma = '1') { - for (int i = sz(s), j = sz(s); i < maxLen; i++) + for (int i = ssize(s), j = ssize(s); i < maxLen; i++) s.push_back(s[i % j]); while(!s.empty() && s.back() == ma) s.pop_back(); if (s.empty()) { diff --git a/content/string/manacher.cpp b/content/string/manacher.cpp index 112bd55..9fa2991 100644 --- a/content/string/manacher.cpp +++ b/content/string/manacher.cpp @@ -1,9 +1,9 @@ vector manacher(const string& t) { //transforms "aa" to ".a.a." to find even length palindromes - string s(sz(t) * 2 + 1, '.'); - for (int i = 0; i < sz(t); i++) s[2 * i + 1] = t[i]; + string s(ssize(t) * 2 + 1, '.'); + for (int i = 0; i < ssize(t); i++) s[2 * i + 1] = t[i]; - int mid = 0, r = 0, n = sz(s); + int mid = 0, r = 0, n = ssize(s); vector pal(n); for (int i = 1; i < n - 1; i++) { if (r > i) pal[i] = min(r - i, pal[2 * mid - i]); diff --git a/content/string/suffixArray.cpp b/content/string/suffixArray.cpp index 0e301b2..c49bdc9 100644 --- a/content/string/suffixArray.cpp +++ b/content/string/suffixArray.cpp @@ -4,19 +4,19 @@ struct SuffixArray { vector SA, LCP; vector> P; - SuffixArray(const string& s) : n(sz(s)), SA(n), LCP(n), + SuffixArray(const string& s) : n(ssize(s)), SA(n), LCP(n), P(__lg(2 * n - 1) + 1, vector(n)) { - P[0].assign(all(s)); - iota(all(SA), 0); - sort(all(SA), [&](int a, int b) { return s[a] < s[b]; }); + P[0].assign(begin(s), end(s)); + iota(begin(SA), end(SA), 0); + ranges::sort(SA, {}, [&](int x) { return s[x]; }); vector x(n); for (int k = 1, c = 1; c < n; k++, c *= 2) { - iota(all(x), n - c); + iota(begin(x), end(x), n - c); for (int ptr = c; int i : SA) if (i >= c) x[ptr++] = i - c; vector cnt(k == 1 ? MAX_CHAR : n); for (int i : P[k-1]) cnt[i]++; - partial_sum(all(cnt), begin(cnt)); + partial_sum(begin(cnt), end(cnt), begin(cnt)); for (int i : x | views::reverse) SA[--cnt[P[k-1][i]]] = i; auto p = [&](int i) { return i < n ? P[k-1][i] : -1; }; @@ -31,7 +31,7 @@ struct SuffixArray { int lcp(int x, int y) { if (x == y) return n - x; int res = 0; - for (int i = sz(P) - 1; i >= 0 && max(x, y) + res < n; i--) { + for (int i = ssize(P) - 1; i >= 0 && max(x, y) + res < n; i--) { if (P[i][x + res] == P[i][y + res]) res |= 1 << i; } return res; diff --git a/content/string/suffixAutomaton.cpp b/content/string/suffixAutomaton.cpp index d81a05d..f9aa80b 100644 --- a/content/string/suffixAutomaton.cpp +++ b/content/string/suffixAutomaton.cpp @@ -4,20 +4,20 @@ struct SuffixAutomaton { struct State { int len, link = -1; array nxt; // map if large Alphabet - State(int l): len(l) { fill(all(nxt), -1); } + State(int l): len(l) { ranges::fill(nxt, -1); } }; vector st = {State(0)}; int cur = 0; SuffixAutomaton(const string& s) { - st.reserve(2 * sz(s)); + st.reserve(2 * ssize(s)); for (auto c : s) extend(c - OFFSET); } void extend(int c) { int p = cur; - cur = sz(st); + cur = ssize(st); st.emplace_back(st[p].len + 1); for (; p != -1 && st[p].nxt[c] < 0; p = st[p].link) { st[p].nxt[c] = cur; @@ -33,9 +33,9 @@ struct SuffixAutomaton { st.back().link = st[q].link; st.back().nxt = st[q].nxt; for (; p != -1 && st[p].nxt[c] == q; p = st[p].link) { - st[p].nxt[c] = sz(st) - 1; + st[p].nxt[c] = ssize(st) - 1; } - st[q].link = st[cur].link = sz(st) - 1; + st[q].link = st[cur].link = ssize(st) - 1; }}} vector calculateTerminals() { @@ -49,7 +49,7 @@ struct SuffixAutomaton { // Pair with start index (in t) and length of LCS. pair longestCommonSubstring(const string& t) { int v = 0, l = 0, best = 0, bestp = -1; - for (int i = 0; i < sz(t); i++) { + for (int i = 0; i < ssize(t); i++) { int c = t[i] - OFFSET; while (v > 0 && st[v].nxt[c] < 0) { v = st[v].link; diff --git a/content/string/suffixTree.cpp b/content/string/suffixTree.cpp index 7112f39..6362c3e 100644 --- a/content/string/suffixTree.cpp +++ b/content/string/suffixTree.cpp @@ -11,12 +11,12 @@ struct SuffixTree { SuffixTree(const string& s_) : s(s_) { needsSuffix = remainder = curVert = curEdge = curLen = 0; pos = -1; - for (int i = 0; i < sz(s); i++) extend(); + for (int i = 0; i < ssize(s); i++) extend(); } int newVert(int start, int end) { tree.push_back({start, end, 0, {}}); - return sz(tree) - 1; + return ssize(tree) - 1; } void addSuffixLink(int vert) { @@ -42,7 +42,7 @@ struct SuffixTree { while (remainder) { if (curLen == 0) curEdge = pos; if (!tree[curVert].nxt.count(s[curEdge])) { - int leaf = newVert(pos, sz(s)); + int leaf = newVert(pos, ssize(s)); tree[curVert].nxt[s[curEdge]] = leaf; addSuffixLink(curVert); } else { @@ -56,7 +56,7 @@ struct SuffixTree { int split = newVert(tree[nxt].start, tree[nxt].start + curLen); tree[curVert].nxt[s[curEdge]] = split; - int leaf = newVert(pos, sz(s)); + int leaf = newVert(pos, ssize(s)); tree[split].nxt[s[pos]] = leaf; tree[nxt].start += curLen; tree[split].nxt[s[tree[nxt].start]] = nxt; @@ -69,4 +69,4 @@ struct SuffixTree { } else { curVert = tree[curVert].suf ? tree[curVert].suf : 0; }}} -}; \ No newline at end of file +}; diff --git a/content/string/trie.cpp b/content/string/trie.cpp index d5e092c..db39c43 100644 --- a/content/string/trie.cpp +++ b/content/string/trie.cpp @@ -3,7 +3,7 @@ constexpr int ALPHABET_SIZE = 2; struct node { int words, ends; array nxt; - node(): words(0), ends(0) { fill(all(nxt), -1); } + node(): words(0), ends(0) { ranges::fill(nxt, -1); } }; vector trie = {node()}; @@ -13,7 +13,7 @@ int traverse(const vector& word, int x) { if (id < 0 || (trie[id].words == 0 && x <= 0)) return -1; trie[id].words += x; if (trie[id].nxt[c] < 0 && x > 0) { - trie[id].nxt[c] = sz(trie); + trie[id].nxt[c] = ssize(trie); trie.emplace_back(); } id = trie[id].nxt[c]; diff --git a/content/string/z.cpp b/content/string/z.cpp index 069fa38..0d8cafb 100644 --- a/content/string/z.cpp +++ b/content/string/z.cpp @@ -1,5 +1,5 @@ vector Z(const string& s) { - int n = sz(s); + int n = ssize(s); vector z(n); for (int i = 1, x = 0; i < n; i++) { z[i] = max(0, min(z[i - x], x + z[x] - i)); diff --git a/content/template/template.cpp b/content/template/template.cpp index 7430d23..7c92f09 100644 --- a/content/template/template.cpp +++ b/content/template/template.cpp @@ -1,17 +1,15 @@ #include using namespace std; -#define tsolve int t; cin >> t; while(t--) solve -#define all(x) ::begin(x), ::end(x) -#define sz(x) (ll)::size(x) - +using ii = pair; +using vi = vector; using ll = long long; using ld = long double; -void solve() {} +void solve() { +} int main() { - cin.tie(0)->sync_with_stdio(false); - cout << setprecision(16); + cin.tie(0)->sync_with_stdio(0); solve(); } diff --git a/test/datastructures/LCT.cpp b/test/datastructures/LCT.cpp index 58d76d7..68a952c 100644 --- a/test/datastructures/LCT.cpp +++ b/test/datastructures/LCT.cpp @@ -73,13 +73,13 @@ struct Naive { } }; dfs_comp(dfs_comp, x); - return seen[Random::integer(sz(seen))]; + return seen[Random::integer(ssize(seen))]; } int randomAdj(int x) { if (adj[x].empty()) return -1; - vector seen(all(adj[x])); - return seen[Random::integer(sz(seen))]; + vector seen(begin(adj[x]), end(adj[x])); + return seen[Random::integer(ssize(seen))]; } }; @@ -179,7 +179,7 @@ void performance_test() { int a = Random::integer(0, N); int b = Random::integer(0, N); ll w = Random::integer(-1000, 1000); - + t.start(); if (!lct.connected(&lct.nodes[a], &lct.nodes[b])) { lct.link(&lct.nodes[a], &lct.nodes[b]); diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp index d50ca60..9a6ffb9 100644 --- a/test/datastructures/dynamicConvexHull.lichao.cpp +++ b/test/datastructures/dynamicConvexHull.lichao.cpp @@ -8,7 +8,7 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); xs = Random::distinct(n, -range, range); - sort(all(xs)); + ranges::sort(xs); HullDynamic hd; Lichao lichao; diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp index f4b797b..1639b3d 100644 --- a/test/datastructures/lichao.cpp +++ b/test/datastructures/lichao.cpp @@ -7,7 +7,7 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); xs = Random::distinct(n, -range, range); - sort(all(xs)); + ranges::sort(xs); vector naive(n, INF); Lichao tree; @@ -42,7 +42,7 @@ constexpr int N = 200'000; void performance_test() { timer t; xs = Random::distinct(N, -1'000'000'000, 1'000'000'000); - sort(all(xs)); + ranges::sort(xs); t.start(); Lichao tree; diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 3ae7c4d..98d74f8 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -12,12 +12,12 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); auto ms = Random::integers(n, -range, range); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto cs = ms; for (int l = 0, r = 0; l < n;) { while (r < n && ms[l] == ms[r]) r++; auto tmp = Random::distinct(r - l, -range, range); - sort(all(tmp), greater<>{}); + ranges::sort(tmp | views::reverse); for (int c : tmp) { cs[l] = c; l++; @@ -25,7 +25,7 @@ void stress_test(ll range) { } auto xs = Random::integers(n*100, -range*n, range*n); - sort(all(xs)); + ranges::sort(xs); int i = 0; vector naive; @@ -58,12 +58,12 @@ void stress_test_independent(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); auto ms = Random::integers(n, -range, range); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto cs = ms; for (int l = 0, r = 0; l < n;) { while (r < n && ms[l] == ms[r]) r++; auto tmp = Random::distinct(r - l, -range, range); - sort(all(tmp), greater<>{}); + ranges::sort(tmp | views::reverse); for (int c : tmp) { cs[l] = c; l++; @@ -81,7 +81,7 @@ void stress_test_independent(ll range) { naive.emplace_back(m, c); auto xs = Random::integers(100, -range, range); - sort(all(xs)); + ranges::sort(xs); auto tmp = mch; for (auto x : xs) { @@ -101,9 +101,9 @@ constexpr int N = 1'000'000; void performance_test() { timer t; auto ms = Random::distinct(N, -1'000'000'000, 1'000'000'000); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto xs = Random::distinct(N, -1'000'000'000, 1'000'000'000); - sort(all(xs)); + ranges::sort(xs); Envelope mch; hash_t hash = 0; diff --git a/test/datastructures/persistentArray.cpp b/test/datastructures/persistentArray.cpp index 6712089..ef8e52b 100644 --- a/test/datastructures/persistentArray.cpp +++ b/test/datastructures/persistentArray.cpp @@ -24,19 +24,19 @@ void stress_test() { cur[j] = x; expected.emplace_back(t, cur); } else if (op <= 16) { - if (sz(expected) < 1) continue; - int j = Random::integer(0, sz(expected)); + if (ssize(expected) < 1) continue; + int j = Random::integer(0, ssize(expected)); for (int k = 0; k < m; k++) { if (got.get(k, expected[j].first) != expected[j].second[k]) cerr << "got: " << got.get(k, expected[j].first) << ", expected: " << expected[j].second[k] << FAIL; } } else { - if (sz(expected) < 1) continue; - int j = Random::integer(0, sz(expected)); + if (ssize(expected) < 1) continue; + int j = Random::integer(0, ssize(expected)); got.reset(expected[j].first); expected.resize(j + 1); cur = expected.back().second; } - + } queries += n; } diff --git a/test/datastructures/segmentTree.cpp b/test/datastructures/segmentTree.cpp index fbac13e..2473724 100644 --- a/test/datastructures/segmentTree.cpp +++ b/test/datastructures/segmentTree.cpp @@ -47,7 +47,7 @@ void performance_test1() { int i = Random::integer(0, N); auto [l, r] = Random::pair(0, N + 1); ll x = Random::integer(-1000, 1000); - + t.start(); tree.update(i, x); hash ^= tree.query(l, r); @@ -68,7 +68,7 @@ void stress_test2() { vector naive(n); SegTree tree(naive); naive = Random::integers(n, -1000, 1000); - copy(all(naive), tree.tree.begin() + n); + ranges::copy(naive, tree.tree.begin() + n); for (int operations = 0; operations < 1000; operations++) { { int l = Random::integer(0, n + 1); @@ -102,7 +102,7 @@ void performance_test2() { int i = Random::integer(0, N); auto [l, r] = Random::pair(0, N + 1); ll x = Random::integer(-1000, 1000); - + t.start(); tree.modify(l, r, x); hash ^= tree.query(i); diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp index 2fc9d63..d93e0f4 100644 --- a/test/datastructures/treap.cpp +++ b/test/datastructures/treap.cpp @@ -26,14 +26,14 @@ void stress_test(int T, int n) { if (a.empty()) is_ins = true; if (is_ins) { - int ind = Random::integer(0, (int)sz(a)+1); + int ind = Random::integer(0, (int)ssize(a)+1); ll val = Random::integer((ll)-1e18, (ll)1e18+1); t.insert(ind, val); a.insert(a.begin() + ind, val); ins--; } else { - int ind = Random::integer(0, (int)sz(a)); - int cnt = Random::integer(1, 1 + min({(int)sz(a)-ind, rem, (int)sqrt(n)})); + int ind = Random::integer(0, (int)ssize(a)); + int cnt = Random::integer(1, 1 + min({(int)ssize(a)-ind, rem, (int)sqrt(n)})); t.remove(ind, cnt); a.erase(a.begin() + ind, a.begin() + ind + cnt); rem -= cnt; diff --git a/test/datastructures/waveletTree.cpp b/test/datastructures/waveletTree.cpp index d294835..e70d57b 100644 --- a/test/datastructures/waveletTree.cpp +++ b/test/datastructures/waveletTree.cpp @@ -20,7 +20,7 @@ void stress_test() { ll expected = -1; if (x >= 0 && l + x < r) { vector tmp(naive.begin() + l, naive.begin() + r); - std::sort(all(tmp)); + ranges::sort(tmp); expected = tmp[x]; } if (got != expected) { @@ -59,7 +59,7 @@ void performance_test() { auto [l2, r2] = Random::pair(0, N + 1); int x1 = Random::integer(l1, r1 + 1); ll x2 = Random::integer(-1000, 1000); - + t.start(); hash ^= tree.kth(l1, r1, x1); hash ^= tree.countSmaller(l2, r2, x2); diff --git a/test/geometry.h b/test/geometry.h index 0167d5c..06520c7 100644 --- a/test/geometry.h +++ b/test/geometry.h @@ -26,7 +26,7 @@ namespace Random { vector partition(ll n, std::size_t k){//min = 0; n += k; vector res = Random::distinct(k-1, 1, n); - sort(all(res)); + ranges::sort(res); res.emplace_back(n); ll last = 0; for (std::size_t i = 0; i < k; i++) { @@ -137,4 +137,4 @@ namespace Random { while (ccw(a, b, c) == 0) c = integerPoint(range); return {a, b, c}; } -} \ No newline at end of file +} diff --git a/test/geometry/antipodalPoints.cpp b/test/geometry/antipodalPoints.cpp index d20dfb6..013f43c 100644 --- a/test/geometry/antipodalPoints.cpp +++ b/test/geometry/antipodalPoints.cpp @@ -9,7 +9,7 @@ constexpr ll EPS = 0; #include "../geometry.h" vector> naive(vector ps) { - ll n = sz(ps); + ll n = ssize(ps); auto test = [&](int i, int j){ if (dot(ps[j] - ps[i], ps[i - 1] - ps[i]) <= 0) return false; if (dot(ps[j] - ps[i], ps[i + 1] - ps[i]) <= 0) return false; @@ -34,13 +34,13 @@ void stress_test(ll range) { auto got = antipodalPoints(ps); for (auto& [a, b] : got) if (a > b) swap(a, b); - sort(all(got)); + ranges::sort(got); auto expected = naive(ps); for (auto& [a, b] : expected) if (a > b) swap(a, b); for (auto x : expected) { - auto it = lower_bound(all(got), x); + auto it = ranges::lower_bound(got, x); if (it == got.end() || *it != x) cerr << "error" << FAIL; } queries += n; @@ -58,7 +58,7 @@ void performance_test() { auto got = antipodalPoints(ps); t.stop(); - hash_t hash = sz(got); + hash_t hash = ssize(got); if (t.time > 50) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/geometry/circle.cpp b/test/geometry/circle.cpp index 3d3d27d..dc975ff 100644 --- a/test/geometry/circle.cpp +++ b/test/geometry/circle.cpp @@ -46,9 +46,9 @@ void test_circleIntersection(ll range) { auto got = circleIntersection(c1, r1, c2, r2); - if (sz(got) != expectedCount(real(c1), imag(c1), r1, real(c2), imag(c2), r2)) cerr << "error: wrong count" << FAIL; + if (ssize(got) != expectedCount(real(c1), imag(c1), r1, real(c2), imag(c2), r2)) cerr << "error: wrong count" << FAIL; - for (int i = 0; i < sz(got); i++) { + for (int i = 0; i < ssize(got); i++) { for (int j = 0; j < i; j++) { if (abs(got[i] - got[j]) < 1e-6) cerr << "error: identical" << FAIL; } @@ -58,7 +58,7 @@ void test_circleIntersection(ll range) { if (float_error(abs(c1 - p), r1) > 1e-6) cerr << "error: 1" << FAIL; if (float_error(abs(c2 - p), r2) > 1e-6) cerr << "error: 2" << FAIL; } - queries += sz(got); + queries += ssize(got); } cerr << "tested circleIntersection: " << queries << endl; } @@ -91,9 +91,9 @@ void test_circleRayIntersection(ll range) { else expected = 1; } - if (sz(got) != expected) cerr << "error: wrong count" << FAIL; + if (ssize(got) != expected) cerr << "error: wrong count" << FAIL; - for (int i = 0; i < sz(got); i++) { + for (int i = 0; i < ssize(got); i++) { for (int j = 0; j < i; j++) { if (abs(got[i] - got[j]) < 1e-6) cerr << "error: identical" << FAIL; } @@ -103,7 +103,7 @@ void test_circleRayIntersection(ll range) { if (float_error(abs(c - p), r) > 1e-6) cerr << "error: 1" << FAIL; if (distToLine(orig, orig + dir, p) > 1e-6) cerr << "error: 2" << FAIL; } - queries += sz(got); + queries += ssize(got); } cerr << "tested circleIntersection: " << queries << endl; } diff --git a/test/geometry/closestPair.cpp b/test/geometry/closestPair.cpp index 5959b21..4e558dc 100644 --- a/test/geometry/closestPair.cpp +++ b/test/geometry/closestPair.cpp @@ -13,7 +13,7 @@ ll isqrt(ll x) {return (ll)sqrtl(x);} //strict convex hull ll naive(const vector& ps) { ll opt = LL::INF; - for (ll i = 0; i < sz(ps); i++) { + for (ll i = 0; i < ssize(ps); i++) { for (ll j = 0; j < i; j++) { opt = min(opt, norm(ps[i] - ps[j])); } diff --git a/test/geometry/closestPair.double.cpp b/test/geometry/closestPair.double.cpp index 2f8a1ab..9ef039f 100644 --- a/test/geometry/closestPair.double.cpp +++ b/test/geometry/closestPair.double.cpp @@ -10,7 +10,7 @@ constexpr ll INF = LL::INF; //strict convex hull double naive(const vector& ps) { double opt = LL::INF; - for (ll i = 0; i < sz(ps); i++) { + for (ll i = 0; i < ssize(ps); i++) { for (ll j = 0; j < i; j++) { opt = min(opt, norm(ps[i] - ps[j])); } diff --git a/test/geometry/convexHull.cpp b/test/geometry/convexHull.cpp index 788a634..0ca52a2 100644 --- a/test/geometry/convexHull.cpp +++ b/test/geometry/convexHull.cpp @@ -9,7 +9,7 @@ constexpr ll EPS = 0; //strict convex hull ll isConvexHull(const vector& ps, const vector& hull) { - ll n = sz(hull) - 1; + ll n = ssize(hull) - 1; if (n == 0) { for (pt p : ps) if (p != hull[0]) return 1; return 0; @@ -67,7 +67,7 @@ void performance_test() { t.start(); auto a = convexHull(ps); t.stop(); - hash_t hash = sz(a); + hash_t hash = ssize(a); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp index 5740b95..b824ad8 100644 --- a/test/geometry/delaunay.cpp +++ b/test/geometry/delaunay.cpp @@ -6,28 +6,27 @@ auto cross(pt p, pt a, pt b) {return cross(a - p, b - p);} #pragma GCC diagnostic ignored "-Wunused-variable" #include + vector convexHull(vector pts){ - sort(all(pts), [](const pt& a, const pt& b){ - return real(a) == real(b) ? imag(a) < imag(b) - : real(a) < real(b); - }); - pts.erase(unique(all(pts)), pts.end()); + ranges::sort(pts, {}, + [](pt x) { return pair{real(x), imag(x)}; }); + pts.erase(begin(ranges::unique(pts)), end(pts)); int k = 0; - 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! - h[k++] = *it; + vector h(2 * ssize(pts)); + auto half = [&](auto &&v, int t) { + for (auto x: v) { + while (k > t && cross(h[k-2], h[k-1], x) < 0) k--; // allow collinear points + h[k++] = x; }}; - half(all(pts), 1); // Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. + half(pts, 1); // Untere Hülle. + half(pts | views::reverse | views::drop(1), k); // Obere Hülle h.resize(k); return h; } lll area(const vector& poly) { //poly[0] == poly.back() lll res = 0; - for (int i = 0; i + 1 < sz(poly); i++) + for (int i = 0; i + 1 < ssize(poly); i++) res += cross(poly[i], poly[i + 1]); return res; } @@ -89,15 +88,15 @@ void stress_test(ll range) { hull.pop_back(); auto got = delaunay(ps); - if (sz(got) % 3 != 0) cerr << "error: not triangles" << FAIL; - if (sz(got) / 3 + sz(hull) - 3 + 1 != 2 * sz(ps) - 4) cerr << "error: wrong number" << FAIL; + if (ssize(got) % 3 != 0) cerr << "error: not triangles" << FAIL; + if (ssize(got) / 3 + ssize(hull) - 3 + 1 != 2 * ssize(ps) - 4) cerr << "error: wrong number" << FAIL; //all triangles should be oriented ccw lll gotArea = 0; - for (int i = 0; i < sz(got); i += 3) gotArea += cross(got[i], got[i+1], got[i+2]); + for (int i = 0; i < ssize(got); i += 3) gotArea += cross(got[i], got[i+1], got[i+2]); if (gotArea != expectedArea) cerr << "error: wrong area" << FAIL; - for (int i = 0; i < sz(got); i++) { + for (int i = 0; i < ssize(got); i++) { int ii = i + 1; if (i / 3 != ii / 3) ii -= 3; for (int j = 0; j < i; j++) { @@ -111,7 +110,7 @@ void stress_test(ll range) { for (pt p : ps) seen |= p == got[i]; if (!seen) cerr << "error: invalid point" << FAIL; } - for (int i = 0; i < sz(got); i += 3) { + for (int i = 0; i < ssize(got); i += 3) { for (pt p : ps) { if (p == got[i]) continue; if (p == got[i+1]) continue; @@ -131,7 +130,7 @@ void performance_test() { t.start(); auto got = delaunay(ps); t.stop(); - hash_t hash = sz(got); + hash_t hash = ssize(got); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/geometry/formulas.cpp b/test/geometry/formulas.cpp index d63d431..f472e1f 100644 --- a/test/geometry/formulas.cpp +++ b/test/geometry/formulas.cpp @@ -107,7 +107,7 @@ void test_uniqueAngle(ll range) { if (it->second != expected) cerr << "error: inconsistent" << FAIL; queries++; } - cerr << "tested uniqueAngle: " << queries << " (" << sz(seen) << ")" << endl; + cerr << "tested uniqueAngle: " << queries << " (" << ssize(seen) << ")" << endl; } int main() { diff --git a/test/geometry/hpi.cpp b/test/geometry/hpi.cpp index a2326bc..e22e8c6 100644 --- a/test/geometry/hpi.cpp +++ b/test/geometry/hpi.cpp @@ -1,4 +1,6 @@ #include "../util.h" +#define sz(X) (ll)::size(X) +#define all(X) ::begin(X), ::end(X) constexpr ll EPS = 0; #define double ll #define polar polar @@ -14,10 +16,10 @@ ll sgn(ll x) { //https://cp-algorithms.com/geometry/halfplane-intersection.html namespace cpalgo { // Redefine epsilon and infinity as necessary. Be mindful of precision errors. - const long double eps = 1e-9, inf = 1e9; + const long double eps = 1e-9, inf = 1e9; // Basic point/vector struct. - struct Point { + struct Point { long double x, y; explicit Point(long double x_ = 0, long double y_ = 0) : x(x_), y(y_) {} @@ -26,23 +28,23 @@ namespace cpalgo { // Addition, substraction, multiply by constant, dot product, cross product. friend Point operator + (const Point& p, const Point& q) { - return Point(p.x + q.x, p.y + q.y); + return Point(p.x + q.x, p.y + q.y); } - friend Point operator - (const Point& p, const Point& q) { - return Point(p.x - q.x, p.y - q.y); + friend Point operator - (const Point& p, const Point& q) { + return Point(p.x - q.x, p.y - q.y); } - friend Point operator * (const Point& p, const long double& k) { - return Point(p.x * k, p.y * k); - } + friend Point operator * (const Point& p, const long double& k) { + return Point(p.x * k, p.y * k); + } friend long double dot(const Point& p, const Point& q) { return p.x * q.x + p.y * q.y; } - friend long double cross(const Point& p, const Point& q) { - return p.x * q.y - p.y * q.x; + friend long double cross(const Point& p, const Point& q) { + return p.x * q.y - p.y * q.x; } friend std::ostream& operator<<(std::ostream& os, const Point& p) { @@ -53,10 +55,10 @@ namespace cpalgo { }; // Basic half-plane struct. - struct Halfplane { + struct Halfplane { // 'p' is a passing point of the line and 'pq' is the direction vector of the line. - Point p, pq; + Point p, pq; long double angle; Halfplane() {} @@ -66,16 +68,16 @@ namespace cpalgo { Halfplane(array ps) : Halfplane(ps[0], ps[1]) {} Halfplane(hp h) : Halfplane(h.from, h.to) {} - // Check if point 'r' is outside this half-plane. + // Check if point 'r' is outside this half-plane. // Every half-plane allows the region to the LEFT of its line. bool out(const Point& r) { - return cross(pq, r - p) < -eps; + return cross(pq, r - p) < -eps; } - // Comparator for sorting. - bool operator < (const Halfplane& e) const { + // Comparator for sorting. + bool operator < (const Halfplane& e) const { return angle < e.angle; - } + } // Intersection point of the lines of two half-planes. It is assumed they're never parallel. friend Point inter(const Halfplane& s, const Halfplane& t) { @@ -89,13 +91,13 @@ namespace cpalgo { }; // Actual algorithm - vector hp_intersect(vector& H) { + vector hp_intersect(vector& H) { /*Point box[4] = { // Bounding box in CCW order - Point(inf, inf), - Point(-inf, inf), - Point(-inf, -inf), - Point(inf, -inf) + Point(inf, inf), + Point(-inf, inf), + Point(-inf, -inf), + Point(inf, -inf) }; for(int i = 0; i<4; i++) { // Add bounding box half-planes. @@ -181,7 +183,7 @@ void test_check(ll range) { auto b = Random::line(range); auto c = b; while (cross(b[0] - b[1], c[0] - c[1]) == 0) c = Random::line(range); - + bool got = hp(a[0], a[1]).check(hp(b[0], b[1]), hp(c[0], c[1])); bool expected = naiveCheck(a, b, c); diff --git a/test/geometry/polygon.cpp b/test/geometry/polygon.cpp index 643ea70..29d3251 100644 --- a/test/geometry/polygon.cpp +++ b/test/geometry/polygon.cpp @@ -135,7 +135,7 @@ void test_insideConvex(ll range) { // convex hull without duplicates, h[0] != h.back() // apply comments if border counts as inside bool insideOrOnConvex(pt p, const vector& hull) { - int l = 0, r = sz(hull) - 1; + int l = 0, r = ssize(hull) - 1; if (cross(hull[0], hull[r], p) > 0) return false; while (l + 1 < r) { int m = (l + r) / 2; @@ -155,7 +155,7 @@ void test_minkowski(ll range) { auto got = minkowski(A, B); bool convex = true; - for (int i = 0; i < sz(got); i++) convex &= cross(got[i], got[(i+1) % sz(got)], got[(i+2) % sz(got)]) >= 0; + for (int i = 0; i < ssize(got); i++) convex &= cross(got[i], got[(i+1) % ssize(got)], got[(i+2) % ssize(got)]) >= 0; if (!convex) cerr << "error: not convex" << FAIL; for (pt a : A) { @@ -172,19 +172,19 @@ double naive_dist(const vector& ps, const vector& qs) { //check if intersect double res = LD::INF; bool intersect = true; - for (int i = 0; i < sz(qs); i++) { + for (int i = 0; i < ssize(qs); i++) { bool sep = true; for (pt p : ps) { - res = min(res, distToSegment(qs[i], qs[(i+1) % sz(qs)], p)); - sep &= cross(qs[i], qs[(i+1) % sz(qs)], p) <= 0; + res = min(res, distToSegment(qs[i], qs[(i+1) % ssize(qs)], p)); + sep &= cross(qs[i], qs[(i+1) % ssize(qs)], p) <= 0; } if (sep) intersect = false; } - for (int i = 0; i < sz(ps); i++) { + for (int i = 0; i < ssize(ps); i++) { bool sep = true; for (pt q : qs) { - res = min(res, distToSegment(ps[i], ps[(i+1) % sz(ps)], q)); - sep &= cross(ps[i], ps[(i+1) % sz(ps)], q) <= 0; + res = min(res, distToSegment(ps[i], ps[(i+1) % ssize(ps)], q)); + sep &= cross(ps[i], ps[(i+1) % ssize(ps)], q) <= 0; } if (sep) intersect = false; } @@ -263,10 +263,10 @@ void test_intersect(ll range) { } } } - if (sz(expected) > 1 && expected[0] == expected[1]) expected.pop_back(); + if (ssize(expected) > 1 && expected[0] == expected[1]) expected.pop_back(); - sort(all(got)); - sort(all(expected)); + ranges::sort(got); + ranges::sort(expected); if (got != expected) cerr << "error" << FAIL; diff --git a/test/geometry/segmentIntersection.cpp b/test/geometry/segmentIntersection.cpp index 6d3ddd6..5271563 100644 --- a/test/geometry/segmentIntersection.cpp +++ b/test/geometry/segmentIntersection.cpp @@ -40,7 +40,7 @@ vector randomSegs(int n, ll range) { } bool naive(vector& segs) { - for (ll i = 0; i < sz(segs); i++) { + for (ll i = 0; i < ssize(segs); i++) { for (ll j = 0; j < i; j++) { if (segmentIntersection(segs[i].a, segs[i].b, segs[j].a, segs[j].b)) return true; } diff --git a/test/geometry/sortAround.cpp b/test/geometry/sortAround.cpp index a27edc8..42ea86b 100644 --- a/test/geometry/sortAround.cpp +++ b/test/geometry/sortAround.cpp @@ -24,7 +24,7 @@ void test_tiny() { }; auto got = expected; for (int i = 0; i < 100'000; i++) { - shuffle(all(got), Random::rng); + ranges::shuffle(got, Random::rng); sortAround(0, got); if (got != expected) cerr << "error" << FAIL; } @@ -51,8 +51,8 @@ void stress_test(ll range) { auto isLeft = [&](pt p){return real(p - c) < 0 || (real(p - c) == 0 && imag(p - c) < 0);}; auto isCCW = [&](pt a, pt b){return cross(c, a, b) > 0;}; - if (!is_partitioned(all(ps), isLeft)) cerr << "error 1" << FAIL; - auto mid = partition_point(all(ps), isLeft); + if (!ranges::is_partitioned(ps, isLeft)) cerr << "error 1" << FAIL; + auto mid = ranges::partition_point(ps, isLeft); if (!is_sorted(ps.begin(), mid, isCCW)) cerr << "error 2" << FAIL; if (!is_sorted(mid, ps.end(), isCCW)) cerr << "error 3" << FAIL; queries += n; diff --git a/test/graph/TSP.cpp b/test/graph/TSP.cpp index f9aab2e..8a67409 100644 --- a/test/graph/TSP.cpp +++ b/test/graph/TSP.cpp @@ -7,9 +7,9 @@ constexpr ll INF = LL::INF; #include vector naive() { - int n = sz(dist); + int n = ssize(dist); vector todo(n - 1); - iota(all(todo), 1); + iota(begin(todo), end(todo), 1); vector res; ll best = LL::INF; do { @@ -26,7 +26,7 @@ vector naive() { res.insert(res.begin(), 0); res.push_back(0); } - } while (next_permutation(all(todo))); + } while (ranges::next_permutation(todo).found); return res; } @@ -39,7 +39,7 @@ void stress_test() { auto expected = naive(); auto got = TSP(); - + if (got != expected) cerr << "error" << FAIL; queries += n; } diff --git a/test/graph/articulationPoints.bcc.cpp b/test/graph/articulationPoints.bcc.cpp index 15f5cf2..cee2d0b 100644 --- a/test/graph/articulationPoints.bcc.cpp +++ b/test/graph/articulationPoints.bcc.cpp @@ -10,9 +10,9 @@ struct edge { vector> naiveBCC(int m) { init(m); - vector seen(sz(adj), -1); + vector seen(ssize(adj), -1); int run = 0; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { for (auto e : adj[i]) { run++; seen[i] = run; @@ -36,9 +36,9 @@ vector> naiveBCC(int m) { for (int i = 0; i < m; i++) { res[findSet(i)].push_back(i); } - for (auto& v : res) sort(all(v)); - res.erase(remove_if(all(res), [](const vector& v){return sz(v) <= 1;}), res.end()); - sort(all(res)); + for (auto& v : res) ranges::sort(v); + res.erase(begin(ranges::remove_if(res, [](const vector& v){return ssize(v) <= 1;})), end(res)); + ranges::sort(res); return res; } @@ -60,12 +60,12 @@ void stress_test_bcc() { auto expected = naiveBCC(nextId); find(); - vector> got(sz(bcc)); - for (int i = 0; i < sz(bcc); i++) { + vector> got(ssize(bcc)); + for (int i = 0; i < ssize(bcc); i++) { for (auto e : bcc[i]) got[i].push_back(e.id); - sort(all(got[i])); + ranges::sort(got[i]); } - sort(all(got)); + ranges::sort(got); if (got != expected) cerr << "error" << FAIL; queries += n; diff --git a/test/graph/articulationPoints.bridges.cpp b/test/graph/articulationPoints.bridges.cpp index a1b89d2..15408ea 100644 --- a/test/graph/articulationPoints.bridges.cpp +++ b/test/graph/articulationPoints.bridges.cpp @@ -7,10 +7,10 @@ struct edge { #undef Edge vector naiveBridges(const vector>& edges) { - vector res(sz(edges)); + vector res(ssize(edges)); - vector seen(sz(adj), -1); - for (int i = 0; i < sz(edges); i++) { + vector seen(ssize(adj), -1); + for (int i = 0; i < ssize(edges); i++) { auto [a, b] = edges[i]; vector todo = {a}; seen[a] = i; @@ -40,14 +40,14 @@ void stress_test_bridges() { adj.assign(n, {}); vector> edges; g.forEdges([&](int a, int b){ - adj[a].push_back({a, b, sz(edges)}); - adj[b].push_back({b, a, sz(edges)}); + adj[a].push_back({a, b, ssize(edges)}); + adj[b].push_back({b, a, ssize(edges)}); edges.emplace_back(a, b); }); auto expected = naiveBridges(edges); find(); - vector got(sz(edges)); + vector got(ssize(edges)); for (auto e : bridges) { if (got[e.id]) cerr << "error: duclicate" << FAIL; got[e.id] = true; diff --git a/test/graph/articulationPoints.cpp b/test/graph/articulationPoints.cpp index 2567a09..c06f3a3 100644 --- a/test/graph/articulationPoints.cpp +++ b/test/graph/articulationPoints.cpp @@ -7,10 +7,10 @@ struct edge { #undef Edge vector naiveArt() { - vector res(sz(adj)); + vector res(ssize(adj)); - vector seen(sz(adj), -1); - for (int i = 0; i < sz(adj); i++) { + vector seen(ssize(adj), -1); + for (int i = 0; i < ssize(adj); i++) { if (adj[i].empty()) continue; seen[i] = i; vector todo = {adj[i][0].to}; @@ -72,9 +72,9 @@ void performance_test() { }); t.start(); - find(); + find(); t.stop(); - hash_t hash = sz(bridges) + sz(bcc); + hash_t hash = ssize(bridges) + ssize(bcc); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/bronKerbosch.cpp b/test/graph/bronKerbosch.cpp index 1ccd493..e0cac22 100644 --- a/test/graph/bronKerbosch.cpp +++ b/test/graph/bronKerbosch.cpp @@ -9,7 +9,7 @@ void naive(bits mask = {}, int l = 0) { if (mask[i]) continue; if ((adj[i] & mask) == mask) maximal = false; } - for (; l < sz(adj); l++) { + for (; l < ssize(adj); l++) { if ((adj[l] & mask) == mask) { maximal = false; mask[l] = 1; @@ -37,10 +37,10 @@ void stress_test() { naiveCliques.clear(); naive(); - sort(all(cliques), [](bits a, bits b){return a.to_ullong() < b.to_ullong();}); - sort(all(naiveCliques), [](bits a, bits b){return a.to_ullong() < b.to_ullong();}); + ranges::sort(cliques, {}, [](bits x) { return x.to_ullong(); }); + ranges::sort(naiveCliques, {}, [](bits x) { return x.to_ullong(); }); - if (cliques != naiveCliques) cerr << "got: " << sz(cliques) << ", expected: " << sz(naiveCliques) << FAIL; + if (cliques != naiveCliques) cerr << "got: " << ssize(cliques) << ", expected: " << ssize(naiveCliques) << FAIL; queries += n; } cerr << "tested random queries: " << queries << endl; @@ -62,7 +62,7 @@ void performance_test() { bronKerbosch(); t.stop(); - hash_t hash = sz(cliques); + hash_t hash = ssize(cliques); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/centroid.cpp b/test/graph/centroid.cpp index 41d9d0f..633c3f1 100644 --- a/test/graph/centroid.cpp +++ b/test/graph/centroid.cpp @@ -13,9 +13,9 @@ int subtreeSize(int c, int p) { vector naive() { vector res; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { bool isCentroid = true; - for (int j : adj[i]) isCentroid &= 2*subtreeSize(j, i) <= sz(adj); + for (int j : adj[i]) isCentroid &= 2*subtreeSize(j, i) <= ssize(adj); if (isCentroid) res.push_back(i); } return res; @@ -33,16 +33,16 @@ void stress_test() { adj[a].push_back(b); adj[b].push_back(a); }); - + auto expected = naive(); - sort(all(expected)); + ranges::sort(expected); for (int i = 0; i < n; i++) { auto [a, b] = find_centroid(i); vector got; if (a >= 0) got.push_back(a); if (b >= 0) got.push_back(b); - sort(all(got)); + ranges::sort(got); if (got != expected) cerr << "error" << FAIL; } @@ -63,7 +63,7 @@ void performance_test() { adj[b].push_back(a); }); - t.start(); + t.start(); auto [gotA, gotB] = find_centroid(); t.stop(); hash_t hash = gotA + gotB; diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp index bba8104..96dc4be 100644 --- a/test/graph/connect.cpp +++ b/test/graph/connect.cpp @@ -52,8 +52,8 @@ void stress_test() { int m = Random::integer(30, 300); vector insertOrder(m); - iota(all(insertOrder), 0); - shuffle(all(insertOrder), Random::rng); + iota(begin(insertOrder), end(insertOrder), 0); + ranges::shuffle(insertOrder, Random::rng); vector> edges(m, {-1, -1}); connect con(n, m); @@ -104,15 +104,15 @@ void performance_test() { t.stop(); vector insertOrder(M); - iota(all(insertOrder), 0); - shuffle(all(insertOrder), Random::rng); + iota(begin(insertOrder), end(insertOrder), 0); + ranges::shuffle(insertOrder, Random::rng); vector inserted(M); for (int i = 0, j = 0; i < N; i++) { int a = Random::integer(0, N); int b = a; while (b == a) b = Random::integer(0, N); - + t.start(); con.addEdge(a, b, insertOrder[i]); t.stop(); diff --git a/test/graph/cycleCounting.cpp b/test/graph/cycleCounting.cpp index 8e53aec..9c7bf0c 100644 --- a/test/graph/cycleCounting.cpp +++ b/test/graph/cycleCounting.cpp @@ -4,11 +4,11 @@ int naive(const vector>& edges, int n) { int res = 0; - for (int i = 1; i < (1ll << sz(edges)); i++) { + for (int i = 1; i < (1ll << ssize(edges)); i++) { vector deg(n); init(n); int cycles = 0; - for (int j = 0; j < sz(edges); j++) { + for (int j = 0; j < ssize(edges); j++) { if (((i >> j) & 1) != 0) { auto [a, b] = edges[j]; deg[a]++; @@ -66,7 +66,7 @@ void performance_test() { t.start(); hash_t hash = cyc.count(); - cerr << sz(cyc.base) << endl; + cerr << ssize(cyc.base) << endl; t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; diff --git a/test/graph/euler.cpp b/test/graph/euler.cpp index 6666040..e468e05 100644 --- a/test/graph/euler.cpp +++ b/test/graph/euler.cpp @@ -20,7 +20,7 @@ Euler eulerGraph(int n, int m) { } int last = -1; for (int i = 0; i < n; i++) { - if (sz(res.idx[i]) % 2 != 0) { + if (ssize(res.idx[i]) % 2 != 0) { if (last >= 0) { res.addEdge(last, i); last = -1; @@ -41,25 +41,25 @@ void stress_test() { int m = Random::integer(n-1, 200); auto g = eulerGraph(n, m); - + vector> expected(n); for (int i = 0; i < n; i++) { for (int j : g.idx[i]) { expected[i].push_back(g.to[j]); } - sort(all(expected[i])); + ranges::sort(expected[i]); } g.euler(0); vector> got(n); if (g.cycle.front() != g.cycle.back()) cerr << "error: not cyclic" << FAIL; - for (int i = 1; i < sz(g.cycle); i++) { + for (int i = 1; i < ssize(g.cycle); i++) { int a = g.cycle[i-1]; int b = g.cycle[i]; got[a].push_back(b); got[b].push_back(a); } - for (auto& v : got) sort(all(v)); + for (auto& v : got) ranges::sort(v); if (got != expected) cerr << "error" << FAIL; queries += n; diff --git a/test/graph/floydWarshall.cpp b/test/graph/floydWarshall.cpp index a93a9ea..182b99b 100644 --- a/test/graph/floydWarshall.cpp +++ b/test/graph/floydWarshall.cpp @@ -40,7 +40,7 @@ void stress_test() { if (path.empty()) continue; if (path.front() != i) cerr << "error: start" << FAIL; if (path.back() != k) cerr << "error: end" << FAIL; - for (int l = 1; l < sz(path); l++) { + for (int l = 1; l < ssize(path); l++) { if (floydWarshall::dist[i][path[l-1]] + orig[path[l-1]][path[l]] + floydWarshall::dist[path[l]][k] != @@ -52,7 +52,7 @@ void stress_test() { for (int i = 0; i < n; i++) { auto got = floydWarshall::dist[i]; auto expected = bellmannFord(n, edges, i); - + if (got != expected) cerr << "error" << FAIL; queries += n; } diff --git a/test/graph/havelHakimi.cpp b/test/graph/havelHakimi.cpp index 71476ec..9491db2 100644 --- a/test/graph/havelHakimi.cpp +++ b/test/graph/havelHakimi.cpp @@ -13,11 +13,11 @@ void stress_test() { for (int i = 0; i < n; i++) expected[i] = g.deg(i); auto res = havelHakimi(expected); - if (sz(res) != n) cerr << "error: wrong number of nodes" << FAIL; + if (ssize(res) != n) cerr << "error: wrong number of nodes" << FAIL; vector> rev(n); vector got(n); for (int i = 0; i < n; i++) { - got[i] = sz(res[i]); + got[i] = ssize(res[i]); for (int j : res[i]) { if (j < 0 || j >= n) cerr << "error: invalid edge" << FAIL; rev[j].push_back(i); @@ -25,11 +25,11 @@ void stress_test() { } for (int i = 0; i < n; i++) { - sort(all(res[i])); - sort(all(rev[i])); + ranges::sort(res[i]); + ranges::sort(rev[i]); if (res[i] != rev[i]) cerr << "error: graph is directed" << FAIL; for (int j : res[i]) if (j == i) cerr << "error: graph has loop" << FAIL; - for (int j = 1; j < sz(res[i]); j++) { + for (int j = 1; j < ssize(res[i]); j++) { if (res[i][j] == res[i][j-1]) cerr << "error: multiedge" << FAIL; } } @@ -54,7 +54,7 @@ void performance_test() { auto res = havelHakimi(expected); t.stop(); hash_t hash = 0; - for (auto& v : res) hash += sz(v); + for (auto& v : res) hash += ssize(v); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp index d5043b4..93f946b 100644 --- a/test/graph/reroot.cpp +++ b/test/graph/reroot.cpp @@ -47,7 +47,7 @@ void performance_test() { t.start(); Reroot re; auto ans = re.solve(); - hash = accumulate(all(ans), 0LL); + hash = accumulate(begin(ans), end(ans), 0LL); t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/graph/stoerWagner.cpp b/test/graph/stoerWagner.cpp index 2003f09..e7a1075 100644 --- a/test/graph/stoerWagner.cpp +++ b/test/graph/stoerWagner.cpp @@ -13,7 +13,7 @@ namespace pushRelabel { #include ll minCut() { ll res = INF; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { for (int j = 0; j < i; j++) { if (i == j) continue; res = min(res, maxFlow(i, j)); @@ -48,7 +48,7 @@ void stress_test() { ll got = stoerWagner::stoer_wagner(); ll expected = pushRelabel::minCut(); - + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } diff --git a/test/graph/treeIsomorphism.cpp b/test/graph/treeIsomorphism.cpp index 97f4df4..4daa373 100644 --- a/test/graph/treeIsomorphism.cpp +++ b/test/graph/treeIsomorphism.cpp @@ -45,7 +45,7 @@ void stress_test_eq() { void test_tiny() { vector expected = {1,1,1,1,2,3,6,11,23}; //#A000055 - for (int i = 1; i < sz(expected); i++) { + for (int i = 1; i < ssize(expected); i++) { set> got; tree t(i); @@ -63,9 +63,9 @@ void test_tiny() { got.insert(t.treeLabel()); } - if (sz(got) != expected[i]) cerr << i << ", got: " << sz(got) << ", expected: " << expected[i] << FAIL; + if (ssize(got) != expected[i]) cerr << i << ", got: " << ssize(got) << ", expected: " << expected[i] << FAIL; } - cerr << "tested tiny: " << sz(expected) << endl; + cerr << "tested tiny: " << ssize(expected) << endl; } void stress_test_neq() { @@ -110,7 +110,7 @@ void performance_test() { tt.adj[b].push_back(a); }); - t.start(); + t.start(); auto [gotA, gotB] = tt.treeLabel(); t.stop(); hash_t hash = gotA + gotB; diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp index d256760..0bd71d9 100644 --- a/test/graph/virtualTree.cpp +++ b/test/graph/virtualTree.cpp @@ -21,7 +21,7 @@ int lca(int u, int v) { } void init(vector>& adj) { - int n = (int)sz(adj); + int n = (int)ssize(adj); d.assign(n, 0); in = par = out = d; int counter = 0; @@ -44,7 +44,7 @@ void stress_test() { vector ind = Random::distinct(Random::integer(1, n+1), 0, n); auto [idk, tree] = virtualTree(ind); vector> edges; - for (int i=0; i 1000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/math/berlekampMassey.cpp b/test/math/berlekampMassey.cpp index 58fd143..a9d5709 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(); performance_test(); diff --git a/test/math/bigint.cpp b/test/math/bigint.cpp index 3fc4ac1..538d0dc 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() { } cerr << "tested random queries: " << queries << endl; } - + int main() { stress_test(); } diff --git a/test/math/binomial0.cpp b/test/math/binomial0.cpp index 00c04d4..25ee344 100644 --- a/test/math/binomial0.cpp +++ b/test/math/binomial0.cpp @@ -14,7 +14,7 @@ void stress_test() { ll expected = last[j]; if (got != expected) cerr << "calc_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..f7d06dd 100644 --- a/test/math/binomial1.cpp +++ b/test/math/binomial1.cpp @@ -11,7 +11,7 @@ void stress_test() { ll expected = last[j]; if (got != expected) cerr << "calc_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..0b6178e 100644 --- a/test/math/binomial2.cpp +++ b/test/math/binomial2.cpp @@ -12,7 +12,7 @@ void stress_test() { ll expected = last[j]; if (got != expected) cerr << "calc_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..c4791d0 100644 --- a/test/math/binomial3.cpp +++ b/test/math/binomial3.cpp @@ -15,7 +15,7 @@ void stress_test() { ll expected = last[j]; if (got != expected) cerr << "calc_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/gauss.cpp b/test/math/gauss.cpp index 6e4759d..eb8f641 100644 --- a/test/math/gauss.cpp +++ b/test/math/gauss.cpp @@ -7,10 +7,10 @@ vector> mat; #include vector> inverseMat(const vector>& 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> inverseMat(const vector>& m) { } vector> mul(const vector>& a, const vector>& 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> res(n, vector(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 bd362eb..fc825e4 100644 --- a/test/math/inversions.cpp +++ b/test/math/inversions.cpp @@ -3,7 +3,7 @@ ll naive(const vector& 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 acdc555..7d1b0d7 100644 --- a/test/math/inversionsMerge.cpp +++ b/test/math/inversionsMerge.cpp @@ -3,7 +3,7 @@ ll naive(const vector& 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(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 ): - 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 8115356..1b3e803 100644 --- a/test/math/kthperm.cpp +++ b/test/math/kthperm.cpp @@ -6,13 +6,13 @@ void stress_test() { for (ll i = 0; i < 10'000; i++) { int n = Random::integer(1, 100); vector 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/lgsFp.cpp b/test/math/lgsFp.cpp index 08f8f84..fa2dea3 100644 --- a/test/math/lgsFp.cpp +++ b/test/math/lgsFp.cpp @@ -6,10 +6,10 @@ vector> mat; constexpr ll mod = 1'000'000'007; vector> inverseMat(const vector>& 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; } @@ -26,10 +26,10 @@ vector> inverseMat(const vector>& m) { } vector> mul(const vector>& a, const vector>& 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> res(n, vector(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index 8640980..79607ac 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -11,10 +11,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(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 e03c27e..922d965 100644 --- a/test/math/linearRecurrenceNTT.cpp +++ b/test/math/linearRecurrenceNTT.cpp @@ -12,10 +12,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(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 dab2256..70609f0 100644 --- a/test/math/linearRecurrenceOld.cpp +++ b/test/math/linearRecurrenceOld.cpp @@ -6,10 +6,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(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 8ea822b..527e729 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 (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/math/longestIncreasingSubsequence.cpp b/test/math/longestIncreasingSubsequence.cpp index 407dafe..befee75 100644 --- a/test/math/longestIncreasingSubsequence.cpp +++ b/test/math/longestIncreasingSubsequence.cpp @@ -9,7 +9,7 @@ constexpr ll INF = LL::INF; template bool isLis(const vector& a, const vector& 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& a, const vector& lis) { template vector naive(const vector& a) { vector res; - for (ll i = 1; i < (1ll << sz(a)); i++) { + for (ll i = 1; i < (1ll << ssize(a)); i++) { vector 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(a, tmp)) res = tmp; + if (ssize(tmp) >= ssize(res) && isLis(a, tmp)) res = tmp; } return res; } @@ -56,10 +56,9 @@ void performance_test() { timer t; auto a = Random::integers(N, -10'000, 10'000); auto b = Random::integers(N, -10'000, 10'000); - sort(all(b)); + ranges::sort(b); auto c = Random::integers(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 4dfb0a8..169ff06 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(dim)) { for (int i = 0; i < dim; i++) m[i][i] = diag; } - mat(const vector c) : m(sz(c), vector(sz(c))) { + mat(const vector c) : m(ssize(c), vector(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 operator*(const vector& o) const { - int dim = sz(m); + int dim = ssize(m); vector 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(n, 0, mod)), c(Random::integers(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(0, 1000); vector got = calc(k, tmp); - vector expected(sz(f.f)); + vector 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 742d353..8c2c79a 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 fd98586..725b744 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/permIndex.cpp b/test/math/permIndex.cpp index 6c77d74..d68ba3a 100644 --- a/test/math/permIndex.cpp +++ b/test/math/permIndex.cpp @@ -6,13 +6,13 @@ void stress_test() { for (ll i = 0; i < 10'000; i++) { int n = Random::integer(1, 100); vector 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; @@ -22,7 +22,7 @@ constexpr int N = 500'000; void performance_test() { timer t; vector 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& 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(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(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(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(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(0, ssize(a) - ssize(b))) cerr << "error: wrong degree (div)" << FAIL; for (int i = 0; i <= n + m; i++) { ll x = Random::integer(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 78a50d2..6bb63f6 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(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 (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; 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 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/transforms/fft.cpp b/test/math/transforms/fft.cpp index 858676b..66df1bf 100644 --- a/test/math/transforms/fft.cpp +++ b/test/math/transforms/fft.cpp @@ -2,14 +2,14 @@ #include vector to_cplx(const vector& in) { - vector res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = in[i]; + vector res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = in[i]; return res; } vector from_cplx(const vector& in) { - vector res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + vector 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 5933864..7887a5e 100644 --- a/test/math/transforms/fftMul.cpp +++ b/test/math/transforms/fftMul.cpp @@ -5,21 +5,21 @@ #include vector from_cplx(const vector& in) { - vector res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + vector res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = llround(real(in[i])); return res; } vector naive(const vector& a, const vector& b) { vector 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 bc73290..8b9eb2f 100644 --- a/test/math/transforms/multiplyBitwise.cpp +++ b/test/math/transforms/multiplyBitwise.cpp @@ -6,13 +6,13 @@ vector naive(const vector& a, const vector& b) { vector 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 782be1b..61040d0 100644 --- a/test/math/transforms/multiplyFFT.cpp +++ b/test/math/transforms/multiplyFFT.cpp @@ -6,13 +6,13 @@ vector naive(const vector& a, const vector& b) { vector 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 70fc137..6424c50 100644 --- a/test/math/transforms/multiplyNTT.cpp +++ b/test/math/transforms/multiplyNTT.cpp @@ -6,13 +6,13 @@ vector naive(const vector& a, const vector& b) { vector 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 ee30e00..f78541d 100644 --- a/test/math/transforms/seriesOperations.cpp +++ b/test/math/transforms/seriesOperations.cpp @@ -24,7 +24,7 @@ namespace reference {//checked against yosupo } vector poly_deriv(vector 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 poly_integr(vector 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 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 q2 = q; q2.resize(2*len); ntt(p), ntt(q2); diff --git a/test/other/bitOps.cpp b/test/other/bitOps.cpp index 44f6297..2250521 100644 --- a/test/other/bitOps.cpp +++ b/test/other/bitOps.cpp @@ -31,9 +31,7 @@ ll naive(ll x) { bits.push_back(x & 1); x >>= 1; } - reverse(all(bits)); - next_permutation(all(bits)); - reverse(all(bits)); + ranges::next_permutation(bits | views::reverse); x = 0; for (ll i = 0, j = 1; i < 64; i++, j <<= 1) { if (bits[i] != 0) x |= j; @@ -56,4 +54,4 @@ void test_nextPerm() { int main() { test_subsets(); test_nextPerm(); -} \ No newline at end of file +} diff --git a/test/other/josephus2.cpp b/test/other/josephus2.cpp index 85a9d28..c6b1cd1 100644 --- a/test/other/josephus2.cpp +++ b/test/other/josephus2.cpp @@ -4,8 +4,8 @@ template ll naive(ll n, ll k) { vector state(n); - iota(all(state), O); - for (ll i = k-1; state.size() > 1; i = (i + k - 1) % sz(state)) { + iota(begin(state), end(state), O); + for (ll i = k-1; state.size() > 1; i = (i + k - 1) % ssize(state)) { state.erase(state.begin() + i); } return state[0]; diff --git a/test/other/josephusK.cpp b/test/other/josephusK.cpp index e837640..1a5aa9d 100644 --- a/test/other/josephusK.cpp +++ b/test/other/josephusK.cpp @@ -5,8 +5,8 @@ template ll naive(ll n, ll k) { vector state(n); - iota(all(state), O); - for (ll i = k-1; state.size() > 1; i = (i + k - 1) % sz(state)) { + iota(begin(state), end(state), O); + for (ll i = k-1; state.size() > 1; i = (i + k - 1) % ssize(state)) { state.erase(state.begin() + i); } return state[0]; diff --git a/test/other/pbs.cpp b/test/other/pbs.cpp index ba3b9d0..e1dfea0 100644 --- a/test/other/pbs.cpp +++ b/test/other/pbs.cpp @@ -49,7 +49,7 @@ void stress_test() { for (int i=1; i ans = pbs(Q, MAX_OPERATIONS); t.stop(); - ll hash = accumulate(all(ans), 0LL); + ll hash = accumulate(begin(ans), end(ans), 0LL); if (t.time > 700) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/other/sos.cpp b/test/other/sos.cpp index f3a6109..3ab34ea 100644 --- a/test/other/sos.cpp +++ b/test/other/sos.cpp @@ -6,8 +6,8 @@ vector sos(const vector& in) { } vector naive(const vector& in) { - vector res(sz(in)); - for (ll i = 0; i < sz(in); i++) { + vector res(ssize(in)); + for (ll i = 0; i < ssize(in); i++) { for (ll j = 0; j <= i; j++) { if ((i | j) == i) { res[i] += in[j]; diff --git a/test/string/deBruijn.cpp b/test/string/deBruijn.cpp index 6b3fea4..eb82b59 100644 --- a/test/string/deBruijn.cpp +++ b/test/string/deBruijn.cpp @@ -5,13 +5,13 @@ bool isDeBruijn(string s, int n, int k) { ll expected = 1; for (ll i = 0; i < n; i++) expected *= k; - if (expected != sz(s)) return false; + if (expected != ssize(s)) return false; s += s; set seen; - for (ll i = 0; 2*i < sz(s); i++) { + for (ll i = 0; 2*i < ssize(s); i++) { seen.insert(string_view(s).substr(i, n)); } - return sz(seen) == expected; + return ssize(seen) == expected; } void stress_test() { @@ -21,7 +21,7 @@ void stress_test() { auto [l, r] = Random::pair('b', 'f'); auto got = deBruijn(n, l, r); if (!isDeBruijn(got, n, r - l + 1)) cerr << "error" << FAIL; - queries += sz(got); + queries += ssize(got); } cerr << "tested random queries: " << queries << endl; } @@ -32,7 +32,7 @@ void performance_test() { t.start(); auto res = deBruijn(N, '0', '1'); t.stop(); - hash_t hash = sz(res); + hash_t hash = ssize(res); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/duval.cpp b/test/string/duval.cpp index 58b4a44..5ebc96c 100644 --- a/test/string/duval.cpp +++ b/test/string/duval.cpp @@ -6,8 +6,8 @@ constexpr int N = 20'000'000; bool isLyndon(string_view s) { string t = string(s) + string(s); - for (ll i = 1; i < sz(s); i++) { - if (s >= t.substr(i, sz(s))) return false; + for (ll i = 1; i < ssize(s); i++) { + if (s >= t.substr(i, ssize(s))) return false; } return !s.empty(); } @@ -21,11 +21,11 @@ void stress_test_duval() { if (got.empty()) cerr << "error: a" << FAIL; if (got.front().first != 0) cerr << "error: b" << FAIL; if (got.back().second != n) cerr << "error: c" << FAIL; - for (int j = 1; j < sz(got); j++) { - if (got[j - 1].second != got[j].first) cerr << "error: d" << FAIL; + for (int j = 1; j < ssize(got); j++) { + if (got[j - 1].second != got[j].first) cerr << "error: d" << FAIL; } for (auto [l, r] : got) { - if (!isLyndon(string_view(s).substr(l, r-l))) cerr << "error: e" << FAIL; + if (!isLyndon(string_view(s).substr(l, r-l))) cerr << "error: e" << FAIL; } queries += n; } @@ -45,7 +45,7 @@ void performance_test_duval() { } int naive(string s) { - ll n = sz(s); + ll n = ssize(s); s += s; int res = 0; for (int i = 0; i < n; i++) { diff --git a/test/string/kmp.cpp b/test/string/kmp.cpp index 9c9c924..2364efd 100644 --- a/test/string/kmp.cpp +++ b/test/string/kmp.cpp @@ -2,8 +2,8 @@ #include vector naive(string_view s) { - vector res(sz(s) + 1, -1); - for (int i = 0; i < sz(s); i++) { + vector res(ssize(s) + 1, -1); + for (int i = 0; i < ssize(s); i++) { for (int j = 0; j <= i; j++) if (s.substr(0, j) == s.substr(i-j+1, j)) res[i+1] = j; diff --git a/test/string/longestCommonSubsequence.cpp b/test/string/longestCommonSubsequence.cpp index 6d7a6c5..128c3c1 100644 --- a/test/string/longestCommonSubsequence.cpp +++ b/test/string/longestCommonSubsequence.cpp @@ -4,19 +4,19 @@ bool isSubstr(string_view s, string_view sub) { int i = 0; for (char c : s) { - if (i < sz(sub) && c == sub[i]) i++; + if (i < ssize(sub) && c == sub[i]) i++; } - return i >= sz(sub); + return i >= ssize(sub); } string naive(string_view s, string_view t) { string res = ""; - for (ll i = 1; i < (1ll << sz(s)); i++) { + for (ll i = 1; i < (1ll << ssize(s)); i++) { string tmp; - for (ll j = 0; j < sz(s); j++) { + for (ll j = 0; j < ssize(s); j++) { if (((i >> j) & 1) != 0) tmp.push_back(s[j]); } - if (sz(tmp) >= sz(res) && isSubstr(t, tmp)) res = tmp; + if (ssize(tmp) >= ssize(res) && isSubstr(t, tmp)) res = tmp; } return res; } @@ -44,7 +44,7 @@ void performance_test() { t.start(); auto res = lcss(a, b); t.stop(); - hash_t hash = sz(res); + hash_t hash = ssize(res); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/lyndon.cpp b/test/string/lyndon.cpp index ecf2dad..6710973 100644 --- a/test/string/lyndon.cpp +++ b/test/string/lyndon.cpp @@ -3,8 +3,8 @@ bool isLyndon(string_view s) { string t = string(s) + string(s); - for (ll i = 1; i < sz(s); i++) { - if (s >= t.substr(i, sz(s))) return false; + for (ll i = 1; i < ssize(s); i++) { + if (s >= t.substr(i, ssize(s))) return false; } return !s.empty(); } @@ -12,8 +12,8 @@ bool isLyndon(string_view s) { vector naive(ll n, char mi, char ma) { vector res; auto dfs = [&](auto&& self, string pref)->void{ - if (sz(pref) <= n && isLyndon(pref)) res.push_back(pref); - if (sz(pref) >= n) return; + if (ssize(pref) <= n && isLyndon(pref)) res.push_back(pref); + if (ssize(pref) >= n) return; for (char c = mi; c <= ma; c++) { self(self, pref + c); } @@ -39,7 +39,7 @@ void stress_test() { auto got = fast(n, l, r); auto expected = naive(n, l, r); if (got != expected) cerr << "error" << FAIL; - queries += sz(expected); + queries += ssize(expected); } cerr << "tested random queries: " << queries << endl; } @@ -50,7 +50,7 @@ void performance_test() { t.start(); auto res = fast(N, 'a', 'f'); t.stop(); - hash_t hash = sz(res); + hash_t hash = ssize(res); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/manacher.cpp b/test/string/manacher.cpp index 503d181..803154b 100644 --- a/test/string/manacher.cpp +++ b/test/string/manacher.cpp @@ -2,16 +2,16 @@ #include vector naive(string_view s) { - vector res(2 * sz(s) + 1); - for (int i = 0; i < sz(s); i++) { //odd palindromes + vector res(2 * ssize(s) + 1); + for (int i = 0; i < ssize(s); i++) { //odd palindromes int j = 2*i+1; - while (i+res[j] < sz(s) && i-res[j] >= 0 && s[i-res[j]] == s[i+res[j]]) res[j]++; + while (i+res[j] < ssize(s) && i-res[j] >= 0 && s[i-res[j]] == s[i+res[j]]) res[j]++; res[j]*=2; res[j]--; } - for (int i = 0; i <= sz(s); i++) { //even palindromes + for (int i = 0; i <= ssize(s); i++) { //even palindromes int j = 2*i; - while (i+res[j] < sz(s) && i-res[j]-1 >= 0 && s[i-res[j]-1] == s[i+res[j]]) res[j]++; + while (i+res[j] < ssize(s) && i-res[j]-1 >= 0 && s[i-res[j]-1] == s[i+res[j]]) res[j]++; res[j] *= 2; } return res; diff --git a/test/string/rollingHash.cpp b/test/string/rollingHash.cpp index 0491bc0..a9dace5 100644 --- a/test/string/rollingHash.cpp +++ b/test/string/rollingHash.cpp @@ -3,7 +3,7 @@ string thueMorse(ll n) { string res = "a"; - while (sz(res) < n) { + while (ssize(res) < n) { string tmp = res; for (char& c : tmp) c ^= 1; res += tmp; @@ -12,7 +12,7 @@ string thueMorse(ll n) { } auto getHash(const string& s) { - return Hash(s)(0, sz(s)); + return Hash(s)(0, ssize(s)); } void testThueMorse() { @@ -20,13 +20,13 @@ void testThueMorse() { set expected; string s = thueMorse(1000); Hash h(s); - for (int l = 0; l < sz(s); l++) { - for (int r = l + 1; r <= sz(s); r++) { + for (int l = 0; l < ssize(s); l++) { + for (int r = l + 1; r <= ssize(s); r++) { got.insert(h(l, r)); expected.insert(s.substr(l, r - l)); } } - if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL; + if (ssize(got) != ssize(expected)) cerr << "error: thueMorse" << FAIL; cerr << "thueMorse: ok" << endl; } @@ -43,13 +43,13 @@ void testSmall() { auto dfs = [&](auto&& self, string pref)->void { expected++; got.insert(getHash(pref)); - if(sz(pref) >= 5) return; + if(ssize(pref) >= 5) return; for (char c = 'a'; c <= 'z'; c++) { self(self, pref + c); } }; dfs(dfs, ""); - if (sz(got) != expected) cerr << "error: small" << FAIL; + if (ssize(got) != expected) cerr << "error: small" << FAIL; cerr << "small: ok" << endl; } @@ -58,13 +58,13 @@ void stress_test() { set expected; string s = Random::string(1000, "abc"); Hash h(s); - for (int l = 0; l < sz(s); l++) { - for (int r = l + 1; r <= sz(s); r++) { + for (int l = 0; l < ssize(s); l++) { + for (int r = l + 1; r <= ssize(s); r++) { got.insert(h(l, r)); expected.insert(s.substr(l, r - l)); } } - if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL; + if (ssize(got) != ssize(expected)) cerr << "error: stress test" << FAIL; cerr << "stress test: ok" << endl; } diff --git a/test/string/rollingHashCf.cpp b/test/string/rollingHashCf.cpp index 79003de..f7ce357 100644 --- a/test/string/rollingHashCf.cpp +++ b/test/string/rollingHashCf.cpp @@ -5,7 +5,7 @@ constexpr ll RandomQ = 318LL << 53; string thueMorse(ll n) { string res = "a"; - while (sz(res) < n) { + while (ssize(res) < n) { string tmp = res; for (char& c : tmp) c ^= 1; res += tmp; @@ -14,7 +14,7 @@ string thueMorse(ll n) { } auto getHash(const string& s) { - return Hash(s, RandomQ)(0, sz(s)); + return Hash(s, RandomQ)(0, ssize(s)); } void testThueMorse() { @@ -22,13 +22,13 @@ void testThueMorse() { set expected; string s = thueMorse(1000); Hash h(s, RandomQ); - for (int l = 0; l < sz(s); l++) { - for (int r = l + 1; r <= sz(s); r++) { + for (int l = 0; l < ssize(s); l++) { + for (int r = l + 1; r <= ssize(s); r++) { got.insert(h(l, r)); expected.insert(s.substr(l, r - l)); } } - if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL; + if (ssize(got) != ssize(expected)) cerr << "error: thueMorse" << FAIL; cerr << "thueMorse: ok" << endl; } @@ -45,13 +45,13 @@ void testSmall() { auto dfs = [&](auto&& self, string pref)->void { expected++; got.insert(getHash(pref)); - if(sz(pref) >= 5) return; + if(ssize(pref) >= 5) return; for (char c = 'a'; c <= 'z'; c++) { self(self, pref + c); } }; dfs(dfs, ""); - if (sz(got) != expected) cerr << "error: small" << FAIL; + if (ssize(got) != expected) cerr << "error: small" << FAIL; cerr << "small: ok" << endl; } @@ -60,13 +60,13 @@ void stress_test() { set expected; string s = Random::string(1000, "abc"); Hash h(s, RandomQ); - for (int l = 0; l < sz(s); l++) { - for (int r = l + 1; r <= sz(s); r++) { + for (int l = 0; l < ssize(s); l++) { + for (int r = l + 1; r <= ssize(s); r++) { got.insert(h(l, r)); expected.insert(s.substr(l, r - l)); } } - if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL; + if (ssize(got) != ssize(expected)) cerr << "error: stress test" << FAIL; cerr << "stress test: ok" << endl; } diff --git a/test/string/suffixArray.cpp b/test/string/suffixArray.cpp index 4945d8e..a1db190 100644 --- a/test/string/suffixArray.cpp +++ b/test/string/suffixArray.cpp @@ -2,9 +2,9 @@ #include vector naive(string_view s) { - vector SA(sz(s)); - iota(all(SA), 0); - sort(all(SA), [s](int a, int b){ + vector SA(ssize(s)); + iota(begin(SA), end(SA), 0); + ranges::sort(SA, [s](int a, int b){ return s.substr(a) < s.substr(b); }); return SA; @@ -12,7 +12,7 @@ vector naive(string_view s) { int lcp(string_view s, int x, int y) { int res = 0; - while (x + res < sz(s) && y + res < sz(s) && s[x + res] == s[y + res]) res++; + while (x + res < ssize(s) && y + res < ssize(s) && s[x + res] == s[y + res]) res++; return res; } @@ -50,7 +50,7 @@ void performance_test() { SuffixArray sa(s); t.stop(); hash_t hash = 0; - for (int i = 0; i < sz(sa.SA); i++) hash += i*sa.SA[i]; + for (int i = 0; i < ssize(sa.SA); i++) hash += i*sa.SA[i]; if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/suffixAutomaton.cpp b/test/string/suffixAutomaton.cpp index c2ff511..cab555e 100644 --- a/test/string/suffixAutomaton.cpp +++ b/test/string/suffixAutomaton.cpp @@ -4,10 +4,10 @@ pair naive(string_view s, string_view t) { int pos = 0; int len = 0; - for (int j = 0; j < sz(t); j++) { - for (int i = 0; i < sz(s); i++) { + for (int j = 0; j < ssize(t); j++) { + for (int i = 0; i < ssize(s); i++) { int cur = 0; - while (i+cur < sz(s) && j+cur < sz(t) && s[i+cur] == t[j+cur]) cur++; + while (i+cur < ssize(s) && j+cur < ssize(t) && s[i+cur] == t[j+cur]) cur++; if (cur > len) { pos = j; len = cur; @@ -43,7 +43,7 @@ void performance_test() { SuffixAutomaton sa(s); t.stop(); hash_t hash = 0; - for (ll c = 0; c < sz(s);) { + for (ll c = 0; c < ssize(s);) { int m = Random::integer(1, 1000); s = Random::string(m, "abc"); t.start(); diff --git a/test/string/suffixTree.cpp b/test/string/suffixTree.cpp index c0d79e4..69c24fe 100644 --- a/test/string/suffixTree.cpp +++ b/test/string/suffixTree.cpp @@ -2,8 +2,8 @@ #include vector naive(string_view s) { - vector res(sz(s)); - for (ll i = 0; i < sz(s); i++) { + vector res(ssize(s)); + for (ll i = 0; i < ssize(s); i++) { res[i] = s.substr(i); } return res; @@ -19,7 +19,7 @@ void stress_test() { auto dfs = [&](auto&& self, string pref, ll node) -> void { auto& [l, r, _, next] = st.tree[node]; if (l >= 0) pref += s.substr(l, r - l); - if (pref.back() == '#') got[n + 1 - sz(pref)] = pref; + if (pref.back() == '#') got[n + 1 - ssize(pref)] = pref; for (auto [__, j] : next) { self(self, pref, j); } @@ -39,7 +39,7 @@ void performance_test() { t.start(); SuffixTree st(s); t.stop(); - hash_t hash = sz(st.tree); + hash_t hash = ssize(st.tree); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/string/z.cpp b/test/string/z.cpp index f890a3e..3c76939 100644 --- a/test/string/z.cpp +++ b/test/string/z.cpp @@ -2,9 +2,9 @@ #include vector naive(const string& s) { - vector res(sz(s)); - for (int i = 1; i < sz(s); i++) { - while (i + res[i] < sz(s) && s[res[i]] == s[i + res[i]]) res[i]++; + vector res(ssize(s)); + for (int i = 1; i < ssize(s); i++) { + while (i + res[i] < ssize(s) && s[res[i]] == s[i + res[i]]) res[i]++; } return res; } diff --git a/test/util.h b/test/util.h index e123fc2..0c14ff8 100644 --- a/test/util.h +++ b/test/util.h @@ -1,9 +1,6 @@ #include using namespace std; -#define all(x) std::begin(x), std::end(x) -#define sz(x) (ll)std::size(x) - using ll = long long; using lll = __int128; using ld = long double; @@ -109,7 +106,7 @@ namespace Random { std::string string(std::size_t n, string_view chars) { std::string res(n, '*'); - for (char& c : res) c = chars[integer(sz(chars))]; + for (char& c : res) c = chars[integer(ssize(chars))]; return res; } @@ -281,9 +278,9 @@ public: Graph(int n) : adj(n) {} - int m() const {return sz(edges);} - int n() const {return sz(adj);} - int deg(int x) const {return sz(adj[x]);} + int m() const {return ssize(edges);} + int n() const {return ssize(adj);} + int deg(int x) const {return ssize(adj[x]);} Graph& clear() { adj.assign(adj.size(), {}); @@ -295,33 +292,33 @@ public: if (!LOOPS && from == to) return false; if (!MULTI && adj[from].find(to) != adj[from].end()) return false; edges.emplace_back(from, to, w); - _addAdj(sz(edges) - 1); + _addAdj(ssize(edges) - 1); return true; } Graph& reverse() { for (auto& e : edges) swap(e.from, e.to); adj.assign(adj.size(), {}); - for (int i = 0; i < sz(edges); i++) _addAdj(i); + for (int i = 0; i < ssize(edges); i++) _addAdj(i); return *this; } Graph& shuffle() { - std::shuffle(all(edges), Random::rng); + ranges::shuffle(edges, Random::rng); if constexpr (!DIR) { for (auto& e : edges) { if (Random::integer(0, 2)) swap(e.from, e.to); } } adj.assign(adj.size(), {}); - for (int i = 0; i < sz(edges); i++) _addAdj(i); + for (int i = 0; i < ssize(edges); i++) _addAdj(i); return *this; } Graph& permutate() { vector perm(n()); - iota(all(perm), 0); - std::shuffle(all(perm), Random::rng); + iota(begin(perm), end(perm), 0); + ranges::shuffle(perm, Random::rng); for (auto& e : edges) { e.from = perm[e.from]; e.to = perm[e.to]; @@ -399,7 +396,7 @@ public: } } } - std::shuffle(all(tmp), Random::rng); + ranges::shuffle(tmp, Random::rng); for (auto [a, b] : tmp) { if (todo <= 0) break; if (addEdge(a, b)) todo--; -- cgit v1.2.3