제출 #1326725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326725		SSKMF	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	109 ms	17056 KiB

palindromic

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

const int mod_1(1000000007) , mod_2(998244353);
const int baza_1(31) , baza_2(29);

int putere[1000001][2] , prefix[1000001][2];
char sir[1000001];

inline pair <int , int> Query (const int stanga , const int dreapta)
{
    return make_pair(
        (prefix[dreapta][0] - 1LL * prefix[stanga - 1][0] * putere[dreapta - stanga + 1][0] % mod_1 + mod_1) % mod_1 ,
        (prefix[dreapta][1] - 1LL * prefix[stanga - 1][1] * putere[dreapta - stanga + 1][1] % mod_2 + mod_2) % mod_2
    );
}

inline void Solve ()
{
    cin >> sir;

    const int lungime = (int)strlen(sir);
    for (int indice = 1 ; indice <= lungime ; indice++) {
        prefix[indice][0] = (1LL * prefix[indice - 1][0] * baza_1 + (sir[indice - 1] - 'a')) % mod_1;
        prefix[indice][1] = (1LL * prefix[indice - 1][1] * baza_2 + (sir[indice - 1] - 'a')) % mod_2;
    }

    int stanga = 1 , dreapta = lungime , maxim = 0;
    while (stanga < dreapta)
    {
        int candidat = 0;
        while (stanga + candidat < dreapta - candidat && Query(stanga , stanga + candidat) != Query(dreapta - candidat , dreapta))
            { candidat++; }

        if (stanga + candidat >= dreapta - candidat)
            { break; }

        maxim += 2;
        stanga += candidat + 1;
        dreapta -= candidat + 1;
    }

    maxim += (stanga <= dreapta ? 1 : 0);

    cout << maxim << '\n';
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    putere[0][0] = putere[0][1] = 1;
    for (int exponent = 1 ; exponent <= 1000000 ; exponent++) {
        putere[exponent][0] = 1LL * putere[exponent - 1][0] * baza_1 % mod_1;
        putere[exponent][1] = 1LL * putere[exponent - 1][1] * baza_2 % mod_2;
    }

    int numar_teste;
    cin >> numar_teste;
    while (numar_teste--)
        { Solve(); }
    
    return 0;
}

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