Untitled
unknown
plain_text
3 months ago
24 kB
4
Indexable
{ "Base Template": { "prefix": "cpcpp", "body": [ "// Authored by Gaurav Kabra", "#include <bits/stdc++.h>", "using namespace std;", "#define ll long long", "#define vll vector<long long>", "#define vi vector<int>", "#define vpll vector<pair<long long, long long>>", "#define mll map<long long, long long>", "#define pb push_back", "#define mp make_pair", "#define fi first", "#define se second", "#define yes cout << \"Yes\\n\"", "#define no cout << \"No\\n\"", "#define mod 1000000007", "#define endl \"\\n\"", "#define invll(x, n) \\", " vll x(n); \\", " rep(i, 0, n) cin >> x[i];", "#define invi(x, n) \\", " vi x(n); \\", " rep(i, 0, n) cin >> x[i];", "#define inarrll(x, n) \\", " ll x[n]; \\", " rep(i, 0, n) cin >> x[i];", "#define inarrint(x, n) \\", " int x[n]; \\", " rep(i, 0, n) cin >> x[i];", "#define makegraph(graph, edges) \\", " for (ll i = 0; i < edges; i++) \\", " { \\", " ll a, b; \\", " cin >> a >> b; \\", " graph[a].pb(b); \\", " graph[b].pb(a); \\", " }", "#define inll(...) \\", " ll __VA_ARGS__; \\", " read(__VA_ARGS__);", "#define inint(...) \\", " int __VA_ARGS__; \\", " read(__VA_ARGS__);", "#define debug(arg) cerr << __LINE__ << \" \" << (#arg) << \"-->\" << arg << endl;", "#define clr(n) memset(n, 0, sizeof(n))", "#define all(n) n.begin(), n.end()", "#define lb lower_bound", "#define ub upper_bound", "#define rep(i, k, n) for (ll i = k; i < n; i++)", "#define repit(i, k) for (auto i = k.start(); i != n.end(); i++)", "#define repr(i, k, n) for (ll i = k; i >= n; i--)", "#define repeat(n) for (ll _ = 0; _ < n; _++)", "#define valset(arr, size, val) rep(i, 0, size) arr[i] = val;", "#define setbits(x) __builtin_popcount(x)", "#define setbitsll(x) __builtin_popcountll(x)", "mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());", "#define orz return 0", "template <typename... T>", "void read(T &...args)", "{", " ((cin >> args), ...);", "}", "template <typename... T>", "void print(T... args)", "{", " ((cout << args << \" \"), ...);", " cout << endl;", "}", "", "//---------IO Operator Overloading---------", "template <typename T>", "istream &operator>>(istream &is, vector<T> &v)", "{", " for (ll i = 0; i < v.size(); i++)", " {", " is >> v[i];", " }", " return is;", "}", "template <typename T>", "ostream &operator<<(ostream &os, vector<T> &v)", "{", " for (auto i : v)", " os << i << \" \";", " os << endl;", " return os;", "}", "template <typename T>", "ostream &operator<<(ostream &os, set<T> &s)", "{", " for (auto i : s)", " os << i << \" \";", " os << endl;", " return os;", "}", "template <typename T>", "ostream &operator<<(ostream &os, multiset<T> &s)", "{", " for (auto i : s)", " os << i << \" \";", " os << endl;", " return os;", "}", "//----------------------------------------------------------", "", "#define fast \\", " ios_base::sync_with_stdio(false); \\", " cin.tie(NULL); \\", " cout.tie(NULL);", "", "bool comp(pair<ll, ll> &a, pair<ll, ll> &b)", "{", " return (a.se < b.se);", "}", "", "ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }", "ll binpow(ll a, ll b)", "{", " ll res = 1;", " while (b > 0)", " {", " if (b & 1)", " res = res * a;", " a = a * a;", " b >>= 1;", " }", " return res;", "}", "", "//-------------Solution-------------", "", "void solve()", "{", "}", "", "signed main()", "{", " fast;", "#ifndef ONLINE_JUDGE", " freopen(\"Input.txt\", \"r\", stdin);", " freopen(\"Output.txt\", \"w\", stdout);", " freopen(\"Error.txt\", \"w\", stderr);", "#endif", " inll(n);", " // ll n = 1;", " rep(i, 1, n + 1)", " {", " solve();", " }", "#ifndef ONLINE_JUDGE", " cerr << \"time taken : \" << (float)clock() / CLOCKS_PER_SEC << \" secs\"", " << \"\\n\";", "#endif", " orz;", "}" ], "description": "Base Template" }, "Factorial Filler": { "prefix": "factfill", "body": [ "factorial[0] = 1;", "for (ll i = 1; i < 1000001; i++){factorial[i] = (factorial[i - 1] * i) % mod;}" ], "description": "Factorial Filler" }, "Binary Exponentiation Modulus": { "prefix": "binexpm", "body": [ "ll binexpmod(ll a, ll b, ll m)", "{", " ll res = 1;", " while (b > 0)", " {", " if (b & 1)", " res = (res * a) % m;", " a = (a * a) % m;", " b >>= 1;", " }", " return res;", "}" ], "description": "Binary Exponentiation Modulus" }, "nCr": { "prefix": "ncr", "body": [ "ll ncr(ll n, ll r)", "{", " ll den = factorial[n - r] * factorial[r] % mod;", " return (factorial[n] * binexpmod(den, mod - 2, mod)) % mod;", "}" ], "description": "nCr" }, "Ordered Set Initialiser": { "prefix": "ordset", "body": [ "#include <ext/pb_ds/assoc_container.hpp>", "#include <ext/pb_ds/tree_policy.hpp>", "using namespace __gnu_pbds;", " ", "#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>" ], "description": "Ordered Set Initialiser" }, "Segment Tree": { "prefix": "segtree", "body": [ "#define segtree", "#ifdef segtree", "#define leftindex index * 2 + 1", "#define rightindex index * 2 + 2", "#define mid (start + end) / 2", "#define leftside start, mid, leftindex, seg", "#define rightside mid + 1, end, rightindex, seg", "#endif", " ", "ll mergeseg(ll leftval, ll rightval)", "{", " return leftval + rightval;", "}", " ", "void maketree(ll arr[], ll start, ll end, ll index, ll seg[])", "{", " if (start == end)", " {", " seg[index] = arr[start];", " return;", " }", " maketree(arr, leftside);", " maketree(arr, rightside);", " seg[index] = mergeseg(seg[leftindex], seg[rightindex]);", "}", " ", "void update(ll left, ll right, ll value, ll start, ll end, ll index, ll seg[])", "{", " if (left > end or right < start)", " return;", " else if (left <= start and end <= right)", " {", " if (start == end)", " {", " //? Change this to change update function", " seg[index] = value;", " return;", " }", " //? Update this area to make lazy", " update(left, right, value, leftside);", " update(left, right, value, rightside);", " seg[index] = mergeseg(seg[leftindex], seg[rightindex]);", " }", " else", " {", " if (start == end)", " {", " //? Change this to change update function", " seg[index] = value;", " return;", " }", " update(left, right, value, leftside);", " update(left, right, value, rightside);", " seg[index] = mergeseg(seg[leftindex], seg[rightindex]);", " }", "}", " ", "ll getans(ll left, ll right, ll start, ll end, ll index, ll seg[])", "{", " if (start > right or left > end)", " return 0;", " else if (left <= start and end <= right)", " {", " return seg[index];", " }", " else", " {", " auto a = getans(left, right, leftside);", " auto b = getans(left, right, rightside);", " auto c = a + b;", " return c;", " }", "}" ], "description": "Segment Tree" }, "Sieve": { "prefix": "spf", "body": [ "int spf[100010];", "", "void sieve()", "{", " for (int i = 1; i < 100010; i++)", " {", " spf[i] = i;", " }", " for (int i = 2; i < 100010; i += 2)", " {", " spf[i] = 2;", " }", " for (int i = 3; i * i < 100010; i++)", " {", " if (spf[i] == i)", " {", " for (int j = i * i; j < 100010; j += i)", " {", " if (spf[j] == j)", " spf[j] = i;", " }", " }", " }", "}" ], "description": "Sieve" }, "Parent Marker with times": { "prefix": "dfsparenttime", "body": [ "void dfs(int node, vector<vector<int>> &graph, vector<int> &parent)", "{", " t_in[node] = ++tym;", " for (auto ele : graph[node])", " {", " if (parent[node] != ele)", " {", " parent[ele] = node;", " dfs(ele, graph, parent);", " }", " }", " t_out[node] = ++tym;", "}" ], "description": "Parent Marker with times" }, "Binary Lifting Filler": { "prefix": "binarylift", "body": [ "void binary_lift(int node, vector<int> &parent, vector<vector<int>> &graph)", "{", " par[node][0] = parent[node];", " rep(i, 1, 20)", " {", " if (par[node][i - 1] == -1)", " {", " par[node][i] = -1;", " }", " else", " {", " par[node][i] = par[par[node][i - 1]][i - 1];", " }", " }", " for (auto ele : graph[node])", " {", " if (ele != parent[node])", " {", " binary_lift(ele, parent, graph);", " }", " }", "}" ], "description": "Binary Lifting Filler" }, "Ancestor Boolean": { "prefix": "isancof", "body": [ "bool is_anc_of(int a, int b)", "{", " return (t_in[a] <= t_in[b] and t_out[a] >= t_out[b]);", "}" ], "description": "Ancestor Boolean" }, "Lowest Common Ancestor": { "prefix": "lca", "body": [ "int LCA(int a, int b)", "{", " //! Make the ancestor boolean and par binary lift", " if (is_anc_of(a, b))", " return a;", " repr(i, 19, 0)", " {", " if (par[a][i] != -1 and !is_anc_of(par[a][i], b))", " {", " a = par[a][i];", " }", " }", " return par[a][0];", "}" ], "description": "Lowest Common Ancestor" }, "String Hashing": { "prefix": "stringhash", "body": [ "ll binexpmod(ll a, ll b, ll m)", "{", " ll res = 1;", " while (b > 0)", " {", " if (b & 1)", " res = (res * a) % m;", " a = (a * a) % m;", " b >>= 1;", " }", " return res;", "}", "", "ll basepowers[2][1000010], base = 31;", "int primes[] = {1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097, 1000000103, 1000000123};", "int pr[2];", "", "void initiateHashingTemplate()", "{", " pr[0] = primes[abs(int(rng())) % 9];", " pr[1] = primes[abs(int(rng())) % 9];", " while (pr[0] == pr[1])", " {", " pr[1] = primes[abs(int(rng())) % 9];", " }", " basepowers[0][0] = 1;", " basepowers[1][0] = 1;", " rep(i, 1, 1000010)", " {", " basepowers[0][i] = ((basepowers[0][i - 1] % pr[0]) * base) % pr[0];", " basepowers[1][i] = ((basepowers[1][i - 1] % pr[1]) * base) % pr[1];", " }", " cerr << pr[0] << \" \" << pr[1] << endl;", "}", "", "struct stringHash", "{", " ll length;", " ll hash[2] = {0};", " // string curr;", "", " stringHash()", " {", " if (!pr[0])", " initiateHashingTemplate();", " length = 0;", " }", " stringHash(string s)", " {", " if (!pr[0])", " {", " initiateHashingTemplate();", " }", " length = 0;", " for (auto c : s)", " this->push_back(c);", " }", "", " void mult(ll &a, ll b, ll c)", " {", " a *= b;", " a %= c;", " }", "", " void add(ll &a, ll b, ll c)", " {", " a += (b % c);", " a -= (a >= c) ? c : 0;", " }", "", " void sub(ll &a, ll b, ll c)", " {", " a -= (b % c);", " a += (a < 0) ? c : 0;", " }", "", " void div(ll &a, ll b, ll c)", " {", " a *= binexpmod(b, c - 2, c);", " a %= c;", " }", "", " void push_back(char c)", " {", " this->length++;", " int val = c - 'a' + 1;", " // this->curr.pb(val);", " rep(i, 0, 2)", " {", " mult(hash[i], base, pr[i]);", " add(hash[i], val, pr[i]);", " }", " }", "", " void pop_back(char c)", " {", " this->length--;", " int val = c - 'a' + 1;", " // this->curr.pop_back();", " rep(i, 0, 2)", " {", " sub(hash[i], val, pr[i]);", " div(hash[i], base, pr[i]);", " }", " }", "", " void push_front(char c)", " {", " this->length++;", " int val = c - 'a' + 1;", " // this->curr = c + this->curr;", " rep(i, 0, 2)", " {", " add(hash[i], val * basepowers[i][length - 1], pr[i]);", " }", " }", "", " void pop_front(char c)", " {", " this->length--;", " int val = c - 'a' + 1;", " // this->curr = this->curr.substr(1, length);", " rep(i, 0, 2)", " {", " sub(hash[i], val * basepowers[i][length], pr[i]);", " }", " }", "", " void pop_front(stringHash h)", " {", " int ldiff = this->length - h.length;", " this->length -= h.length;", " // this->curr = this->curr.substr(h.length, length);", " rep(i, 0, 2)", " {", " mult(h.hash[i], basepowers[i][ldiff], pr[i]);", " sub(hash[i], h.hash[i], pr[i]);", " }", " }", "", " bool operator==(stringHash h)", " {", " if (this->length != h.length)", " return false;", " rep(i, 0, 2)", " {", " if (this->hash[i] != h.hash[i])", " {", " return false;", " }", " }", " return true;", " }", "", " stringHash operator+(stringHash h)", " {", " this->length += h.length;", " rep(i, 0, 2)", " {", " mult(hash[i], basepowers[i][h.length], pr[i]);", " add(hash[i], h.hash[i], pr[i]);", " }", " return *this;", " }", "", " stringHash operator-(stringHash h)", " {", " this->length -= h.length;", " rep(i, 0, 2)", " {", " sub(hash[i], h.hash[i], pr[i]);", " div(hash[i], basepowers[i][h.length], pr[i]);", " }", " return *this;", " }", "", " stringHash operator=(stringHash h)", " {", " this->length = h.length;", " rep(i, 0, 2)", " {", " hash[i] = h.hash[i];", " }", " return *this;", " }", "};" ], "description": "String Hashing" }, "Rabin Karp": { "prefix": "rabinkarp", "body": [ "vector<int> rabin_karp(string &s, string &t)", "{", " int a = s.size(), b = t.size();", " vector<int> occurences;", " vector<stringHash> prefixHashes(s.size() + 1);", " prefixHashes[0].pb(s[0]);", " rep(i, 1, a)", " {", " prefixHashes[i] = prefixHashes[i - 1];", " prefixHashes[i].pb(s[i]);", " }", " stringHash two(t);", " if (prefixHashes[b - 1] == two)", " {", " occurences.pb(b - 1);", " }", " rep(i, b, a)", " {", " stringHash temp = prefixHashes[i];", " temp.pop_front(prefixHashes[i - b]);", " if (temp == two)", " {", " occurences.pb(i);", " }", " }", " return occurences;", "}", "", "vector<int> rabin_karp(vector<stringHash> &prefixHashes, string &t)", "{", " int a = prefixHashes.size(), b = t.size();", " vector<int> occurences;", " stringHash two(t);", " if (prefixHashes[b - 1] == two)", " {", " occurences.pb(b - 1);", " }", " rep(i, b, a)", " {", " stringHash temp = prefixHashes[i];", " temp.pop_front(prefixHashes[i - b]);", " if (temp == two)", " {", " occurences.pb(i);", " }", " }", " return occurences;", "}", "bool rabin_karp_bool(vector<stringHash> &prefixHashes, string &t)", "{", " int a = prefixHashes.size(), b = t.size();", " stringHash two(t);", " if (prefixHashes[b - 1] == two)", " {", " return true;", " }", " rep(i, b, a)", " {", " stringHash temp = prefixHashes[i];", " temp.pop_front(prefixHashes[i - b]);", " if (temp == two)", " {", " return true;", " }", " }", " return false;", "}" ], "description": "Rabin Karp" }, "Prefix Function for KMP": { "prefix": "prefkmp", "body": [ "vector<int> prefix_function(string &s)", "{", " int n = s.size();", " vector<int> pref(n);", " rep(i, 1, n)", " {", " int j = pref[i - 1];", " while (j > 0 && s[i] != s[j])", " j = pref[j - 1];", " if (s[i] == s[j])", " j++;", " pref[i] = j;", " }", " return pref;", "}" ], "description": "Prefix Function for KMP" }, "DSU (With Merging)": { "prefix": "dsumerge", "body": [ "", "template <typename T>", "class DSU", "{", " vector<int> root;", " vector<int> sz;", " vector<set<T>> elements;", "", "public:", " DSU(int n)", " {", " root = vector<int>(n + 1);", " sz = vector<int>(n + 1, 1);", " elements = vector<set<int>>(n + 1);", " iota(all(root), 0);", " rep(i, 0, n + 1)", " {", " elements[i].insert(i);", " }", " }", " int find(int x)", " {", " if (root[x] != x)", " root[x] = find(root[x]);", " return root[x];", " }", " void join(int x, int y)", " {", " x = find(x);", " y = find(y);", " if (x == y)", " return;", " if (sz[x] > sz[y])", " {", " swap(x, y);", " }", " root[x] = y;", " sz[y] += sz[x];", " sz[x] = 0;", " for (auto i : elements[x])", " {", " elements[y].insert(i);", " root[i] = y;", " }", " elements[x].clear();", " }", "};" ], "description": "DSU (With Merging)" }, "DSU": { "prefix": "dsu", "body": [ "class DSU", "{", " vector<int> root;", " vector<int> sz;", "", "public:", " DSU(int n)", " {", " root = vector<int>(n + 1);", " sz = vector<int>(n + 1, 1);", " iota(all(root), 0);", " }", " int find(int x)", " {", " if (root[x] != x)", " root[x] = find(root[x]);", " return root[x];", " }", " void join(int x, int y)", " {", " x = find(x);", " y = find(y);", " if(x == y) return;", " if(sz[x] > sz[y]) swap(x, y);", " sz[y] += sz[x];", " sz[x] = 0;", " root[x] = y;", " }", "};" ], "description": "DSU" }, "Dijkstra": { "prefix": "Dijkstra", "body": [ "priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;", " pq.push({0, src});", " vll distances(k + 1, INT_MAX);", " vll locked(k + 1);", " while (!pq.empty())", " {", " auto ele = pq.top();", " pq.pop();", " if (locked[ele.se])", " continue;", " locked[ele.se] = 1;", " distances[ele.se] = ele.fi;", " for (auto neighbour : graph[ele.se])", " {", " if (distances[neighbour.fi] > distances[ele.se] + neighbour.se)", " {", " pq.push({distances[ele.se] + neighbour.se, neighbour.fi});", " }", " }", " }" ], "description": "Dijkstra" }, "Mod Integer Struct": { "prefix": "modint", "body": [ "template <int MOD>", "struct mint", "{", " int value;", " mint() : value() {}", " mint(ll value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD", " : value_) {}", " mint(int value_, nullptr_t) : value(value_) {}", " explicit operator bool() const { return value; }", " inline mint<MOD> operator+(mint<MOD> other) const { return mint<MOD>(*this) += other; }", " inline mint<MOD> operator-(mint<MOD> other) const { return mint<MOD>(*this) -= other; }", " inline mint<MOD> operator*(mint<MOD> other) const { return mint<MOD>(*this) *= other; }", " inline mint<MOD> &operator+=(mint<MOD> other)", " {", " this->value = this->value + other.value;", " if (this->value >= MOD)", " this->value -= MOD;", " return *this;", " }", " inline mint<MOD> &operator-=(mint<MOD> other)", " {", " this->value = this->value - other.value;", " if (this->value < 0)", " this->value += MOD;", " return *this;", " }", " inline mint<MOD> &operator*=(mint<MOD> other)", " {", " this->value = ((ll)this->value * other.value) % MOD;", " return *this;", " }", " inline mint<MOD> operator-() const", " {", " return mint<MOD>(this->value ? MOD - this->value : 0, nullptr);", " }", " inline bool operator==(mint<MOD> other) const { return value == other.value; }", " inline bool operator!=(mint<MOD> other) const { return value != other.value; }", "", " inline mint<MOD> pow(ll x, ll k)", " {", " ll y = 1;", " for (; k; k >>= 1)", " {", " if (k & 1)", " (y *= x) %= MOD;", " (x *= x) %= MOD;", " }", " return mint<MOD>(y);", " }", " inline mint<MOD> inv()", " {", " return pow((ll)this->value, MOD - 2);", " }", " inline mint<MOD> operator/(mint<MOD> other) const { return *this * other.inv(); }", " inline mint<MOD> &operator/=(mint<MOD> other) { return *this *= other.inv(); }", "};", "template <int MOD>", "mint<MOD> operator+(ll value, mint<MOD> n) { return mint<MOD>(value) + n; }", "template <int MOD>", "mint<MOD> operator-(ll value, mint<MOD> n) { return mint<MOD>(value) - n; }", "template <int MOD>", "mint<MOD> operator*(ll value, mint<MOD> n) { return mint<MOD>(value) * n; }", "template <int MOD>", "mint<MOD> operator/(ll value, mint<MOD> n) { return mint<MOD>(value) / n; }", "template <int MOD>", "mint<MOD> operator+(int value, mint<MOD> n) { return mint<MOD>(value) + n; }", "template <int MOD>", "mint<MOD> operator-(int value, mint<MOD> n) { return mint<MOD>(value) - n; }", "template <int MOD>", "mint<MOD> operator*(int value, mint<MOD> n) { return mint<MOD>(value) * n; }", "template <int MOD>", "mint<MOD> operator/(int value, mint<MOD> n)", "{", " print(value);", " return mint<MOD>(value) / n;", "}", "", "template <int MOD>", "std::istream &operator>>(std::istream &in, mint<MOD> &n)", "{", " inll(value);", " n = value;", " return in;", "}", "template <int MOD>", "std::ostream &operator<<(std::ostream &out, mint<MOD> n) { return out << n.value; }", "" ], "description": "Mod Integer Struct" } }
Editor is loading...
Leave a Comment