API tools faq
paste
newb_ie

Library

newb_ie
Dec 10th, 2020 (edited)
186
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 20.05 KB | None | 0 0
raw download clone embed print report
  1. == == == == == =
  2.     [TEMPLATES]
  3.  == == == == == =
  4. Direction array :
  5. int dx[8] = {1, 0, -1, 0, -1, -1, 1, 1};
  6. int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
  7. //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  8. #define filein freopen ("in.txt", "r", stdin)
  9. #define fileout freopen ("out.txt", "w", stdout)
  10. == == ==
  11. [PBDS]
  12. == == ==
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. using namespace __gnu_pbds;
  16. typedef tree<int64_t, null_type, less_equal<int64_t>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  17.  
  18. freopen ("input.txt", "r", stdin);
  19. freopen ("output.txt", "w", stdout);
  20. template<typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
  21. template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
  22. template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
  23. template<typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
  24. template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
  25. template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
  26. template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
  27. template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << ", " << pa.second << ")"; return os; }
  28. template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
  29. template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
  30. template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
  31. template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
  32. template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
  33. template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }
  34. template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
  35. template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
  36. == == == == == == == == == == == =
  37.     [ BITWISE FUNCTIONS   ]
  38.     == == == == == == == == == == == =
  39.  
  40. int set_bit(int n, int pos) {return n = (n | (1 << pos));}
  41. int reset_bit(int n, int pos) {return n = n & ~(1 << pos);}
  42. bool check_bit(int n, int pos) {return n = n & (1 << pos);}
  43.  
  44. void add (int & s, int n) {
  45.     if ((s & (1 << (n - 1)))) return;
  46.     s ^= (1 << (n - 1));
  47. }
  48.  
  49. void remove (int & s, int n) {
  50.     if (!(s & (1 << (n - 1)))) return;
  51.     s ^= (1 << (n - 1));
  52. }
  53.  
  54. void display (int s) {
  55.     for (int bit = 0; bit < 9; ++bit) {
  56.         if (s & (1 << bit)) {
  57.             cout << bit + 1 << ' ';
  58.         }
  59.     }
  60.     cout << '\n';
  61. }
  62. == == == == == == == == == == == =
  63.     [NUMBER THEORY SECTION]
  64.     == == == == == == == == == == == =
  65.  
  66.         /*
  67.         Fibonacchi
  68.         */
  69.  
  70. int64_t Fibo (int64_t n) {
  71.     //res[-1] = 0,res[0] = res[1] = 1;
  72.     //check fibo of n, cout << Fibo(n - 1);
  73.     if (res.find(n) != res.end()) {
  74.         return res[n];
  75.     }
  76.     if (n % 2 == 0) {
  77.         return res[n] = (Fibo(n / 2) * Fibo(n / 2) + Fibo(n / 2 - 1) * Fibo(n / 2 - 1)) % mod;
  78.     } else {
  79.         return res[n] = (Fibo(n / 2) * Fibo(n / 2 + 1) + Fibo(n / 2 - 1) * Fibo(n / 2)) % mod;
  80.     }
  81. }
  82.  
  83. /*
  84.  GCD & LCM Template
  85.  */
  86.  
  87. template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a % b) : a); }
  88. template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
  89.  
  90. /*
  91. Moduler Arithmetic
  92. */
  93. inline void normal(int64_t &a) { a %= mod; (a < 0) && (a += mod); }
  94. inline int64_t modMul(int64_t a, int64_t b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; }
  95. inline int64_t modAdd(int64_t a, int64_t b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; }
  96. inline int64_t modSub(int64_t a, int64_t b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; }
  97. inline int64_t modPow(int64_t b, int64_t p) { int64_t r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
  98. inline int64_t modInverse(int64_t a) { return modPow(a, mod - 2); }
  99. inline int64_t modDiv(int64_t a, int64_t b) { return modMul(a, modInverse(b)); }
  100.  
  101. == == == == == == =
  102.     [MOD Inversepar
  103.     == == == == == == =
  104.  
  105.  
  106.  
  107.         == == ==
  108.         [PBDS]
  109.         == == ==
  110. #include <ext/pb_ds/assoc_container.hpp>
  111. #include <ext/pb_ds/tree_policy.hpp>
  112.         template <typename K, typename V = __gnu_pbds::null_type>
  113. using tree = __gnu_pbds::tree<K, V, less<K>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  114. == == == == == == ==
  115. [MATH FORMULA]
  116. == == == == == == ==
  117. //sum of (n)
  118. int sum = n * (n + 1) / 2;
  119. //sum of(n^2)
  120. int sum = ((n * (n + 1)) * (2 * n + 1)) / 6;
  121. //sum of range
  122. sum_of_range = n * ((r - l + 1) * (l + r)) / 2;
  123. /*
  124.  Bitwise Sieve_of_Eratosthenes
  125.  */
  126. const int maxN = 10000;
  127. int64_t isVisited[maxN / 64 + 200];
  128. vector<int> primes;
  129. void Sieve_of_Eratosthenes(int limit) {
  130.     limit += 100;
  131.     for (int64_t i = 3; i <= sqrt(limit) ; i += 2) {
  132.         if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
  133.             for (int64_t j = i * i; j <= limit; j += 2 * i) {
  134.                 isVisited[j / 64] |= (1LL << (j % 64));
  135.             }
  136.         }
  137.     }
  138.     primes.push_back(2);
  139.     for (int64_t i = 3; i <= limit; i += 2) {
  140.         if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
  141.             primes.push_back(i);
  142.         }
  143.     }
  144. }
  145.  
  146. /*
  147.  IS PRIME Function(Bitwise Seive)
  148. */
  149. bool is_prime(int n) {
  150.     if (n < 2) return false;
  151.     if (n == 2) return true;
  152.     if (n % 2 == 0) return false;
  153.     if (!(isVisited[n / 64] & (1LL << (n % 64)))) return true;
  154.     return false;
  155. }
  156.  
  157.  
  158. /*
  159.  Generate All Divisors of a Number Using Prime Factorization
  160.  */
  161.  
  162. //Seive CODE Here
  163.  
  164. vector<int> setDivisors(int n, int i, vector<int> & divisors, vector<pair<int, int>> factors) {
  165.     int j, x, k;
  166.     for (j = i; j < (int) factors.size(); j++) {
  167.         x = factors[j].first * n;
  168.         for (k = 0; k < factors[j].second; k++) {
  169.             divisors.push_back(x);
  170.             setDivisors(x, j + 1, divisors, factors);
  171.             x *= factors[j].first;
  172.         }
  173.     }
  174.     return divisors;
  175. }
  176. vector<int> PF(int n) {
  177.     int x = n;
  178.     vector<pair<int, int>> factors;
  179.     for (auto i : primes) {
  180.         if (i * i > n) {
  181.             break;
  182.         }
  183.         if (n % i == 0) {
  184.             int count = 0;
  185.             while (n % i == 0) {
  186.                 n /= i;
  187.                 count += 1;
  188.             }
  189.             factors.push_back(make_pair(i, count));
  190.         }
  191.     }
  192.     if (n > 1) {
  193.         factors.push_back(make_pair(n, 1));
  194.     }
  195.     vector<int> d = {1};
  196.     vector<int> divisors = setDivisors(1, 0, d, factors);
  197.     return divisors;
  198. }
  199.  
  200. /*
  201. Generate Divisors in Sqrt(n) Time
  202. */
  203. vector<int> GEN_DIVS_SQRT(int n) {
  204.     vector<int> divisors;
  205.     for (int i = 1; i * i <= n; i++) {
  206.         if (n % i == 0) {
  207.             if (n / i != i) {
  208.                 divisors.push_back(n / i);
  209.             }
  210.             divisors.push_back(i);
  211.         }
  212.     }
  213.     return divisors;
  214. }
  215.  
  216. /*
  217. Count Divisors Using Prime Factorization
  218. */
  219. int COUNT_DIVISORS(int n) {
  220.     int divisors = 1;
  221.     for (auto i : primes) {
  222.         if (n % i == 0) {
  223.             if (i * i > n) {
  224.                 return divisors;
  225.             }
  226.             int count = 1;
  227.             while (n % i == 0) {
  228.                 n /= i;
  229.                 count += 1;
  230.             }
  231.             divisors *= count;
  232.         }
  233.     }
  234.     return divisors;
  235. }
  236.  
  237. == == == == == == == == == =
  238.     [ BIG MOD SECTION ]
  239.     == == == == == == == == == =
  240. //divide a long number(like 10^18)
  241. int Quotient(string s, int m) {
  242.     int count = 0;
  243.     for (int i = 0; i < (int) s.size(); i++) {
  244.         count = (count * 10 + (s[i] - 48)) % m;
  245.     }
  246.     return  count;
  247. }
  248.  
  249. == == == == == == == == == == == == == == =
  250.     [Range Minimum Query SECTION]
  251.     == == == == == == == == == == == == == == =
  252.         == == == == == == == == == == == == == ==
  253.         [SEGMENT TREE (SUM) EDITABLE]
  254.         == == == == == == == == == == == == == ==
  255.         const int maxN = 10000 * 4 + 1;
  256. int input[maxN / 4], tree[maxN];
  257. void buildTree(int idx, int start, int end) {
  258.     if (start == end) {
  259.         tree[idx] = input[start];
  260.     } else {
  261.         int mid = start + (end - start) / 2;
  262.         buildTree(idx * 2, start, mid);
  263.         buildTree(idx * 2 + 1, mid + 1, end);
  264.         tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
  265.     }
  266. }
  267. int query(int idx, int start, int end, int l, int r) {
  268.     if (l > end or r < start) {
  269.         return 0;
  270.     }
  271.     if (start >= l and  end <= r) {
  272.         return tree[idx];
  273.     }
  274.     int mid = start + (end - start) / 2;
  275.     return query(idx * 2, start, mid, l, r) + query(idx * 2 + 1, mid + 1, end, l, r);
  276. }
  277. void update(int idx, int l, int r, int pos, int val) {
  278.     set<char> res;
  279.     if (l == r) {
  280.         tree[idx] = val;
  281.     } else {
  282.         int mid = l + (r - l) / 2;
  283.         if (pos <= mid) {
  284.             update(idx * 2, l, mid, pos, val);
  285.         } else {
  286.             update(idx * 2 + 1, mid + 1, r, pos, val);
  287.         }
  288.         res.insert(tree[idx * 2].begin(), tree[idx * 2].end());
  289.         res.isnert(Tree[idx * 2 + 1].begin(), tree[idx * 2].end());
  290.         tree[idx] = res;
  291.     }
  292. }
  293. == == == == == == == == == == == == ==
  294. [DIS - JOINT SET UNION (DSU)]
  295. == == == == == == == == == == == == ==
  296. const int maxN = 100100;
  297. int parent[maxN];
  298.  
  299. int Find(int child) {
  300.     if (parent[child] < 0) {
  301.         return child;
  302.     }
  303.     return parent[child] = Find(parent[child]);
  304. }
  305.  
  306. void Union(int a, int b) {
  307.     parent[a] += parent[b];
  308.     parent[b] = a;
  309. }
  310. == == == == == == == == == =
  311.     [STRING ALGORITHMS]
  312.     == == == == == == == == == =
  313.         == == == == == == == == == == == == =
  314.             [   KMP SEARCH ALGORITHM]
  315.             [   COMPLEXITY : O(N + M) ]
  316.             == == == == == == == == == == == == =
  317.  
  318. vector<int> lps_array(string p) {
  319.     vector<int> lps((int) p.size());
  320.     int i = 1, idx = 0;
  321.     while (i < (int) p.size()) {
  322.         if (p[idx] == p[i]) {
  323.             lps[i] = idx + 1;
  324.             idx += 1, i += 1;
  325.         } else {
  326.             if (idx != 0) {
  327.                 idx = lps[idx - 1];
  328.             } else {
  329.                 lps[i] = 0;
  330.                 i += 1;
  331.             }
  332.         }
  333.     }
  334.     return lps;
  335. }
  336. void kmp(string s, string p) {
  337.     vector<int> lps = lps_array(p);
  338.     int i = 0, j = 0;
  339.     while (i < (int) s.size()) {
  340.         if (s[i] == p[j]) {
  341.             i += 1, j += 1;
  342.         } else {
  343.             if (j != 0) {
  344.                 j = lps[j - 1];
  345.             } else {
  346.                 i += 1;
  347.             }
  348.         }
  349.         if (j == (int) p.size()) {
  350.             cout << i - (int) p.size() << "\n";
  351.         }
  352.     }
  353. }
  354. == == == == == == ==
  355. [GRAPH THEORY]
  356. == == == == == == ==
  357. /*
  358.  Bipartile(Also Known as Two Coloring Problem) Checking
  359.  */
  360. const int maxN = 101;
  361. vector<int> adj[maxN];
  362. bool isVisited[maxN];
  363. int color[maxN];
  364. int Two_Coloring(int node, int col) {
  365.     isVisited[node] = true;
  366.     color[node] = col;
  367.     for (auto u : adj[node]) {
  368.         if (!isVisited[node]) {
  369.             if (!Two_Coloring(u, col ^ 1)) {
  370.                 return false;
  371.             }
  372.         } else {
  373.             if (color[node] == color[u`]) {
  374.                 return false;
  375.             }
  376.         }
  377.     }
  378.     return true;
  379. }
  380.  
  381. int dx[4] = {1, 0, -1, 0};
  382. int dy[4] = {0, 1, 0, -1};
  383.  
  384. /*
  385.  Cycle Detection / Finding Back Edge
  386.  */
  387. const int maxN = 101;
  388. vector<int> adj[maxN];
  389. bool isVisited[maxN];
  390. bool CycleDetection(int node, int parent) {
  391.     isVisited[node] = true;
  392.     for (auto u : adj[node]) {
  393.         if (!isVisited[u]) {
  394.             if (CycleDetection(u, node)) {
  395.                 return true;
  396.             }
  397.         }
  398.     } else {
  399.         if (u != parent) {
  400.             return true;
  401.         }
  402.     }
  403. }
  404. return false;
  405. }
  406.  
  407. /*
  408.  In and Out Time of a Node
  409.  */
  410. const int maxN = 101;
  411. vector<int> adj[maxN];
  412. bool isVisited[maxN];
  413. int InTime[maxN], OutTime[maxN];
  414. int Timer = 1;
  415. void InOutTime(int node) {
  416.     isVisited[node] = true;
  417.     InTime[node] = Timer++;
  418.     for (auto u : adj[node]) {
  419.         if (!isVisited[u]) {
  420.             InOutTime(u);
  421.         }
  422.     }
  423.     OutTime[node] = Timer++;
  424. }
  425.  
  426. /*
  427.  BFS : Breath First Search
  428.  */
  429. const int maxN = 101;
  430. vector<int> adj[maxN];
  431. bool isVisited[maxN];
  432. int dist[maxN];
  433. void BFS(int node) {
  434.     queue<int> q;
  435.     q.push(node);
  436.     isVisited[node] = true;
  437.     dist[node] = 0;
  438.     while (!q.empty()) {
  439.         int v = q.front();
  440.         for (auto u : adj[v]) {
  441.             if (!isVisited[u]) {
  442.                 isVisited[u] = true;
  443.                 dist[u] = dist[v] + 1;
  444.                 q.push(u);
  445.             }
  446.         }
  447.     }
  448. }
  449.  
  450. /*
  451.  Diameter of a Tree Using DFS
  452. */
  453.  
  454. const int maxN = 10100;
  455. int max_distance, max_node;
  456. vector<int> adj[maxN];
  457. bool isVisited[maxN];
  458. void diameter(int node, int distance) {
  459.     isVisited[node] = true;
  460.     if (distance > max_distance) {
  461.         max_distance = distance;
  462.         max_node = node; `
  463.     }
  464.     for (int child : adj[node]) {
  465.         if (!isVisited[child]) {
  466.             dfs(child, distance + 1);
  467.         }
  468.     }
  469. }
  470.  
  471. /*
  472.  Diameter of a Tree Using BFS
  473. */
  474. const int maxN = 10100;
  475. vector<int> adj[maxN];
  476. bool isVisited[maxN];
  477. int dist[maxN];
  478. pair<int, int> BFS(int node, int distance) {
  479.     int max_node = -1, max_dist = -1;
  480.     queue<int> q;
  481.     q.push(node);
  482.     dist[node] = distance;
  483.     while (!q.empty()) {
  484.         int v = q.front();
  485.         q.pop();
  486.         for (auto u : adj[v]) {
  487.             if (!isVisited[u]) {
  488.                 q.push(u);
  489.                 isVisited[u] = true;
  490.                 dist[u] = dist[v] + 1;
  491.                 if (dist[u] > max_dist) {
  492.                     max_dist = dist[u];
  493.                     max_node = u;
  494.                 }
  495.             }
  496.         }
  497.     }
  498.     return {max_node, max_dist};
  499. }
  500. /* Main Functon (DFS) */
  501. max_distance = -1;
  502. dfs(1, 0);
  503. for (int i = 1; i <= n; i++) {
  504.     isVisited[i] = false;
  505. }
  506. max_distance = -1;
  507. dfs(max_node, 0);
  508. cout << max_distance << "\n";
  509.  
  510. /* Main Function (BFS) */
  511. pair<int, int> node = BFS(1, 0);
  512. for (int i = 1; i <= n; i++) {
  513.     isVisited[i] = false;
  514.     dist[i] = 0;
  515. }
  516. node = BFS(node.first, 0);
  517. cout << node.second << "\n";
  518.  
  519. /*
  520.  Calculating SUbtree size using dfs in O(n) Time
  521. */
  522.  
  523. const int maxN = 101;
  524. vector<int> adj[maxN];
  525. bool isVisited[maxN];
  526. int subTreeSize[maxN];
  527. int dfs(int node) {
  528.     isVisited[node] = true;
  529.     int count = 1;
  530.     for (auto child : adj[node]) {
  531.         if (!isVisited[child]) {
  532.             count += dfs(child);
  533.         }
  534.     }
  535.     subTreeSize[node] = count;
  536. }
  537.  
  538. /*
  539.  Find Bridges Using DFS
  540. */
  541.  
  542. const int maxN = 101;
  543. const int maxN = 101;
  544. vector<int> adj[maxN];
  545. bool visited[maxN];
  546. int in[maxN], low[maxN];
  547. int timer = 0;
  548. void dfs(int node, int parent) {
  549.     visited[node] = true;
  550.     in[node] = low[node] = timer++;
  551.     for (auto child : adj[node]) {
  552.         if (child == parent) {
  553.             continue;
  554.         }
  555.         if (visited[child]) {
  556.             low[node] = min(low[node], in[child]);
  557.         } else {
  558.             dfs(child, node);
  559.             if (low[child] > in[node]) {
  560.                 cout << node << " -> " << child << " Is a Bridge\n";
  561.             }
  562.             low[node] = min(low[node], low[child]);
  563.         }
  564.     }
  565. }
  566.  
  567. /*
  568.     Build Suffix Array (basic)
  569. */
  570.  
  571. #include<bits/stdc++.h>
  572. using namespace std;
  573.  
  574. int main () {
  575.     ios::sync_with_stdio(false);
  576.     cin.tie(nullptr);
  577.     cout.tie(nullptr);
  578.     int T = 1;
  579.     //~ cin >> T;
  580.     for (int t = 1; t <= T; ++t) {
  581.         string s;
  582.         cin >> s;
  583.         s += '$';
  584.         int n = s.size();
  585.         int order[n]; // order
  586.         int class_[n]; // equivalent class
  587.         pair<char, int> pos[n]; // position
  588.         for (int i = 0; i < n; ++i) {
  589.             pos[i] = make_pair(s[i], i);
  590.         }
  591.         sort(pos, pos + n);
  592.         for (int i = 0; i < n; ++i) {
  593.             order[i] = pos[i].second;
  594.         }
  595.         class_[order[0]] = 0;
  596.         for (int i = 1; i < n; ++i) {
  597.             if (pos[i].first == pos[i - 1].first) {
  598.                 class_[order[i]] = class_[order[i - 1]];
  599.             } else {
  600.                 class_[order[i]] = class_[order[i - 1]] + 1;
  601.             }
  602.         }
  603.         int k = 0;
  604.         while ((1 << k) < n) {
  605.             pair<pair<int, int>, int> suf[n]; //positon array
  606.             for (int i = 0; i < n; ++i) {
  607.                 suf[i] = make_pair(make_pair(class_[i], class_[(i + (1 << k)) % n]), i);
  608.             }
  609.             sort(suf, suf + n);
  610.             for (int i = 0; i < n; ++i) {
  611.                 order[i] = suf[i].second;
  612.             }
  613.             class_[order[0]] = 0; // first class to be order[0] = 0
  614.             for (int i = 1; i < n; ++i) {
  615.                 if (suf[i].first == suf[i - 1].first) {
  616.                     class_[order[i]] = class_[order[i - 1]];
  617.                 } else {
  618.                     class_[order[i]] = class_[order[i - 1]] + 1;
  619.                 }
  620.             }
  621.             k += 1;
  622.         }
  623.         for (int i = 0; i < n; ++i) {
  624.             cout << order[i] << " ";
  625.         }
  626.     }
  627. }
  628.  
  629.  
  630. //[Count Set Bits]
  631. int count = 0;
  632. while (n) {
  633.     count += (n & 1);
  634.     n >>= 1;
  635. }
  636.  
  637. == == == == == == =
  638.     [Z Algorithm]
  639.     == == == == == == =
  640. vector<int> z_algo (string s) {
  641.     int n = (int) s.size();
  642.     int l = 0, r = 0;
  643.     vector<int> z(n);
  644.     for (int i = 1; i < n; ++i) {
  645.         if (i > r) {
  646.             l = r = i;
  647.             while (r < n and s[r] == s[r - l]) {
  648.                 ++r;
  649.             }
  650.             z[i] = r - l;
  651.             --r;
  652.         } else {
  653.             if (i + z[i - l] <= r) {
  654.                 z[i] = z[i - l];
  655.             } else {
  656.                 l = i;
  657.                 while (r < n and s[r] == s[r - l]) {
  658.                     ++r;
  659.                 }
  660.                 z[i] = r - l;
  661.                 --r;
  662.             }
  663.         }
  664.     }
  665.     return z;
  666. }
  667.  
  668. int main () {
  669.     ios::sync_with_stdio(false);
  670.     cin.tie(nullptr);
  671.     cout.tie(nullptr);
  672.     int T = 1;
  673.     //~ cin >> T;
  674.     for (int test_case = 1; test_case <= T; ++test_case) {
  675.         string s, t;
  676.         cin >> s >> t;
  677.         string total = t + "$" + s;
  678.         vector<int> z = z_algo(total);
  679.         for (int i = 0; i < (int) z.size(); ++i) {
  680.             if (z[i] == (int) t.size()) {
  681.                 cout << i - (int) t.size() - 1 << "\n";
  682.             }
  683.         }
  684.     }
  685.     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  686. }
  687.  
  688. == == == == == ==
  689. [BITMASK DP]
  690. == == == == == ==
  691. #include<bits/stdc++.h>
  692. using namespace std;
  693.  
  694. int mem[1000][1030];
  695.  
  696. bool check (int mask) {
  697.     return (bool) (mask & ((1 << 10) - 1));
  698. }
  699.  
  700. int solve (int pos, int n, int mask) {
  701.     if (pos >= n) {
  702.         return check(mask);
  703.     }
  704.     if (mem[pos][mask] != -1) {
  705.         return mem[pos][mask];
  706.     }
  707.     int res = 0;
  708.     for (int i = (pos == 0 ? 1 : pos); i <= 9; ++i) {
  709.         res += solve (pos + 1, n, mask | (1 << pos));
  710.     }
  711.     return mem[pos][mask] = res;
  712. }
  713.  
  714. int main () {
  715.     ios::sync_with_stdio(false);
  716.     cin.tie(nullptr);
  717.     cout.tie(nullptr);
  718.     int T = 1;
  719.     //~ cin >> T;
  720.     for (int test_case = 1; test_case <= T; ++test_case) {
  721.         memset(mem, -1, sizeof(mem));
  722.         int n;
  723.         cin >> n;
  724.         cout << solve (1, n, 0) << "\n";
  725.     }
  726.     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  727. }
  728.  
  729. == == == == ==
  730. [DIJKSTRA]
  731. == == == == ==
  732.  
  733. /*
  734. ======================
  735. [     ___T_          ]
  736. [    | 6=6 | =>HI :-)]
  737. [    |__o__|         ]
  738. [ >===]__o[===<      ]
  739. [     [o__]          ]
  740. [      .".           ]
  741. [      |_|           ]
  742. [                    ]
  743. ======================
  744. */
  745.  
  746. #include<bits/stdc++.h>
  747. using namespace std;
  748.  
  749. const int maxN = 2 * 1e5;
  750. vector<pair<int64_t, int64_t>> adj[maxN];
  751. int64_t dist[maxN];
  752.  
  753. void dijkstra (int source, int n) {
  754.     for (int i = 1; i <= n; ++i) dist[i] = LLONG_MAX;
  755.     dist[source] = 0;
  756.     priority_queue<pair<int64_t, int64_t>, vector<pair<int64_t, int64_t>>, greater<pair<int64_t, int64_t>>> pq;
  757.     pq.push(make_pair(0, source));
  758.  
  759.     while (!pq.empty()) {
  760.         int64_t u = pq.top().second;
  761.         int64_t current_dist = pq.top().first;
  762.         pq.pop();
  763.  
  764.         if (dist[u] < current_dist) {
  765.             continue;
  766.         }
  767.  
  768.         for (pair<int64_t, int64_t> v : adj[u]) {
  769.             if (current_dist + v.second < dist[v.first]) {
  770.                 dist[v.first] = current_dist + v.second;
  771.                 pq.push(make_pair(dist[v.first], v.first));
  772.             }
  773.         }
  774.     }
  775. }
  776.  
  777. int main () {
  778.     ios::sync_with_stdio(false);
  779.     cin.tie(nullptr);
  780.     cout.tie(nullptr);
  781.     int T = 1;
  782.     //~ cin >> T;
  783.     for (int test_case = 1; test_case <= T; ++test_case) {
  784.         int n, m;
  785.         cin >> n >> m;
  786.         for (int i = 1; i <= m; ++i) {
  787.             int64_t u, v, w;
  788.             cin >> u >> v >> w;
  789.             adj[u].push_back(make_pair(v, w));
  790.         }
  791.         dijkstra(1, n);
  792.         for (int i = 1; i <= n; ++i) {
  793.             cout << dist[i] << " ";
  794.         }
  795.     }
  796.     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  797. }
  798.  
  799.  
  800. Sparse Table
  801.  
  802. const int maxN = 1e5 + 10;
  803. int64_t st[maxN][20];
  804. int bin_log[maxN];
  805. int64_t input[maxN];
  806.  
  807. void sparseTable (int n) {
  808.     for (int i = 2; i <= n; ++i) bin_log[i] = bin_log[i / 2] + 1;
  809.     for (int i = 0; i < n; ++i) st[i][0] = input[i];
  810.     for (int j = 1; j < 20; ++j) {
  811.         for (int i = 0; i + (1 << j) - 1 < n; ++i) {
  812.             st[i][j] = max(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
  813.         }
  814.     }
  815.     //for query min_max
  816.     /*
  817.          int l,r;
  818.          cin >> l >> r;
  819.          int j = bin_log[r - l + 1];
  820.          cout << min(st[l][j],st[r - (1 << j) + 1][j]) << '\n';
  821.     */
  822. }
  823.  
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!