제출 #1011529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011529		NValchanov	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	92 ms	26924 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;
const ll HASH = 31;

string s;
int n;
ll h[MAXN];
ll pw[MAXN];

void read()
{
    cin >> s;
    n = s.size();
}

void fill_hash()
{
    h[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        h[i] = (h[i - 1] * HASH + (s[i - 1] - 'a' + 1)) % MOD;
    }
}

void precompute()
{
    pw[0] = 1;
    for(int i = 1; i < MAXN; i++)
    {
        pw[i] = (pw[i - 1] * HASH) % MOD;
    }
}

ll get_hash(int left, int right)
{
    return (h[right + 1] - h[left] * pw[right - left + 1] % MOD + MOD) % MOD;
}

bool compare(int left1, int right1, int left2, int right2)
{
    return get_hash(left1, right1) == get_hash(left2, right2);
}

void solve()
{
    fill_hash();

    int left = 0;
    int right = n - 1;
    int ans = 0;

    while(left <= right)
    {

        if(left == right)
        {
            ans++;
            break;
        }

        int ptr1 = left;
        int ptr2 = right;

        while(ptr1 < ptr2 && !compare(left, ptr1, ptr2, right))
        {
            ptr1++;
            ptr2--;
        }

        if(ptr1 < ptr2)
        {
            ans += 2;
        }
        else
        {
            ans++;
            break;
        }

        left = ptr1 + 1;
        right = ptr2 - 1;
    }

    cout << ans << endl;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll t;
    cin >> t;

    precompute();

    while(t--)
    {
        read();
        solve();
    }

    return 0;
}

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