Submission #592844

#	Time	Username	Problem	Language	Result	Execution time	Memory
592844		VasLemmy	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	13 ms	8072 KiB

palindromic

/// slava sovet·skomu soyuzu
#include <bits/stdc++.h>
using namespace std;
using db = long double;
//#define int long long

#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back

const pii mod = {1000000007,123456791};
const int maxN = 1000005;
const int base = 31;

int n;
string s;
pii prehash[maxN];
pii powr[maxN];

void Prepare()
{
    powr[0] = {1,1};
    for(int i = 1;i < maxN;i++)
    {
        powr[i].fi = powr[i-1].fi * base % mod.fi;
        powr[i].se = powr[i-1].se * base % mod.se;
    }
}

pii Gethash(int l,int r)
{
    pii res;
    res.fi = (prehash[r].fi - prehash[l-1].fi * powr[r-l+1].fi % mod.fi) % mod.fi;
    if(res.fi < 0) res.fi += mod.fi;
    res.se = (prehash[r].se - prehash[l-1].se * powr[r-l+1].se % mod.se) % mod.se;
    if(res.se < 0) res.se += mod.se;
    return res;
}

void read()
{
    cin >> s;
    n = s.size();
    s.insert(0,"?");
    for(int i = 1;i <= n;i++)
    {
        prehash[i].fi = (prehash[i-1].fi * base % mod.fi + (s[i] - 'a' + 1)) % mod.fi;
        prehash[i].se = (prehash[i-1].se * base % mod.se + (s[i] - 'a' + 1)) % mod.se;
    }
    int res = 0;
    int L = 1;
    int R = n;
    int len = 1;
    while(true)
    {
        int l1,r1,l2,r2;
        l1 = L;
        r1 = l1 + len - 1;
        l2 = R - len + 1;
        r2 = R;
        if(l2 <= r1) {cout << res + 1 <<'\n';return;}
        if(Gethash(l1,r1) == Gethash(l2,r2))
        {
            res += 2;
            L = r1 + 1;
            R = l2 - 1;
            len = 1;
        }
        else
        {
            len++;
        }
    }

}

void sol()
{

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.inp","r",stdin);
    Prepare();
    int tests;
    cin >> tests;
    //ests = 1;
    while (tests--)
    {
        read();
        sol();
    }
    return 0;
}

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