제출 #1142552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142552		liangjeremy	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	100 ms	19792 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=0; 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--;
        }
        if(start<=end)ans++;
        cout<<ans;
        if(t)cout<<'\n';
    }
}

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