SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #pragma comment(linker, "/STACK:32000000")
  4. #pragma GCC optimize("O3")
  5.  
  6. #include <stdio.h>
  7. #include <string.h>
  8. #include <memory.h>
  9. #include <stdlib.h>
  10. #include <iostream>
  11. #include <time.h>
  12. #include <algorithm>
  13. #include <math.h>
  14. #include <vector>
  15. #include <set>
  16. #include <queue>
  17. #include <stack>
  18. #include <bitset>
  19. #include <string>
  20. #include <cstring>
  21. #include <cassert>
  22. #include <fstream>
  23. #include <map>
  24. #include <unordered_map>
  25. #include <deque>
  26.  
  27. using namespace std;
  28.  
  29. #define inf 1000000007
  30. #define eps 1e-9
  31. #define mp(a, b) make_pair(a, b)
  32. #define llinf 2000000000000000008LL
  33.  
  34. typedef long long ll;
  35. typedef unsigned u;
  36. typedef long double ld;
  37. typedef unsigned char uc;
  38. typedef unsigned long long ull;
  39.  
  40. ll c1 = 1999, mod1 = 1'000'000'007;
  41. int n, m;
  42. ll arr[200005];
  43. ll pow1[200005];
  44. ll h1[200005];
  45. ll hinv1[200005];
  46.  
  47. int main() {
  48.     ios_base::sync_with_stdio(0);
  49.     cin.tie(0);
  50.     cout.tie(0);
  51.     cin.sync_with_stdio(0);
  52.     cout.sync_with_stdio(0);
  53.     cout.precision(8);
  54.     srand(time(0));
  55.    
  56.     cin >> n >> m;
  57.     for (int i = 1; i <= n; i++) {
  58.         cin >> arr[i];
  59.     }
  60.     pow1[0] = 1;
  61.     for (int i = 1; i <= n; i++) {
  62.         pow1[i] = (pow1[i - 1] * c1) % mod1;
  63.     }
  64.     for (int i = 1; i <= n; i++) {
  65.         h1[i] = (h1[i - 1] + arr[i] * pow1[i - 1]) % mod1;
  66.     }
  67.     for (int i = n; i >= 1; i--) {
  68.         hinv1[i] = (hinv1[i + 1] + arr[i] * pow1[n - i]) % mod1;
  69.     }
  70.    
  71.     vector <int> ans;
  72.     for (int i = 0; i <= n / 2; i++) {
  73.         ll H1 = h1[i];
  74.         ll H2 = ((hinv1[i + 1] - hinv1[i + 1 + i]) % mod1 + mod1) % mod1;
  75.         int id1 = 1, id2 = n - i - i + 1;
  76.         if (id1 > id2) {
  77.             swap(id1, id2);
  78.             swap(H1, H2);
  79.         }
  80.         H1 = (H1 * pow1[id2 - id1]) % mod1;
  81.         if (H1 == H2) {
  82.             ans.push_back(n - i);
  83.         }
  84.    
  85.         }
  86.     }
  87.     sort(ans.begin(), ans.end());
  88.     for (auto &i : ans) {
  89.         cout << i << " ";
  90.     }
  91.     return 0;
  92. }
RAW Paste Data
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
 
Top