Advertisement
999ms

test

Jan 28th, 2020
237
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7.  
  8. template<ll MOD, ll p>
  9. struct THash {
  10.     int n;
  11.     vector<int> t;
  12.     vector<int> pw;
  13.     THash(const vector<int>& s)
  14.         : n(s.size())
  15.         , t(n)
  16.         , pw(n + 1)
  17.     {
  18.         pw[0] = 1;
  19.         t[0] = s[0];
  20.         for (int i = 1; i < n; i++) {
  21.             t[i] = (s[i] + t[i - 1] * p) % MOD;
  22.             pw[i] = pw[i - 1] * p % MOD;
  23.         }
  24.     }
  25.     int operator () (int l, int r) {
  26.         if (r < l) return 0;
  27.         return (t[r] + MOD - (l ? t[l - 1] * 1LL * pw[r - l + 1] % MOD : 0)) % MOD;
  28.     }
  29. };
  30.  
  31.  
  32. template<ll mod, int n, ll m>
  33. void Test() {
  34.     vector<int> arr(n);
  35.     const int Size = n / 1000;
  36.     vector<int> brr(Size * 2);
  37.     for (int i = 0; i < n; i++) {
  38.         arr[i] = (rand() % m) + 1;
  39.     }
  40.     for (int i = 0; i < Size; i++) {
  41.         brr[i] = (rand() % m) + 1;
  42.         brr[i + Size] = brr[i];
  43.     }
  44.     unordered_set<int> hshs;
  45.     THash<mod, m + 1> a(arr);
  46.     THash<mod, m + 1> b(brr);
  47.     for (int i = 0; i < Size; i++) {
  48.         hshs.insert(b(i, i + Size - 1));
  49.     }
  50.     vector<bool> cyc(n, false);
  51.     for (int i = 0; i + Size <= n; i++) {
  52.         if (hshs.count(a(i, i + Size - 1))) {
  53.             cyc[i] = true;
  54.         }
  55.     }
  56.  
  57.     for (int i = 0; i < n; i++) {
  58.         if (cyc[i]) {
  59.             bool ans = false;
  60.             for (int start = 0; start < Size && !ans; start++) {
  61.                 bool current = true;
  62.                 for (int j = 0; j < Size && current; j++) {
  63.                     current &= arr[i + j] == brr[start + j];
  64.                 }
  65.                 ans |= current;
  66.             }
  67.             if (!ans) {
  68.                 cout << "FAILED!!!" << endl;
  69.                 assert(false);
  70.             }
  71.         }
  72.     }
  73.     cout << "passed " << accumulate(all(cyc), 0) << endl;
  74. }
  75.  
  76. int main() {
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(nullptr);
  79.     cout.tie(nullptr);
  80.     const int T = 500;
  81.     const ll mod = 1e9 + 9;
  82.     const int n = 1e4;
  83.     const ll m = 2;
  84.     cout << "Test cases : " << T << endl;
  85.     cout << "Modulo : " << mod << endl;
  86.     cout << "Length of a : " << n << endl;
  87.     cout << "Length of b : " << n / 1000 << endl;
  88.     cout << "Alphabet : " << m << endl;
  89.  
  90.     for (int i = 0; i < T; i++) {
  91.         cout << i + 1 << " ";
  92.         Test<mod, n, m>();
  93.     }
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement