Submission #751567

#TimeUsernameProblemLanguageResultExecution timeMemory
751567FidanPalindromic Partitions (CEOI17_palindromic)C++17
100 / 100
157 ms18132 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for(ll i=ll(a); i<ll(b); i++) #define repn(i, a, b) for(ll i=ll(b)-1; i>=ll(a); i--) #define be begin() #define en end() #define ff first #define ss second #define si size() const ll mod=(1e9)+9; void solve(){ string s; cin>>s; ll n=s.si; ll l=0, h=n-1; ll s1=0, s2=0; ll sum=0; map<char, ll> mp; rep(i, 0, 26){ mp[97+i]=i; } vector<ll> pw(n+10, 1); rep(i, 1, n+10){ pw[i]=(pw[i-1]*26)%mod; } ll x=0; while(l<h){ s1=(s1*26)%mod; s1=(s1+s[l])%mod; s2=(s2+(pw[x]*s[h])%mod)%mod; if(s1==s2){ x=-1; sum+=2; s1=0, s2=0; } x++; l++, h--; } if(s1>0 || s2>0) sum++; else if(l==h) sum++; cout<<sum<<'\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll t=1; cin>>t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...