Submission #1368516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368516		Newtonabc	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	213 ms	10676 KiB

palindromic

#include<bits/stdc++.h>
#define ll long long
const ll MOD=1e9+7;
const ll C=676767677;
using namespace std;
ll po(ll base,int p){
    ll ret=1,mul=base;
    while(p){
        if(p&1) ret=(ret*mul)%MOD;
        mul=(mul*mul)%MOD;
        p>>=1;
    }
    return ret;
}
int main(){
    int t; cin>>t;
    while(t--){
        string s; cin>>s;
        deque<ll> dq;
        int ans=0;
        for(auto c:s) dq.push_back((int)(c));
        ll l=0,r=0;
        int cnt=0;
        while(dq.size()>=2){
            if(cnt==0){
                l+=dq.front();
                dq.pop_front();
                r+=dq.back();
                dq.pop_back();
                cnt++;
                if(l==r){
                    l=r=0;
                    ans+=2;
                    cnt=0;
                }
                continue;
            }
            //use 1 from front and 1 from back
            r=((r*C)+(dq.back()))%MOD;
            dq.pop_back();
            l=(l+dq.front()*po(C,cnt))%MOD;
            dq.pop_front();
            cnt++;
            if(l==r){
                //equal
                l=r=0;
                ans+=2;
                cnt=0;
            }
        }
        if(!dq.empty() || (l!=0 && r!=0)) ans++;
        cout<<ans <<"\n";
    }
}

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