fork download 
  1. #include <bits/stdc++.h>
  2. #define pub push_back
  3. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  4. #define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
  5. #define all(x) begin(x), end(x)
  6. #define pii pair<int, int>
  7. #define fi first
  8. #define se second
  9. #define int long long
  10. using namespace std;
  11.  
  12. const int N = 3e6 + 5;
  13. const int M = 350;
  14. const int LOG = 19;
  15. const int mod = 1e9 + 7;
  16. const int inf = 3e18;
  17.  
  18. string s;
  19. int n, base[N], f[N], prefix[N], ans = 0;
  20. map <int, bool> used;
  21. deque <int> dq;
  22.  
  23. int minusMod(int a, int b) {
  24.     return ((a - b) % mod + mod) % mod;
  25. }
  26. int mulMod(int a, int b) {
  27.     return (a * b) % mod;
  28. }
  29. void calBase() {
  30.     base[0] = 1;
  31.     FOR(i, 1, n, 1) {
  32.         base[i] = (base[i - 1] * 256) % mod;
  33.     }
  34. }
  35. void hashing(string s) {
  36.     FOR(i, 1, n, 1) {
  37.         f[i] = (f[i - 1] * 256 + (int)s[i]) % mod;
  38.     }
  39. }
  40. int getHash(int l, int r) {
  41.     return minusMod(f[r], mulMod(f[l - 1], base[r - l + 1]));
  42. }
  43. void push(int i) {
  44.     while(!dq.empty() && prefix[i] <= prefix[dq.back()]) {
  45.         dq.pop_back();
  46.     }
  47.     dq.push_back(i);
  48. }
  49. void pop(int i) {
  50.     if (i == dq.front()) {
  51.         dq.pop_front();
  52.     }
  53. }
  54. void input() {
  55.     cin >> n;
  56.     cin >> s;
  57.     s += s; s.pop_back(); s.insert(0, " ");
  58.     calBase();
  59.  
  60.  
  61.     int l = 3, r = 8;
  62.     hashing(s);
  63.     int hash1 = getHash(l, r);
  64.     cout << hash1 << '\n';
  65.     cout << l  << " " << r<< '\n';
  66.     cout << s.substr(l, r - l + 1) << '\n';
  67.  
  68.     l = 5, r = 10;
  69.     hashing(s);
  70.     hash1 = getHash(l, r);
  71.     cout << hash1 << '\n';
  72.     cout << l  << " " << r<< '\n';
  73.     cout << s.substr(l, r - l + 1) << '\n';
  74. }
  75.  
  76. void solve() {
  77.     input();
  78. //    FOR(i, 1, 2 * n - 1, 1) {
  79. //        prefix[i] = prefix[i - 1] + (s[i] == '(' ? 1 : -1);
  80. //    }
  81. //
  82. //    FOR(r, 1, n, 1) {
  83. //        push(r);
  84. //    }
  85. //
  86. //    FOR(r, n + 1, 2 * n - 1, 1) {
  87. //        int l = (r - n + 1);
  88. //        pop(l - 1); push(r);
  89. //
  90. //        if (prefix[r] - prefix[l - 1] != 0) continue;
  91. //        if (prefix[dq.front()] - prefix[l - 1] < 0) continue;
  92. //
  93. //        int hash1 = getHash(l, r);
  94. //        if (used[hash1]) continue;
  95. //        used[hash1] = 1;
  96. //        cout << hash1 << '\n';
  97. //        cout << l  << " " << r<< '\n';
  98. //        cout << s.substr(l, r - l + 1) << '\n';
  99. //
  100. //        ans ++;
  101. //    }
  102. //
  103. //    cout << ans << '\n';
  104. }
  105.  
  106. signed main() {
  107.     #define name "baitap"
  108.     if (ifstream(name".inp")) {
  109.         freopen(name".inp", "r", stdin);
  110.         freopen(name".out", "w", stdout);
  111.     }
  112.  
  113.     ios_base::sync_with_stdio(0);
  114.     cin.tie(0);
  115.     cout.tie(0);
  116.  
  117.     solve();
  118. }
  119.  
Success #stdin #stdout 0.01s 5652KB
comments (?)
stdin 
6
()()()
stdout 
694655176
3 8
()()()
615950837
5 10
()()()
https://ideone.com/rqzrjQ
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!