Submission #318024

#	Time	Username	Problem	Language	Result	Execution time	Memory
318024		parsabahrami	Palindromic Partitions (CEOI17_palindromic)	C++17	15 / 100	2 ms	1152 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=1e5+10,LN=30,SQ=550,M=1e9+10;
const ll INF=1e16;
const int MOD=1000000007 /*998244353*/;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pair<pll,ll>, null_type,less<pair<pll,ll>>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll t,b=737,m=1000696969,p[N];
int main(){
    fast_io;
    p[0]=1;
    for(ll i=1; i<N; i++) p[i]=p[i-1]*b%m;
    cin >> t;
    while(t--){
        string s;
        ll n;
        cin >> s;
        n=s.size();
        ll l=0,r=n-1,ans=1,x=0,h1=0,h2=0;
        while(r-l>1){
            h1=(h1*b+s[l]-'a'+1)%m;
            h2+=p[x]*(s[r]-'a'+1);
            h2%=m;
            x++;
            if(h1==h2) ans+=2,h1=0,h2=0,x=0;
            l++;
            r--;
        }
        if(r>l){
            h1=(h1*b+s[l]-'a'+1)%m;
            h2+=p[x]*(s[r]-'a'+1);
            if(h1==h2) ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

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