fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
  5.  
  6. template<typename... Args>
  7. void logger(string vars, Args &&... values) {
  8.     cout << vars << " = ";
  9.     string delim = "";
  10.     (..., (cout << delim << values, delim = ", "));
  11.     cout << '\n';
  12. }
  13.  
  14. #define int long long
  15. #define ll long long
  16. #define ld long double
  17. #define nl "\n"
  18. #define aw3dni_ink_tet3aleg ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  19. #define ff first
  20. #define ss second
  21.  
  22. void FILES() {
  23.     aw3dni_ink_tet3aleg
  24. }
  25.  
  26. ll OO = 0x3f3f3f3f3f3f3f3f, oo = 0x3f3f3f3f, MOD = 1e9 + 7; //1e9 + 7 ,,998244353
  27. // وَقُلْ رَبِّ زِدْنِي عِلْمًا
  28. long long randomLongLong(long long a, long long b) {
  29.     random_device rd;
  30.     mt19937_64 rng(rd());
  31.     uniform_int_distribution<long long> dist(a, b);
  32.     return dist(rng);
  33. }
  34.  
  35. void solve() {
  36.     string s;
  37.     cin >> s;
  38.     ll n = s.size();
  39.     const int N = 1e6 + 10, base = randomLongLong(1123, 1000000007), mod = 1e9 + 9;
  40.     vector<ll> power(N);
  41.     power[0] = 1;
  42.     for (ll i = 1; i < N; i++) {
  43.         power[i] = (power[i - 1] * base) % mod;
  44.     }
  45.     ll cur = 0;
  46.     vector<ll> pre;
  47.     for (ll i = 0; i < n; i++) {
  48.         cur = (cur * base + s[i]) % mod;
  49.         pre.push_back(cur);
  50.     }
  51.     map<ll,ll> mp;
  52.     int l = 0, r = n - 1;
  53.     for (ll i = 0; i < n - 1; i++) {
  54.         cur = ((cur - (s[l] * power[n - 2]) % mod) + mod) % mod;
  55.         cur = (cur * base + s[l]) % mod;
  56.         mp[l] = cur;
  57.         l++;
  58.     }
  59.     int ans =  -1,momkn = OO;
  60.     for (auto it : mp) {
  61.         cout <<it.ff<<" "<<it.ss<<nl;
  62.         if (it.ss < momkn) {
  63.             momkn = it.ss; ans = it.ff;
  64.         }
  65.     }
  66.     cout <<ans;
  67. }
  68.  
  69. signed main() {
  70.     FILES();
  71. #ifndef ONLINE_JUDGE
  72.     freopen("input.txt", "r", stdin);
  73.     freopen("output.txt", "w", stdout);
  74. #endif
  75.     int T = 1, t = 1;
  76.     // cin >> T;
  77.     while (T--) {
  78.         solve();
  79.         t++;
  80.         // vid++;
  81.         if (T >= 1) {
  82.             cout << endl;
  83.         }
  84.     }
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 10932KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/rSfDTQ
language:
C++ (gcc 8.3)
created:
8 hours 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!