Submission #819721

#	Time	Username	Problem	Language	Result	Execution time	Memory
819721		isaachew	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	4590 ms	27176 KiB

palindromic

#include <bits/stdc++.h>

/*
 Use hashing
 
 AAAAAAA  AAAAAAA
 BBBB        BBBB
 ABCABCA  ABCABCA
 -> A BC A BC A (rotations)
 
 
 ABCDEABCDEABC -> ABC DE ABC DE ABC, original is not solution
 
 Greedy works
 
 
 
 */

int n,t;
int hashbase;
int hashmod=1000000007;
long long binexp(int a,int b,int mod=hashmod){
    b=(b%(mod-1)+(mod-1))%(mod-1);
    long long e=a;
    long long s=1;
    while(b){
        if(b&1)s*=e;
        s%=mod;
        e=e*e%mod;
        b>>=1;
    }
    return s;
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::mt19937 rgen(std::chrono::steady_clock().now().time_since_epoch().count());
    std::cin>>t;
    for(;t--;){
        hashbase=std::uniform_int_distribution(100000000,1000000006)(rgen);
        std::string s;
        std::cin>>s;
        n=s.size();
        std::vector<long long> hashes(1);
        long long chash=0;
        for(int i=0;i<n;i++){
            chash+=s[i]*binexp(hashbase,i,hashmod);
            chash%=hashmod;
            hashes.push_back(chash);
        }
        int progress=0;
        int last=0;
        int total=1;
        for(int i=1;i*2<=n;i++){
            long long hash1=(hashes[i]-hashes[progress]+hashmod)%hashmod*binexp(hashbase,(n-i)-progress,hashmod)%hashmod;
            long long hash2=(hashes[n-progress]-hashes[n-i]+hashmod)%hashmod;
            //std::cout<<hash1<<' '<<hash2<<'\n';
            if(hash1==hash2){
                //std::cout<<i-progress<<'\n';
                progress=i;
                total+=2;
                if(i*2==n)total--;//no substr in between
            }
        }
        std::cout<<total<<'\n';
    }
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:53:13: warning: unused variable 'last' [-Wunused-variable]
   53 |         int last=0;
      |             ^~~~

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