13. Code Template C++

Cpp code template

/*
  Author : Shaurya Singhal(jugshaurya)
*/

// #code
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int                          long long
#define setbits(x)                  __builtin_popcountll(x)
#define zrobits(x)                  __builtin_ctzll(x)
#define inf                         1e18
#define ps(x,y)                     fixed<<setprecision(y)<<x
#define mk(arr,n,type)              type *arr=new type[n];
#define endl                        "\n"
#define IOS                         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(_x)                     _x.begin(), _x.end()
#define sz(_x)                      int(_x.size())
mt19937                             rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// [fbo][ook]
// iterator find_by_order(int i) => return `iterator` to ith-index value.
// int order_by_key(int key) => return `index` of element >= key

const int MOD = 1e9 + 7;
const int INF = LLONG_MAX >> 1;

// Binary Exponentitation
int binpow(int a,int b){int res=1;while(b){if(b&1)res*=a;a*=a;b>>=1;}return res;}

// Binary Exponentitation with mod
int binpowMod(int a,int b,int m){int res=1;a%=m;while(b){if(b&1)res=res*a%m;a=a*a%m;b>>=1;}return res;}

inline void fastIO(){
    IOS
    // for CPH: Check ONLINE_JUDGE checkbox
    //  #ifndef ONLINE_JUDGE
    //      freopen("input.txt", "r", stdin);
    //      freopen("output.txt", "w", stdout);
    //  #endif
}

// clang-format on

// #debug
#ifndef ONLINE_JUDGE
#define debarr(a,n) cerr<<#a<<" : ";for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
#define debmat(mat,row,col) cerr<<#mat<<" :\n";for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const unordered_set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const unordered_map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
#else
#define pr(...) {}
#define debarr(a,n) {}
#define debmat(mat,row,col) {}
#endif

// int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; string dir = "DRUL";
// int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}; int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};

/*
- Templates TODOs
  5. Debugging template for random input and brute force solution
  3. For  loops (1D and 2D)
  2. Segment tree code into template
  8. Trie code in template
  9. Union find code snippet/template
  10. Dijikstra code
  10. Bellman ford code
  10. Floyd warshall code
  11. Add time per cock second in cerr file and break code exectuion
      cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
  12. add sieve code
  13. add gcd code
      int gcd(int a, int b) {
        if(b==0) return a;
        return gcd(b,a%b);
      }

      int gcd(int a, int b) {
        while(b!=0){
          int temp = a;
          a = b;
          b = temp%b;
        }
        return a;
      }
  15. Add string split(string, delimiter) code using stringstream
  16. Create trie template - both BIT trie and string trie

 */

// Matrix Multiplication
struct Mat {
  vector<vector<int>> mat;
  int n;  // matrix (n x n)

  // make a zero sqaure-matrix of size nxn.
  Mat(int n) : n(n) {
    mat = vector<vector<int>>(n, vector<int>(n, 0));
  }

  // make a sqaure-matrix of size nxn same as A.
  Mat(vector<vector<int>> A) {
    n = A.size();
    mat = A;
  }

  // make matrix an identity matrix
  void identity() {
    for (int i = 0; i < n; i++) {
      mat[i][i] = 1;
    }
  }

  // Multiply square Matrices.
  Mat operator*(Mat A) {
    Mat res(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          res.mat[i][j] += mat[i][k] * A.mat[k][j];
          res.mat[i][j] %= MOD;
        }
      }
    }
    return res;
  }

  void print() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        cout << mat[i][j] << " ";
      }
      cout << endl;
    }
  }
};

// DSU
vector<int> parent;
vector<int> ranks;

int findSet(int v){
  if(parent[v]==-1) return v;
  return parent[v] = findSet(parent[v]);
}

void unionSet(int v1, int v2){
  int s1 = findSet(v1);
  int s2 = findSet(v2);
  if(s1!=s2){
    if(ranks[s1] > ranks[s2]){
      parent[s2] = s1;
      ranks[s1] += ranks[s2];
    }else{
      parent[s1] = s2;
      ranks[s2] += ranks[s1];
    }
  }
}

void initDSU(int n){
  parent.clear();
  ranks.clear();
  parent.assign(n,-1);
  ranks.assign(n,1);
}

// call it like
// void call(){
//   initDSU(/*number of vertices*/);
// }

void pre() {}

void solve() {
}

// clang-format off
signed main() {
  IOS
  // for CPH: Check ONLINE_JUDGE checkbox
  //    #ifndef ONLINE_JUDGE
  //        freopen("input.txt", "r", stdin);
  //        freopen("output.txt", "w", stdout);
  //    #endif

  pre();
  int i = 1;
  // int _t; cin>>_t; for(;i<=_t;i++)
  solve(i);
  return 0;
}
Cpp code template​

Cpp code template
