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