Submission #340465

#	Time	Username	Problem	Language	Result	Execution time	Memory
340465		blue	Palindromic Partitions (CEOI17_palindromic)	C++11	100 / 100	487 ms	27828 KiB

palindromic

#include <iostream>
#include <string>
using namespace std;

//a^p-1 = 1 mod p
//a^p-2 = 1/a mod p

long long p[1000001];
long long mod = 1e9 + 7;

long long prefhash[1000001];

long long pow(long long base, long long exp)
{
    if(exp == 0) return 1;
    if(exp % 2) return (pow(base, exp-1) * base) % mod;
    long long temp = pow(base, exp/2);
    return (temp * temp) % mod;
}

long long gethash(long long a, long long b)
{
    return (mod + prefhash[b] - (prefhash[a-1]*p[b-(a-1)]) % mod) % mod;
}

void run()
{
    string S;
    cin >> S;
    long long n = S.length();
    S = " " + S;

    // cout << S.substr(4, 4) << '\n';

    prefhash[0] = 0;
    for(long long i = 1; i <= n; i++) prefhash[i] = (p[1] * prefhash[i-1]  +  (S[i] - 'a' + 1)) % mod;

    long long res = 0;
    long long j = 1;
    for(long long i = 1; 1; i++)
    {
         // cout << "i = " << i << '\n';
         // cout << j << ' ' << i << ' ' << n-i+1 << ' ' << n-j+1 << '\n';
         // cout << S.substr(j, i-j+1) << ' ' << S.substr(n-i+1, (n-j+1) - (n-i+1) + 1) << '\n';
         // cout << gethash(j, i) << ' ' << gethash(n-i+1, n-j+1) << '\n';
        if(gethash(j, i) == gethash(n-i+1, n-j+1))
        {
            // cout << "temp2 " << j << ' ' << i << ' ' << n-i+1 << ' ' << n-j+1 << '\n';
            if(i == n-j+1)
            {
                res += 1;
                break;
            }
            else
            {
                res += 2;

                if(2*i == n) break;
            }
            j = i+1;
        }
        // cout << j << '\n';
        // cout << "temp " << i << ' ' << j << '\n';
    }
    cout << res << '\n';
}

int main()
{
    p[0] = 1;
    for(long long i = 1; i <= 1000000; i++) p[i] = (p[i-1] * 347) % mod;

    long long t;
    cin >> t;
    for(long long i = 1; i <= t; i++) run();
}

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