Submission #1248220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248220		minhanhphan555	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	178 ms	50796 KiB

palindromic

#include <bits/stdc++.h>
using namespace std ;

#define int long long
#define BIT(x , i) (((x) >> (i)) & 1)
#define MASK(i) (1ll << (i))
#define pb push_back
#define LOG 19
#define endl '\n'

template <class X , class Y>
    bool minimize(X& x , const Y& y) {
        if(x > y) {
            x = y ;
            return true ;
        }
        return false ;
    }

template <class X , class Y>
    bool maximize(X& x , const Y& y) {
        if(x < y) {
            x = y ;
            return true ;
        }
        return false ;
    }

const int MAXN = 1e6 + 2 ;
const int MOD1 = 1e9 + 5277 ;
const int MOD2 = 1e9 + 2277 ;
const int BASE = 256 ;
int hs[MAXN] , pw[MAXN] , inv[MAXN] , n , newHs[MAXN] , newPw[MAXN] , newInv[MAXN] ;
string s ;

int mul(int a , int b , int m) {
    return (a * b) % m ;
}

int binPow(int a , int b , int m) {
    if(b == 0) return 1 ;
    int x = binPow(a , b / 2 , m) ;
    if(b & 1) return mul(x , x , m) * a % m ;
    else return mul(x , x , m) ;
}

void createHash(void) {
    cin >> s ;
    n = (int) s.size() ;
    s = "." + s ;
    pw[0] = newPw[0] = 1 ;
    for(int i = 1 ; i <= n ; ++i) pw[i] = mul(pw[i - 1] , BASE , MOD1) , newPw[i] = mul(newPw[i - 1] , BASE , MOD2) ;
    for(int i = 1 ; i <= n ; ++i) {
        hs[i] = (hs[i - 1] + mul(s[i] , pw[i - 1] , MOD1)) % MOD1 ;
        newHs[i] = (newHs[i - 1] + mul(s[i] , newPw[i - 1] , MOD2)) % MOD2 ;
    }
    inv[n] = binPow(pw[n] , MOD1 - 2 , MOD1) ;
    newInv[n] = binPow(newPw[n] , MOD2 - 2 , MOD2) ;
    for(int i = n ; i >= 1 ; --i) inv[i - 1] = mul(inv[i] , BASE , MOD1) , newInv[i - 1] = mul(newInv[i] , BASE , MOD2) ;
}

int getHash(int l , int r) {
    pair <int , int> tmp = {hs[r] - hs[l - 1] , newHs[r] - newHs[l - 1]};
    if(tmp.first < 0) tmp.first += MOD1 ;
    if(tmp.second < 0) tmp.second += MOD2 ;
    return mul(tmp.first , inv[l - 1] , MOD1) ;
}

void process(void) {
    int l = 1 , r = n , cnt = 0 ;
    while(l <= r) {
        bool found = false ;
        for(int k = 1 ; l + k - 1 < r - k + 1 ; ++k) {
            if(getHash(l , l + k - 1) == getHash(r - k + 1 , r)) {
                found = true ;
                l += k , r -= k , cnt += 2 ;
                break ;
            }
        }
        if(!found) {
            ++cnt ;
            break ;
        }
    }
    cout << cnt << endl ;
}

int32_t main(void) {
    ios_base :: sync_with_stdio(false) ;
    cout.tie(nullptr) ;
    cin.tie(nullptr) ;
    int numTest ; cin >> numTest ;
    while(numTest--) {
        createHash() ;
        process() ;
    }
    return 0 ;
}

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