Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cassert>
- #include <cmath>
- #include <cstring>
- #include <deque>
- #include <fstream>
- #include <iomanip>
- #include <iostream>
- #include <limits>
- #include <map>
- #include <numeric>
- #include <ostream>
- #include <queue>
- #include <random>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <string>
- #include <unordered_map>
- #include <unordered_set>
- #include <vector>
- using namespace std;
- /// Pragmas ///
- #pragma GCC optimize("Ofast, O3, unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
- /// Defines ///
- typedef long long ll;
- /// consts ///
- long long N = 100100;
- vector<bool> used(N);
- vector<vector<int>> g(N);
- vector<int> dist(N);
- vector<int> isPrime(N, true);
- /// Geometry ///
- struct Vector {
- double x, y;
- Vector() {}
- Vector(double x1, double y1) {
- x = x1;
- y = y1;
- }
- Vector(Vector a, Vector b) {
- x = b.x - a.x;
- y = b.y - a.y;
- }
- Vector operator+(Vector other) const {
- return Vector(x + other.x, y + other.y);
- }
- Vector operator-(Vector other) const {
- return Vector(x - other.x, y - other.y);
- }
- Vector operator*(double d) { return Vector(x * d, y * d); }
- double operator*(Vector other) const { return x * other.x + y * other.y; }
- long long operator^(Vector other) const { return x * other.y - y * other.x; }
- long long len2() { return x * x + y * y; }
- long long len() { return sqrt(len2()); }
- };
- typedef Vector Point;
- double Angle(Vector a, Vector b) { return atan2(a ^ b, a * b); }
- double Dist(Vector a, Vector b) { return Vector(a, b).len(); }
- double Area(Point a, Point b, Point c) {
- Vector ab(a, b);
- Vector ac(a, c);
- return (double)abs(ab ^ ac) / 2;
- }
- istream &operator>>(istream &in, Point &p) {
- in >> p.x >> p.y;
- return in;
- }
- ostream &operator<<(ostream &out, Point p) {
- out << p.x << ' ' << p.y;
- return out;
- }
- /// GCD & LCM ///
- ll gcd(ll a, ll b) { return (b ? gcd(b, a % b) : a); }
- ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
- /// DFS ///
- void dfs(int v) {
- used[v] = true;
- for (int i = 0; i < g[v].size(); i++) {
- int u = g[v][i];
- if (!used[u])
- dfs(u);
- }
- }
- /// BFS ///
- void bfs(int start, int end) {
- dist[start] = 0;
- used[start] = true;
- queue<int> q;
- q.push(start);
- while (!q.empty()) {
- int v = q.front();
- q.pop();
- for (int i = 0; i < g[v].size(); i++) {
- int u = g[v][i];
- if (dist[v] + 1 < dist[u]) {
- used[u] = true;
- dist[u] = dist[v] + 1;
- q.push(u);
- }
- }
- }
- }
- /// SIEVE ///
- void sieve() {
- isPrime[0] = isPrime[1] = false;
- for (int i = 2; i < N; i++) {
- if (isPrime[i]) {
- for (int j = i * i; j < N; j += i) {
- isPrime[j] = false;
- }
- }
- }
- }
- /// CountDivs ///
- vector<int> divs;
- int countDivs(int n) {
- int cnt = 2;
- divs.push_back(1);
- divs.push_back(n);
- for (int i = 2; i * i <= n; i++) {
- if (n % i == 0) {
- cnt += 2;
- divs.push_back(i);
- divs.push_back(n / i);
- if (i * i == n) {
- cnt--;
- divs.pop_back();
- }
- }
- }
- return cnt;
- }
- /// BinPow ///
- ll binPow(ll x, ll n) {
- if (n == 0) {
- return 1;
- }
- if (n % 2 == 0) {
- ll a = binPow(x, n / 2);
- return a * a;
- } else {
- ll a = binPow(x, n - 1);
- return x * a;
- }
- }
- /// Extended Euclid algorithm ///
- int gcdExtended(int a, int b, int *x, int *y) {
- if (a == 0) {
- *x = 0;
- *y = 1;
- return b;
- }
- int x1, y1;
- int gcd = gcdExtended(b % a, a, &x1, &y1);
- *x = y1 - (b / a) * x1;
- *y = x1;
- return gcd;
- }
- /// dijstra ///
- void dijkstra(ll s) {
- dist[s] = 0;
- set<pair<ll, ll>> q;
- q.emplace(dist[s], s);
- while (!q.empty()) {
- ll v = q.begin()->second;
- q.erase(q.begin());
- for (int i = 0; i < g[v].size(); ++i) {
- ll u = g[v][i].second;
- ll len = g[v][i].first;
- if (dist[u] < dist[v] + len) {
- q.erase({dist[u], u});
- dist[u] = dist[v] + len;
- q.emplace(dist[u], u);
- }
- }
- }
- }
- /// DSU ///
- vector <int> dsu_par(1e5+50000);
- vector <int> dsu_sz(1e5+50000);
- ll dsu_setId(ll v) {
- if (dsu_par[v] == v)
- return v;
- else
- return dsu_par[v] = dsu_setId(dsu_par[v]);
- }
- void dsu_union(ll a, ll b) {
- ll x = dsu_setId(a);
- ll y = dsu_setId(b);
- if (dsu_sz[x] < dsu_sz[y])
- swap(x,y);
- dsu_par[x] = y;
- dsu_sz[x] += dsu_sz[y];
- }
- bool dsu_check(ll a, ll b) {
- if (dsu_setId(a) == dsu_setId(b)) {
- return true;
- } else {
- return false;
- }
- }
- /// segtree ///
- struct segtree {
- struct node {
- int x;
- };
- vector<node> tree;
- int size;
- const node ZERO = {0};
- node one_element(int a) { return {a}; }
- node combine(node a, node b) { return {a.x + b.x}; }
- void init(int n) {
- size = 1;
- while (size < n)
- size *= 2;
- tree.assign(2 * size - 1, ZERO);
- }
- void build(vector<int> &q, int x, int lx, int rx) {
- if (rx - lx == 1) {
- if (lx < q.size()) {
- tree[x] = node({1});
- }
- return;
- }
- int m = lx + (rx - lx) / 2;
- build(q, 2 * x + 1, lx, m);
- build(q, 2 * x + 2, m, rx);
- tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
- }
- void build(vector<int> &q) {
- init(q.size());
- build(q, 0, 0, size);
- }
- void set(int i, int v, int x, int lx, int rx) {
- if (rx - lx == 1) {
- tree[x] = node({v});
- return;
- }
- int m = lx + (rx - lx) / 2;
- if (i < m)
- set(i, v, 2 * x + 1, lx, m);
- else
- set(i, v, 2 * x + 2, m, rx);
- tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
- }
- void set(int i, int v) { set(i, v, 0, 0, size); }
- int calc(int l, int r, int x, int lx, int rx) {
- if (lx >= r || rx <= l) {
- return 0;
- }
- if (lx >= l && rx <= r) {
- return tree[x].x;
- }
- int m = lx + (rx - lx)/2;
- int s1 = calc(l, r, 2*x+1, lx, m);
- int s2 = calc(l, r, 2*x+2, m, rx);
- return s1 + s2;
- }
- int calc(int l, int r) { return calc(l,r, 0, 0, size); }
- };
- /// stack min ///
- struct stack_min {
- vector<int> val;
- vector<int> val_min = {((ll) 1e9)};
- void push(int v) {
- val.push_back(v);
- val_min.push_back(min(val_min.back(), v));
- }
- void pop() {
- val_min.pop_back();
- val.pop_back();
- }
- int get_min() {
- return val_min.back();
- }
- int back() {
- return val.back();
- }
- };
- /// queue min ///
- struct queue_min {
- stack_min st1, st2;
- void push(int v) {
- st1.push(v);
- }
- void pop() {
- if (st2.val.size()) {
- st2.pop();
- } else {
- while (st1.val.size()) {
- st2.push(st1.back());
- st1.pop();
- }
- st2.pop();
- }
- }
- int get_min() {
- return min(st1.get_min(), st2.get_min());
- }
- };
- /// next under
- vector<int> next_under_right(vector<int> &q) {
- vector<int> st;
- vector<int> ans(q.size());
- for (int i = 0; i < q.size(); ++i) {
- while (st.size() && q[st.back()] > q[i]) {
- ans[st.back()] = i;
- st.pop_back();
- }
- st.push_back(i);
- }
- while (!st.empty()) {
- ans[st.back()] = q.size();
- st.pop_back();
- }
- return ans;
- }
- /// substring ///
- void substring() {
- vector <ll> p_pow(s.size() + 1, 1), pr(s.size() + 1, 0);
- //
- for (int i = 0; i < s.size(); ++i) {
- p_pow[i+1] = (p_pow[i] * p) % MOD;
- }
- //
- for (int i = 0; i < s.size(); ++i) {
- pr[i+1] = (pr[i] * p + s[i]) % MOD;
- }
- //
- ll h = 0;
- for (int i = 0; i < t.size(); ++i) {
- h = (h * p + t[i]) % MOD;
- }
- //
- vector <int> ans;
- for (int i = 0; i <= s.size() - t.size(); ++i) {
- ll h_nw = (pr[i + t.size()] - (pr[i] * p_pow[t.size()]) + MOD * MOD) % MOD;
- if (h_nw == h) {
- ans.push_back(i);
- }
- }
- cout << ans.size() << '\n';
- for (auto& x : ans) cout << x << ' ';
- }
- void solve() {}
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- int t = 1;
- // cin >> t;
- while (t--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement