Submission #1142548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142548		liangjeremy	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	0 ms	320 KiB

palindromic

#include<bits/stdc++.h>
#include <iomanip>
#include<random>
using namespace std;
using db=double;
using ll=long long;
using sll=__int128;//super long long
using lb=long double;//lb is slow
//numbers for hashing: b(19260817),mod(998244353)
// freopen("fencedin.in", "r", stdin);
// freopen("fencedin.out", "w", stdout);

class HashString{
    private:
        vector<ll>phash;
        static vector<ll>pow;
        static const ll B=19260817;
        static const ll M=998244353;
    public:
        HashString(const string&s):phash(s.size()+1){
            while(pow.size()<=s.size()){
                pow.push_back(pow.back()*B%M);
            }
            phash[0]=0;
            for(int i=0; i<s.size(); i++){
                phash[i+1]=(phash[i]*B+s[i])%M;
            }
        }
        ll gethash(int end, int start){
            ll val=(phash[end+1]-phash[start]*pow[end-start+1])%M;
            return (val+M)%M;
        }
}; vector<ll>HashString::pow={1};

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll t; cin>>t;
    while(t--){
        string s; cin>>s; HashString hs(s); 
        ll ans=1; ll left=0; ll right=s.size()-1; ll start=0; ll end=s.size()-1;
        while(left<right){
            if(hs.gethash(left,start)==hs.gethash(end,right)){
                ans+=2; start=left+1; end=right-1;
            }
            left++; right--;
        }
        cout<<ans;
        if(t)cout<<'\n';
    }
}

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