From 61cac9c0febbb5440b99e22770d917bf3a63c405 Mon Sep 17 00:00:00 2001 From: MZuenni Date: Wed, 11 Jan 2023 11:15:50 +0100 Subject: dont use .size() --- datastructures/RMQ.cpp | 10 +++--- datastructures/lazyPropagation1.cpp | 2 +- geometry/antipodalPoints.cpp | 2 +- geometry/closestPair.cpp | 2 +- graph/LCA.cpp | 6 ++-- graph/capacityScaling.cpp | 6 ++-- graph/pushRelabel2.cpp | 6 ++-- math/bigint.cpp | 62 +++++++++++++++++------------------ math/inversions.cpp | 2 +- math/inversionsMerge.cpp | 14 ++++---- math/longestIncreasingSubsequence.cpp | 2 +- math/transforms/fftMul.cpp | 8 ++--- string/kmp.cpp | 8 ++--- string/longestCommonSubsequence.cpp | 8 ++--- string/suffixAutomaton.cpp | 9 +++-- string/suffixTree.cpp | 3 +- string/trie.cpp | 2 +- template/template.cpp | 4 +-- 18 files changed, 77 insertions(+), 79 deletions(-) diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp index b38b838..8e5cc3f 100644 --- a/datastructures/RMQ.cpp +++ b/datastructures/RMQ.cpp @@ -6,22 +6,22 @@ int select(int a, int b) { } void build() { - for(int i = 0, s = 1, ss = 1; s <= values.size(); ss=s, s*=2, i++) { - for(int l = 0; l + s <= values.size(); l++) { + for(int i = 0, s = 1, ss = 1; s <= sz(values); ss=s, s*=2, i++) { + for(int l = 0; l + s <= sz(values); l++) { if(i == 0) rmq[0][l] = l; else { int r = l + ss; rmq[i][l] = select(rmq[i-1][l], rmq[i-1][r]]); }}}} -void init(vector& v) { +void init(const vector& v) { values = v; - rmq = vector>(floor(log2(values.size()))+1, vector(values.size())); + rmq = vector>(__lg(sz(values))+1, vector(sz(values))); build(); } int query(int l, int r) { if(l >= r) return l; - int s = floor(log2(r-l)); r = r - (1 << s); + int s = __lg(r-l); r = r - (1 << s); return select(rmq[s][l],rmq[s][r]); } \ No newline at end of file diff --git a/datastructures/lazyPropagation1.cpp b/datastructures/lazyPropagation1.cpp index 9fdffb1..5f0049f 100644 --- a/datastructures/lazyPropagation1.cpp +++ b/datastructures/lazyPropagation1.cpp @@ -5,7 +5,7 @@ vector d(N, updateFlag); void apply(int p, ll value) { tree[p] += value; - if (p < tree.size()/2) d[p] += value; + if (p < sz(tree)/2) d[p] += value; } void build(int p) { diff --git a/geometry/antipodalPoints.cpp b/geometry/antipodalPoints.cpp index 707cf84..06efd6c 100644 --- a/geometry/antipodalPoints.cpp +++ b/geometry/antipodalPoints.cpp @@ -1,6 +1,6 @@ vector> antipodalPoints(vector& h) { vector> result; - int n = (int)h.size(); + int n = sz(h); if (n < 2) return result; for (int i = 0, j = 1; i < j; i++) { while (true) { diff --git a/geometry/closestPair.cpp b/geometry/closestPair.cpp index 552eb0c..0cad353 100644 --- a/geometry/closestPair.cpp +++ b/geometry/closestPair.cpp @@ -12,7 +12,7 @@ bool compX(pt a, pt b) { : real(a) < real(b); } -double shortestDist(vector& pts) { // pts.size() > 1 +double shortestDist(vector& pts) { // sz(pts) > 1 set status(compY); sort(all(pts), compX); double opt = 1.0/0.0, sqrtOpt = 1.0/0.0; diff --git a/graph/LCA.cpp b/graph/LCA.cpp index bdb8f12..027d101 100644 --- a/graph/LCA.cpp +++ b/graph/LCA.cpp @@ -16,9 +16,9 @@ int getLCA(int a, int b) { void exampleUse() { int c = 0; - visited = vector(2*adjlist.size()); - first = vector(adjlist.size(), 2*adjlist.size()); - depth = vector(2*adjlist.size()); + visited = vector(2*sz(adjlist)); + first = vector(sz(adjlist), 2*sz(adjlist)); + depth = vector(2*sz(adjlist)); initLCA(0, 0, c); init(depth); } diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp index b59c322..8467f81 100644 --- a/graph/capacityScaling.cpp +++ b/graph/capacityScaling.cpp @@ -10,9 +10,9 @@ vector visited; ll capacity; void addEdge(int from, int to, ll c) { - adjlist[from].push_back(edges.size()); + adjlist[from].push_back(sz(edges)); edges.push_back({from, to, 0, c}); - adjlist[to].push_back(edges.size()); + adjlist[to].push_back(sz(edges)); edges.push_back({to, from, 0, 0}); } @@ -34,7 +34,7 @@ ll maxFlow(int source, int target) { s = source; t = target; ll flow = 0; - visited.assign(adjlist.size(), 0); + visited.assign(sz(adjlist), 0); dfsCounter = 0; while (capacity) { while (dfsCounter++, dfs(s)) flow += capacity; diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp index 8b5f0c6..343f71d 100644 --- a/graph/pushRelabel2.cpp +++ b/graph/pushRelabel2.cpp @@ -14,9 +14,9 @@ vector::iterator> iter; int highest, highestActive; void addEdge(int from, int to, ll c) { - adjlist[from].push_back(edges.size()); + adjlist[from].push_back(sz(edges)); edges.push_back({from, to, 0, c}); - adjlist[to].push_back(edges.size()); + adjlist[to].push_back(sz(edges)); edges.push_back({to, from, 0, 0}); } @@ -79,7 +79,7 @@ void discharge(int n, int u) { }} ll maxFlow(int s, int t) { - int n = adjlist.size(); + int n = sz(adjlist); llist.assign(n + 1, {}); dlist.assign(n + 1, {}); highestActive = highest = 0; diff --git a/math/bigint.cpp b/math/bigint.cpp index f8e3507..59d6afe 100644 --- a/math/bigint.cpp +++ b/math/bigint.cpp @@ -26,10 +26,10 @@ struct bigint { bigint operator+(const bigint& v) const { if (sign == v.sign) { bigint res = v; - for (ll i = 0, carry = 0; i < (ll)max(a.size(), v.a.size()) || carry; ++i) { - if (i == (ll)res.a.size()) + for (ll i = 0, carry = 0; i < max(sz(a), sz(v.a)) || carry; ++i) { + if (i == sz(res.a)) res.a.push_back(0); - res.a[i] += carry + (i < (ll)a.size() ? a[i] : 0); + res.a[i] += carry + (i < sz(a) ? a[i] : 0); carry = res.a[i] >= base; if (carry) res.a[i] -= base; @@ -43,8 +43,8 @@ struct bigint { if (sign == v.sign) { if (abs() >= v.abs()) { bigint res = *this; - for (ll i = 0, carry = 0; i < (ll)v.a.size() || carry; ++i) { - res.a[i] -= carry + (i < (ll)v.a.size() ? v.a[i] : 0); + for (ll i = 0, carry = 0; i < sz(v.a) || carry; ++i) { + res.a[i] -= carry + (i < sz(v.a) ? v.a[i] : 0); carry = res.a[i] < 0; if (carry) res.a[i] += base; } @@ -58,8 +58,8 @@ struct bigint { void operator*=(ll v) { if (v < 0) sign = -sign, v = -v; - for (ll i = 0, carry = 0; i < (ll)a.size() || carry; ++i) { - if (i == (ll)a.size()) a.push_back(0); + for (ll i = 0, carry = 0; i < sz(a) || carry; ++i) { + if (i == sz(a)) a.push_back(0); ll cur = a[i] * v + carry; carry = cur / base; a[i] = cur % base; @@ -78,12 +78,12 @@ struct bigint { bigint a = a1.abs() * norm; bigint b = b1.abs() * norm; bigint q, r; - q.a.resize(a.a.size()); - for (ll i = (ll)a.a.size() - 1; i >= 0; i--) { + q.a.resize(sz(a.a)); + for (ll i = sz(a.a) - 1; i >= 0; i--) { r *= base; r += a.a[i]; - ll s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()]; - ll s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1]; + 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 d = (base * s1 + s2) / b.a.back(); r -= b * d; while (r < 0) r += b, --d; @@ -106,7 +106,7 @@ struct bigint { void operator/=(ll v) { if (v < 0) sign = -sign, v = -v; - for (ll i = (ll)a.size() - 1, rem = 0; i >= 0; --i) { + for (ll i = sz(a) - 1, rem = 0; i >= 0; --i) { ll cur = a[i] + rem * base; a[i] = cur / v; rem = cur % v; @@ -123,7 +123,7 @@ struct bigint { ll operator%(ll v) const { if (v < 0) v = -v; ll m = 0; - for (ll i = (ll)a.size() - 1; i >= 0; --i) + for (ll i = sz(a) - 1; i >= 0; --i) m = (a[i] + m * base) % v; return m * sign; } @@ -143,9 +143,9 @@ struct bigint { bool operator<(const bigint& v) const { if (sign != v.sign) return sign < v.sign; - if (a.size() != v.a.size()) - return a.size() * sign < v.a.size() * v.sign; - for (ll i = (ll)a.size() - 1; i >= 0; i--) + 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 (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign; return false; @@ -173,7 +173,7 @@ struct bigint { } bool isZero() const { - return a.empty() || (a.size() == 1 && a[0] == 0); + return a.empty() || (sz(a) == 1 && a[0] == 0); } bigint operator-() const { @@ -190,7 +190,7 @@ struct bigint { ll longValue() const { ll res = 0; - for (ll i = (ll)a.size() - 1; i >= 0; i--) + for (ll i = sz(a) - 1; i >= 0; i--) res = res * base + a[i]; return res * sign; } @@ -199,11 +199,11 @@ struct bigint { sign = 1; a.clear(); ll pos = 0; - while (pos < (ll)s.size() && (s[pos] == '-' || s[pos] == '+')) { + while (pos < sz(s) && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } - for (ll i = (ll)s.size() - 1; i >= pos; i -= base_digits) { + for (ll i = sz(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'; @@ -222,13 +222,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 = (ll)v.a.size() - 2; i >= 0; --i) + for (ll i = sz(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 = a.size(); + ll n = sz(a); vll res(n + n); if (n <= 32) { for (ll i = 0; i < n; i++) @@ -246,25 +246,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 < (ll)a1b1.size(); i++) r[i] -= a1b1[i]; - for (ll i = 0; i < (ll)a2b2.size(); i++) r[i] -= a2b2[i]; - for (ll i = 0; i < (ll)r.size(); i++) res[i + k] += r[i]; - for (ll i = 0; i < (ll)a1b1.size(); i++) res[i] += a1b1[i]; - for (ll i = 0; i < (ll)a2b2.size(); i++) res[i + n] += a2b2[i]; + 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]; return res; } bigint operator*(const bigint& v) const { vll a(this->a.begin(), this->a.end()); vll b(v.a.begin(), v.a.end()); - while (a.size() < b.size()) a.push_back(0); - while (b.size() < a.size()) b.push_back(0); - while (a.size() & (a.size() - 1)) + while (sz(a) < sz(b)) a.push_back(0); + while (sz(b) < sz(a)) b.push_back(0); + while (sz(a) & (sz(a) - 1)) a.push_back(0), b.push_back(0); vll c = karatsubaMultiply(a, b); bigint res; res.sign = sign * v.sign; - for (ll i = 0, carry = 0; i < (ll)c.size(); i++) { + for (ll i = 0, carry = 0; i < sz(c); i++) { ll cur = c[i] + carry; res.a.push_back(cur % base); carry = cur / base; diff --git a/math/inversions.cpp b/math/inversions.cpp index 02256ca..051408c 100644 --- a/math/inversions.cpp +++ b/math/inversions.cpp @@ -1,7 +1,7 @@ ll inversions(const vector& v) { Tree> t; //ordered statistics tree ll res = 0; - for (ll i = 0; i < (ll)v.size(); i++) { + for (ll i = 0; i < sz(v); i++) { res += i - t.order_of_key({v[i], i}); t.insert({v[i], i}); } diff --git a/math/inversionsMerge.cpp b/math/inversionsMerge.cpp index 1ea2ada..8235b11 100644 --- a/math/inversionsMerge.cpp +++ b/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 < (int)left.size() && b < (int)right.size()) { + while (a < sz(left) && b < sz(right)) { if (left[a] < right[b]) v[i++] = left[a++]; else { - inv += left.size() - a; + inv += sz(left) - a; v[i++] = right[b++]; } } - while (a < (int)left.size()) v[i++] = left[a++]; - while (b < (int)right.size()) v[i++] = right[b++]; + while (a < sz(left)) v[i++] = left[a++]; + while (b < sz(right)) v[i++] = right[b++]; return inv; } ll mergeSort(vector &v) { // Sortiert v und gibt Inversionszahl zurück. - int n = v.size(); + int n = sz(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 (left.size() > 1) result += mergeSort(left); - if (right.size() > 1) result += mergeSort(right); + if (sz(left) > 1) result += mergeSort(left); + if (sz(right) > 1) result += mergeSort(right); return result + merge(v, left, right); } diff --git a/math/longestIncreasingSubsequence.cpp b/math/longestIncreasingSubsequence.cpp index a4a8211..c2c5f3e 100644 --- a/math/longestIncreasingSubsequence.cpp +++ b/math/longestIncreasingSubsequence.cpp @@ -1,5 +1,5 @@ vector lis(vector &seq) { - int n = seq.size(), lisLength = 0, lisEnd = 0; + int n = sz(seq), lisLength = 0, lisEnd = 0; vector L(n), L_id(n), parents(n); for (int i = 0; i < n; i++) { int pos = upper_bound(L.begin(), L.begin() + lisLength, diff --git a/math/transforms/fftMul.cpp b/math/transforms/fftMul.cpp index dc19412..c8de19a 100644 --- a/math/transforms/fftMul.cpp +++ b/math/transforms/fftMul.cpp @@ -1,11 +1,11 @@ vector mul(vector& a, vector& b) { - vector c(a.size()), d(a.size()); - for (int i = 0; i < b.size(); i++) { + vector c(sz(a)), d(sz(a)); + for (int i = 0; i < sz(b); i++) { c[i] = {real(a[i]), real(b[i])}; } c = fft(c); - for (int i = 0; i < b.size(); i++) { - int j = (a.size() - i) % a.size(); + for (int i = 0; i < sz(b); i++) { + int j = (sz(a) - i) % sz(a); cplx x = (c[i] + conj(c[j])) / cplx{2, 0}; //fft(a)[i]; cplx y = (c[i] - conj(c[j])) / cplx{0, 2}; //fft(b)[i]; d[i] = x * y; diff --git a/string/kmp.cpp b/string/kmp.cpp index 282019e..12ae3eb 100644 --- a/string/kmp.cpp +++ b/string/kmp.cpp @@ -1,8 +1,8 @@ vector kmpPreprocessing(const string& sub) { - vector b(sub.size() + 1); + vector b(sz(sub) + 1); b[0] = -1; int i = 0, j = -1; - while (i < (int)sub.size()) { + while (i < sz(sub)) { while (j >= 0 && sub[i] != sub[j]) j = b[j]; i++; j++; b[i] = j; @@ -12,10 +12,10 @@ vector kmpPreprocessing(const string& sub) { vector kmpSearch(const string& s, const string& sub) { vector pre = kmpPreprocessing(sub), result; int i = 0, j = 0; - while (i < (int)s.size()) { + while (i < sz(s)) { while (j >= 0 && s[i] != sub[j]) j = pre[j]; i++; j++; - if (j == (int)sub.size()) { + if (j == sz(sub)) { result.push_back(i - j); j = pre[j]; }} diff --git a/string/longestCommonSubsequence.cpp b/string/longestCommonSubsequence.cpp index dd2368e..fa1adb6 100644 --- a/string/longestCommonSubsequence.cpp +++ b/string/longestCommonSubsequence.cpp @@ -1,12 +1,12 @@ string lcss(string& a, string& b) { - vector> m(a.size() + 1, vector(b.size() + 1)); - for(int y = a.size() - 1; y >= 0; y--) { - for(int x = b.size() - 1; x >= 0; x--) { + vector> m(sz(a) + 1, vector(sz(b) + 1)); + for(int y = sz(a) - 1; y >= 0; y--) { + for(int x = sz(b) - 1; x >= 0; x--) { if(a[y] == b[x]) m[y][x] = 1 + m[y+1][x+1]; else m[y][x] = max(m[y+1][x], m[y][x+1]); }} // Für die Länge: return m[0][0]; string res; int x=0; int y=0; - while(x < b.size() && y < a.size()) { + while(x < sz(b) && y < sz(a)) { if(a[y] == b[x]) res += a[y++], x++; else if(m[y][x+1] > m[y+1][x+1]) x++; else y++; diff --git a/string/suffixAutomaton.cpp b/string/suffixAutomaton.cpp index 15265c8..69aa979 100644 --- a/string/suffixAutomaton.cpp +++ b/string/suffixAutomaton.cpp @@ -1,5 +1,5 @@ constexpr char MIN_CHAR = 'a'; -constexpr long long ALPHABET_SIZE = 26; +constexpr ll ALPHABET_SIZE = 26; struct SuffixAutomaton { struct State { int length, link; @@ -9,8 +9,7 @@ struct SuffixAutomaton { vector states; int size, last; - SuffixAutomaton(string &s) { - states.resize(2 * sz(s)); + SuffixAutomaton(const string &s) : states(2*sz(s)) { size = 1; last = 0; states[0].length = 0; states[0].link = -1; @@ -46,9 +45,9 @@ struct SuffixAutomaton { // Pair with start index and length of LCS. // Index in parameter t. - pair longestCommonSubstring(string &t) { + pair longestCommonSubstring(const string &t) { int v = 0, l = 0, best = 0, bestpos = 0; - for (int i = 0; i < (int)t.size(); i++) { + for (int i = 0; i < sz(t); i++) { int c = t[i] - MIN_CHAR; while (v && !states[v].next[c]) { v = states[v].link; diff --git a/string/suffixTree.cpp b/string/suffixTree.cpp index 7af3ee6..2601c34 100644 --- a/string/suffixTree.cpp +++ b/string/suffixTree.cpp @@ -53,7 +53,6 @@ struct SuffixTree { if (!tree[curVert].next.count(s[curEdge])) { int leaf = newVert(pos, sz(s)); tree[curVert].next[s[curEdge]] = leaf; - tree[curVert].next[s[curEdge]] = leaf; addSuffixLink(curVert); } else { int nxt = tree[curVert].next[s[curEdge]]; @@ -77,7 +76,7 @@ struct SuffixTree { curLen--; curEdge = pos - remainder + 1; } else { - curVert = tree[curVert].suffix ? tree[curVert].suffix + curVert = tree[curVert].suffix ? tree[curVert].suffix : root; }}} }; \ No newline at end of file diff --git a/string/trie.cpp b/string/trie.cpp index f112e1e..0544a9f 100644 --- a/string/trie.cpp +++ b/string/trie.cpp @@ -11,7 +11,7 @@ int insert(vector& word) { for (int c : word) { trie[id].words++; if (trie[id].children[c] < 0) { - trie[id].children[c] = trie.size(); + trie[id].children[c] = sz(trie); trie.emplace_back(); } id = trie[id].children[c]; diff --git a/template/template.cpp b/template/template.cpp index 48c2b99..79cb6dd 100644 --- a/template/template.cpp +++ b/template/template.cpp @@ -3,8 +3,8 @@ using namespace std; #define fora(i, n) for (int i = 0; i < n; ++i) #define forb(i, n) for (int i = 1; i <= n; ++i) -#define sz(x) ((int)(x).size()) -#define all(x) (x).begin(), (x).end() +#define all(x) begin(x), end(x) +#define sz(x) (ll)size(x) #define _ << " " << #define debug(x) #x << " = " << (x) -- cgit v1.2.3