Advertisement
YEZAELP

TOI13: Timer Switch

Dec 28th, 2020
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.60 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using lli = long long;
  6. const lli INF = 2e18;
  7. const lli PB = 98765431;
  8.  
  9. int main(){
  10.  
  11.     int n;
  12.     scanf("%d", &n);
  13.  
  14.     string str;
  15.     cin >> str;
  16.  
  17.     lli rem = 1, hsh = 0;
  18.     for(int i = 0; i < n; i ++){
  19.         if(i != 0) rem = rem * PB;
  20.         str[i] -= '0';
  21.         hsh = hsh * PB + str[i];
  22.     }
  23.  
  24.     lli cmp = hsh;
  25.  
  26.     for(int i = 0; i < n; i ++){
  27.         hsh = hsh - (rem * str[i]);
  28.         hsh = hsh * PB + str[i];
  29.         if(hsh == cmp){
  30.             printf("%d", i + 1);
  31.             return 0;
  32.         }
  33.     }
  34.  
  35. }
  36.  
Advertisement
RAW Paste Data Copied
Advertisement