oj.uz

Submission #340449

# Submission time Handle Problem Language Result Execution time Memory
340449 2020-12-27T16:04:06 Z blue Palindromic Partitions (CEOI17_palindromic) C++11
0 / 100
 23 ms 16364 KB 
#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;

    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 << j << ' ' << i << ' ' << n-i+1 << ' ' << n-j+1 << '\n';
         // cout << S.substr(j, i) << ' ' << S.substr(n-i+1, n-j+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;
            }
            j = i+1;
        }
        // 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -