Submission #318150

#TimeUsernameProblemLanguageResultExecution timeMemory
318150RohamIzadidoostPalindromic Partitions (CEOI17_palindromic)C++14
0 / 100
10014 ms17572 KiB
#pragma GCC optimize("O2") #include<bits/stdc++.h> typedef long long ll ; #define pll pair<ll , ll > #define X first #define Y second #define mp make_pair #define pii pair<int , int> #define vec vector #define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define pb push_back using namespace std; const int maxn = 1000*1000+5 ; const ll inf = 9223372036854775807 ; const ll mod = 1000696969 ; const ll mod2 = 1e9 + 7 ; const ll H = 1777013 ; string s ; ll pt[maxn] , h[maxn] , L , R , sz , n , l, r , mid , b , ans ; ll hsh(int l , int r){ if(l == 0 ) return h[r] ; return ( h[r] - h[l-1] * pt[r-l+1] % mod + mod ) % mod ; } bool check(int x){ return( hsh(L , L + x - 1) == hsh(R - x + 1 , R) ) ; } int Main() { ans = 0 ; cin>>s ; n = s.size() ; h[0] = s[0] ; for(int i = 1 ; i < n ; i ++ ){ h[i] = h[i-1] * H % mod + s[i] ; h[i] %= mod ; } L= 0 , R = n - 1 ; while(n){ l = 0 , r = n/2 + 1 , b = 1 ; while(r-l>1){ mid = (l + r)/ 2 ; if(check(mid)) l = mid , b = 0 ; else r = mid ; } if(b){ n = 0 ; ans ++ ; }else{ L += l ; R -= l ; ans += 2 ; n -= 2 * l ; } } cout<<ans << endl ; } int main() { int t ; migmig; pt[0] = 1 ; for(int i = 1; i < maxn ; i ++ ) { pt[i] = pt[i-1] * H % mod ; } cin>> t ; while(t--) { Main() ; } }

Compilation message (stderr)

palindromic.cpp: In function 'int Main()':
palindromic.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...