Advertisement
clown1337

Untitled

Nov 24th, 2023 (edited)
518
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.09 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <deque>
  7. #include <fstream>
  8. #include <iomanip>
  9. #include <iostream>
  10. #include <limits>
  11. #include <map>
  12. #include <numeric>
  13. #include <ostream>
  14. #include <queue>
  15. #include <random>
  16. #include <set>
  17. #include <sstream>
  18. #include <stack>
  19. #include <string>
  20. #include <unordered_map>
  21. #include <unordered_set>
  22. #include <vector>
  23.  
  24. using namespace std;
  25. /// Pragmas ///
  26. #pragma GCC optimize("Ofast, O3, unroll-loops")
  27. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
  28. /// Defines ///
  29. typedef long long ll;
  30. /// consts ///
  31. long long N = 100100;
  32. vector<bool> used(N);
  33. vector<vector<int>> g(N);
  34. vector<int> dist(N);
  35. vector<int> isPrime(N, true);
  36. /// Geometry ///
  37. struct Vector {
  38.   double x, y;
  39.   Vector() {}
  40.   Vector(double x1, double y1) {
  41.     x = x1;
  42.     y = y1;
  43.   }
  44.   Vector(Vector a, Vector b) {
  45.     x = b.x - a.x;
  46.     y = b.y - a.y;
  47.   }
  48.   Vector operator+(Vector other) const {
  49.     return Vector(x + other.x, y + other.y);
  50.   }
  51.   Vector operator-(Vector other) const {
  52.     return Vector(x - other.x, y - other.y);
  53.   }
  54.   Vector operator*(double d) { return Vector(x * d, y * d); }
  55.   double operator*(Vector other) const { return x * other.x + y * other.y; }
  56.   long long operator^(Vector other) const { return x * other.y - y * other.x; }
  57.   long long len2() { return x * x + y * y; }
  58.   long long len() { return sqrt(len2()); }
  59. };
  60. typedef Vector Point;
  61. double Angle(Vector a, Vector b) { return atan2(a ^ b, a * b); }
  62.  
  63. double Dist(Vector a, Vector b) { return Vector(a, b).len(); }
  64.  
  65. double Area(Point a, Point b, Point c) {
  66.   Vector ab(a, b);
  67.   Vector ac(a, c);
  68.   return (double)abs(ab ^ ac) / 2;
  69. }
  70.  
  71. istream &operator>>(istream &in, Point &p) {
  72.   in >> p.x >> p.y;
  73.   return in;
  74. }
  75.  
  76. ostream &operator<<(ostream &out, Point p) {
  77.   out << p.x << ' ' << p.y;
  78.   return out;
  79. }
  80. /// GCD & LCM ///
  81. ll gcd(ll a, ll b) { return (b ? gcd(b, a % b) : a); }
  82.  
  83. ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
  84. /// DFS ///
  85. void dfs(int v) {
  86.   used[v] = true;
  87.   for (int i = 0; i < g[v].size(); i++) {
  88.     int u = g[v][i];
  89.     if (!used[u])
  90.       dfs(u);
  91.   }
  92. }
  93. /// BFS ///
  94. void bfs(int start, int end) {
  95.   dist[start] = 0;
  96.   used[start] = true;
  97.   queue<int> q;
  98.   q.push(start);
  99.   while (!q.empty()) {
  100.     int v = q.front();
  101.     q.pop();
  102.     for (int i = 0; i < g[v].size(); i++) {
  103.       int u = g[v][i];
  104.       if (dist[v] + 1 < dist[u]) {
  105.         used[u] = true;
  106.         dist[u] = dist[v] + 1;
  107.         q.push(u);
  108.       }
  109.     }
  110.   }
  111. }
  112. /// SIEVE ///
  113. void sieve() {
  114.   isPrime[0] = isPrime[1] = false;
  115.   for (int i = 2; i < N; i++) {
  116.     if (isPrime[i]) {
  117.       for (int j = i * i; j < N; j += i) {
  118.         isPrime[j] = false;
  119.       }
  120.     }
  121.   }
  122. }
  123. /// CountDivs ///
  124. vector<int> divs;
  125. int countDivs(int n) {
  126.   int cnt = 2;
  127.   divs.push_back(1);
  128.   divs.push_back(n);
  129.   for (int i = 2; i * i <= n; i++) {
  130.     if (n % i == 0) {
  131.       cnt += 2;
  132.       divs.push_back(i);
  133.       divs.push_back(n / i);
  134.       if (i * i == n) {
  135.         cnt--;
  136.         divs.pop_back();
  137.       }
  138.     }
  139.   }
  140.   return cnt;
  141. }
  142. /// BinPow ///
  143. ll binPow(ll x, ll n) {
  144.   if (n == 0) {
  145.     return 1;
  146.   }
  147.   if (n % 2 == 0) {
  148.     ll a = binPow(x, n / 2);
  149.     return a * a;
  150.   } else {
  151.     ll a = binPow(x, n - 1);
  152.     return x * a;
  153.   }
  154. }
  155. /// Extended Euclid algorithm ///
  156. int gcdExtended(int a, int b, int *x, int *y) {
  157.   if (a == 0) {
  158.     *x = 0;
  159.     *y = 1;
  160.     return b;
  161.   }
  162.   int x1, y1;
  163.   int gcd = gcdExtended(b % a, a, &x1, &y1);
  164.   *x = y1 - (b / a) * x1;
  165.   *y = x1;
  166.   return gcd;
  167. }
  168. /// dijstra ///
  169. void dijkstra(ll s) {
  170.   dist[s] = 0;
  171.   set<pair<ll, ll>> q;
  172.   q.emplace(dist[s], s);
  173.   while (!q.empty()) {
  174.     ll v = q.begin()->second;
  175.     q.erase(q.begin());
  176.     for (int i = 0; i < g[v].size(); ++i) {
  177.       ll u = g[v][i].second;
  178.       ll len = g[v][i].first;
  179.       if (dist[u] < dist[v] + len) {
  180.         q.erase({dist[u], u});
  181.         dist[u] = dist[v] + len;
  182.         q.emplace(dist[u], u);
  183.       }
  184.     }
  185.   }
  186. }
  187. /// DSU ///
  188. vector <int> dsu_par(1e5+50000);
  189. vector <int> dsu_sz(1e5+50000);
  190.  
  191. ll dsu_setId(ll v) {
  192.     if (dsu_par[v] == v)
  193.         return v;
  194.     else
  195.         return dsu_par[v] = dsu_setId(dsu_par[v]);
  196. }
  197.  
  198. void dsu_union(ll a, ll b) {
  199.     ll x = dsu_setId(a);
  200.     ll y = dsu_setId(b);
  201.     if (dsu_sz[x] < dsu_sz[y])
  202.         swap(x,y);
  203.     dsu_par[x] = y;
  204.     dsu_sz[x] += dsu_sz[y];
  205. }
  206.  
  207. bool dsu_check(ll a, ll b) {
  208.     if (dsu_setId(a) == dsu_setId(b)) {
  209.         return true;
  210.     } else {
  211.         return false;
  212.     }
  213. }
  214. /// segtree ///
  215. struct segtree {
  216.   struct node {
  217.     int x;
  218.   };
  219.  
  220.   vector<node> tree;
  221.   int size;
  222.  
  223.   const node ZERO = {0};
  224.   node one_element(int a) { return {a}; }
  225.  
  226.   node combine(node a, node b) { return {a.x + b.x}; }
  227.  
  228.   void init(int n) {
  229.     size = 1;
  230.     while (size < n)
  231.       size *= 2;
  232.     tree.assign(2 * size - 1, ZERO);
  233.   }
  234.  
  235.   void build(vector<int> &q, int x, int lx, int rx) {
  236.     if (rx - lx == 1) {
  237.       if (lx < q.size()) {
  238.         tree[x] = node({1});
  239.       }
  240.       return;
  241.     }
  242.     int m = lx + (rx - lx) / 2;
  243.     build(q, 2 * x + 1, lx, m);
  244.     build(q, 2 * x + 2, m, rx);
  245.     tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  246.   }
  247.  
  248.   void build(vector<int> &q) {
  249.     init(q.size());
  250.     build(q, 0, 0, size);
  251.   }
  252.  
  253.   void set(int i, int v, int x, int lx, int rx) {
  254.     if (rx - lx == 1) {
  255.       tree[x] = node({v});
  256.       return;
  257.     }
  258.     int m = lx + (rx - lx) / 2;
  259.     if (i < m)
  260.       set(i, v, 2 * x + 1, lx, m);
  261.     else
  262.       set(i, v, 2 * x + 2, m, rx);
  263.     tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  264.   }
  265.  
  266.   void set(int i, int v) { set(i, v, 0, 0, size); }
  267.  
  268.   int calc(int l, int r, int x, int lx, int rx) {
  269.     if (lx >= r || rx <= l) {
  270.       return 0;
  271.     }
  272.     if (lx >= l && rx <= r) {
  273.       return tree[x].x;
  274.     }
  275.     int m = lx + (rx - lx)/2;
  276.     int s1 = calc(l, r, 2*x+1, lx, m);
  277.     int s2 = calc(l, r, 2*x+2, m, rx);
  278.     return s1 + s2;
  279.  
  280.   }
  281.  
  282.   int calc(int l, int r) { return calc(l,r, 0, 0, size); }
  283. };
  284.  
  285. /// stack min ///
  286. struct stack_min {
  287.   vector<int> val;
  288.   vector<int> val_min = {((ll) 1e9)};
  289.  
  290.   void push(int v) {
  291.     val.push_back(v);
  292.     val_min.push_back(min(val_min.back(), v));
  293.   }
  294.   void pop() {
  295.     val_min.pop_back();
  296.     val.pop_back();
  297.   }
  298.   int get_min() {
  299.     return val_min.back();
  300.   }
  301.   int back() {
  302.     return val.back();
  303.   }
  304. };
  305. /// queue min ///
  306. struct queue_min {
  307.   stack_min st1, st2;
  308.   void push(int v) {
  309.     st1.push(v);
  310.   }
  311.   void pop() {
  312.     if (st2.val.size()) {
  313.       st2.pop();
  314.     } else {
  315.       while (st1.val.size()) {
  316.         st2.push(st1.back());
  317.         st1.pop();
  318.       }
  319.       st2.pop();
  320.     }
  321.   }
  322.   int get_min() {
  323.     return min(st1.get_min(), st2.get_min());
  324.   }
  325. };
  326. /// next under
  327. vector<int> next_under_right(vector<int> &q) {
  328.   vector<int> st;
  329.   vector<int> ans(q.size());
  330.   for (int i = 0; i < q.size(); ++i) {
  331.     while (st.size() && q[st.back()] > q[i]) {
  332.       ans[st.back()] = i;
  333.       st.pop_back();
  334.     }
  335.     st.push_back(i);
  336.   }
  337.   while (!st.empty()) {
  338.     ans[st.back()] = q.size();
  339.     st.pop_back();
  340.   }
  341.   return ans;
  342. }
  343. /// substring ///
  344. void substring() {
  345.   vector <ll> p_pow(s.size() + 1, 1), pr(s.size() + 1, 0);
  346.     //  
  347.     for (int i = 0; i < s.size(); ++i) {
  348.         p_pow[i+1] = (p_pow[i] * p) % MOD;
  349.     }
  350.     //  
  351.     for (int i = 0; i < s.size(); ++i) {
  352.         pr[i+1] = (pr[i] * p + s[i]) % MOD;
  353.     }
  354.     //  
  355.     ll h = 0;
  356.     for (int i = 0; i < t.size(); ++i) {
  357.         h = (h * p + t[i]) % MOD;
  358.     }
  359.     //
  360.     vector <int> ans;
  361.     for (int i = 0; i <= s.size() - t.size(); ++i) {
  362.         ll h_nw = (pr[i + t.size()] - (pr[i] * p_pow[t.size()]) + MOD * MOD) % MOD;
  363.         if (h_nw == h) {
  364.             ans.push_back(i);
  365.         }
  366.     }
  367.     cout << ans.size() << '\n';
  368.     for (auto& x : ans) cout << x << ' ';
  369. }
  370. void solve() {}
  371.  
  372. signed main() {
  373.   ios_base::sync_with_stdio(false);
  374.   cin.tie(NULL);
  375.   cout.tie(NULL);
  376.   int t = 1;
  377.   // cin >> t;
  378.   while (t--)
  379.     solve();
  380.   return 0;
  381. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement