Submission #1307185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307185		mhn_neek	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	7 ms	8248 KiB

palindromic

//In the name of God
#include<bits/stdc++.h>
/*
NNNNNNNN        NNNNNNNN                                       kkkkkkkk             iiii  
N:::::::N       N::::::N                                       k::::::k            i::::i 
N::::::::N      N::::::N                                       k::::::k             iiii  
N:::::::::N     N::::::N                                       k::::::k                   
N::::::::::N    N::::::N    eeeeeeeeeeee        eeeeeeeeeeee    k:::::k    kkkkkkkiiiiiii 
N:::::::::::N   N::::::N  ee::::::::::::ee    ee::::::::::::ee  k:::::k   k:::::k i:::::i 
N:::::::N::::N  N::::::N e::::::eeeee:::::ee e::::::eeeee:::::eek:::::k  k:::::k   i::::i 
N::::::N N::::N N::::::Ne::::::e     e:::::ee::::::e     e:::::ek:::::k k:::::k    i::::i 
N::::::N  N::::N:::::::Ne:::::::eeeee::::::ee:::::::eeeee::::::ek::::::k:::::k     i::::i 
N::::::N   N:::::::::::Ne:::::::::::::::::e e:::::::::::::::::e k:::::::::::k      i::::i 
N::::::N    N::::::::::Ne::::::eeeeeeeeeee  e::::::eeeeeeeeeee  k:::::::::::k      i::::i 
N::::::N     N:::::::::Ne:::::::e           e:::::::e           k::::::k:::::k     i::::i 
N::::::N      N::::::::Ne::::::::e          e::::::::e         k::::::k k:::::k   i::::::i
N::::::N       N:::::::N e::::::::eeeeeeee   e::::::::eeeeeeee k::::::k  k:::::k  i::::::i
N::::::N        N::::::N  ee:::::::::::::e    ee:::::::::::::e k::::::k   k:::::k i::::::i
NNNNNNNN         NNNNNNN    eeeeeeeeeeeeee      eeeeeeeeeeeeee kkkkkkkk    kkkkkkkiiiiiiii
*/
using namespace std;
typedef long long int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> piiii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=1e6+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define minheap priority_queue<pair<lli,pii>, std::vector<pair<lli,pii>>, std::greater<pair<lli,pii>>>
#define set_preci(x) cout << fixed << setprecision(x);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define BN(l,a) while(l){a.PB(l%2);l/=2;}
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
#define SZ(X) (lli)X.size()
lli tmp;
const lli M = 998244353;
const lli B = 73;
lli hsh[N];
string s;
lli n;
lli pw[N];

lli get(lli l,lli r){
    if(l == 0)return hsh[r];
    lli L = pw[r-l+1] * hsh[l-1] % M;
    lli res = hsh[r] - L + M;
    res = (res + M)%M;
    return res;
}

int main(){
    migmig;
    pw[0] = 1;
    FORS(i,N-1){
        pw[i] = B * pw[i-1];
        pw[i] %= M;
    }
    TEST{
        cin>>s;
        n = SZ(s);        
        hsh[0] = (s[0] - 'a');
        FORS(i,n-1){
            hsh[i] = (B * hsh[i-1])%M + (s[i] - 'a');
            hsh[i] %= M;
        }
        lli ans = 0;
        lli l = 0,r = n-1;
        FOR(i,n){
            if(i > r)break;
            if(l > r)break;
            lli k = i - l + 1;
            // if(i == 0){
            //     debug(get(l,i));
            //     debug(k);
            //     debug(get(r-k+1,r));
            // }
            if(get(l,i) == get(r-k+1,r)){
                l = i + 1,r-=k;
                ans += 2;
                ans -= (r < l);
            }


        }
        cout<<ans<<endl;
    }
    
}

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