Salvens

I

Aug 9th, 2023
989
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.07 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8.  
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #pragma comment(linker,"/STACK:1000000000,1000000000")
  14.  
  15. const long long INF = 1e9 + 7;
  16. const int MAXN = 1e6 + 5;
  17. const int N = 1e5 + 10;
  18.  
  19. const int M1 = 1e9 + 123;
  20. const int M2 = 1e9 + 321;
  21. int P1 = 22811;
  22. int P2 = 22699;
  23.  
  24. array<int, MAXN> power1, power2;
  25.  
  26. inline void init_pow() {
  27.     power1[0] = 1;
  28.     power2[0] = 1;
  29.     for (int i = 1; i < MAXN; ++i) {
  30.         power1[i] = (1ll * power1[i - 1] * P1) % M1;
  31.         power2[i] = (1ll * power2[i - 1] * P2) % M2;
  32.     }
  33. }
  34.  
  35. inline void build_hash(vector<int>& s, vector<pair<int, int>>& h) {
  36.     int n = s.size();
  37.     h.resize(n + 1);
  38.     h[0].first = 0;
  39.     h[0].second = 0;
  40.  
  41.     for (int i = 0; i < n; ++i) {
  42.         h[i + 1].first = (h[i].first + 1ll * s[i] * power1[i]) % M1;
  43.         h[i + 1].second = (h[i].second + 1ll * s[i] * power2[i]) % M2;
  44.     }
  45. }
  46.  
  47. inline pair<int, int> get_hash(vector<pair<int, int>>& h, int pos, int len, int mx_pow = 0) {
  48.     int h1 = h[pos + len].first - h[pos].first;
  49.     int h2 = h[pos + len].second - h[pos].second;
  50.     if (h1 < 0) {
  51.         h1 += M1;
  52.     }
  53.     if (h2 < 0) {
  54.         h2 += M2;
  55.     }
  56.     if (mx_pow != 0) {
  57.         h1 = h1 * power1[mx_pow - (pos + len - 1)] % M1;
  58.         h2 = h2 * power2[mx_pow - (pos + len - 1)] % M2;
  59.     }
  60.     return make_pair(h1, h2);
  61. }
  62.  
  63. inline bool is_equal(vector<pair<int, int>>& h_l, vector<pair<int, int>>& h_r, int start1, int start2, int len) {
  64.     pair<int, int> d_l, d_r;
  65.     d_l.first = ((h_l[start1 + len].first - h_l[start1].first + M1) % M1 * 1ll * power1[start2]) % M1;
  66.     d_l.second = ((h_l[start1 + len].second - h_l[start1].second + M2) % M2 * 1ll * power2[start2]) % M2;
  67.  
  68.     d_r.first = ((h_r[start2 + len].first - h_r[start2].first + M1) % M1 * 1ll * power1[start1]) % M1;
  69.     d_r.second = ((h_r[start2 + len].second - h_r[start2].second + M2) % M2 * 1ll * power2[start1]) % M2;
  70.  
  71.     return d_l == d_r;
  72. }
  73.  
  74. inline int random_key(const int before, const int after) {
  75.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  76.     std::mt19937 mt_rand(seed);
  77.     int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
  78.     return base;
  79. }
  80.  
  81. signed main() {
  82.     ios_base::sync_with_stdio(false);
  83.     cin.tie(nullptr);
  84.     cout.tie(nullptr);
  85.  
  86.     P1 = random_key(256, M1);
  87.     P2 = random_key(256, M2);
  88.  
  89.     int n, m;
  90.     cin >> n >> m;
  91.     vector<int> a(n), b(n);
  92.     for (int i = 0; i < n; ++i) {
  93.         cin >> a[i];
  94.         b[i] = a[i];
  95.     }
  96.     reverse(b.begin(), b.end());
  97.  
  98.  
  99.     vector<pair<int, int>> h_a, h_b;
  100.     init_pow();
  101.     build_hash(a, h_a);
  102.     build_hash(b, h_b);
  103.  
  104.     vector<int> ans = {n};
  105.     for (int i = 1; i <= n / 2; ++i) {
  106.         if (get_hash(h_a, 0, i, n) == get_hash(h_b, n - 2 * i, i, n)) {
  107.             ans.emplace_back(n - i);
  108.         }
  109.     }
  110.     sort(ans.begin(), ans.end());
  111.     for (const auto& i: ans) {
  112.         cout << i << ' ';
  113.     }
  114. }
Advertisement
Add Comment
Please, Sign In to add comment