Submission #338031

#	Time	Username	Problem	Language	Result	Execution time	Memory
338031		rrrr10000	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	443 ms	26080 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<PP> vpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(v) v.begin(),v.end()
#define dupli(v) {sort(all(v));v.erase(unique(all(v)),v.end());}
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>void out(T a){cout<<a<<endl;}
template<class T>void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T>void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T>void outvp(T v){for(auto a:v)cout<<'('<<a.fi<<','<<a.se<<')';cout<<endl;}
template<class T>void outvv(T v){for(auto x:v)outv(x);}
template<class T>void outvvp(T v){for(auto x:v)outvp(x);}
const ll inf=1001001001001001001;
const int mod=1000000007;
int main(){
    ll t;cin>>t;
    rep(tt,t){
        ll ans=1;
        string s;cin>>s;
        vi fac(s.size()+1);
        vi mp(s.size()+1);
        mp[0]=1;
        rep(i,s.size())mp[i+1]=mp[i]*31%mod;
        rep(i,s.size())fac[i+1]=(fac[i]*31+(s[i]-'a'))%mod;
        ll l=0,r=s.size()-1,k=1;
        while(l<r){
            bool same=true;
            ll a=((fac[l+1]-fac[l-k+1]*mp[k])%mod+mod)%mod;
            ll b=((fac[r+k]-fac[r]*mp[k])%mod+mod)%mod;
            if(a==b){
                ans+=2;k=0;
            }
            l++;r--;k++;
        }
        if(k==1&&s.size()%2==0)ans--;
        out(ans);
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:45:18: warning: unused variable 'same' [-Wunused-variable]
   45 |             bool same=true;
      |                  ^~~~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40