Submission #915730

#	Time	Username	Problem	Language	Result	Execution time	Memory
915730		aykhn	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	224 ms	36252 KiB

palindromic

#include <bits/stdc++.h>

// author: aykhn

using namespace std;
typedef long long ll;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int mod = 1e9 + 7;
const int MXN = 1e6 + 1;
const int base = 12031;

int ph[MXN], p[MXN], invp[MXN];

int mult(int a, int b)
{
    return (a * b) % mod;
}

int add(int a, int b)
{
    return (a + b) % mod;
}

int pw(int a, int b, int c)
{
    a %= c;
    int res = 1;
    while (b)
    {
        if (b & 1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int get_hash(int l, int r)
{
    return mult(add(ph[r], mod - ph[l - 1]), invp[l]);
}

void _()
{
    string s;
    cin >> s;
    int n = s.length();
    s = "#" + s;
    ph[0] = 0;
    for (int i = 1; i <= n; i++) ph[i] = add(ph[i - 1], mult(p[i], s[i] - 'a'));
    int res = 0;
    int f = 1;
    int l = 1;
    int r = n;
    for (int i = 1; i <= n/2; i++)
    {
        if (get_hash(l, i) == get_hash(n - i + 1, r)) 
        {
            l = i + 1;
            r = n - i;
            res++;
        }
    }
    
    cout << res * 2 + (l <= r) << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    p[0] = 1;
    for (int i = 1; i < MXN; i++) p[i] = mult(p[i - 1], base);
    for (int i = 0; i < MXN; i++) invp[i] = pw(p[i], mod - 2, mod);
    int t = 1;
    cin >> t;
    for (int tt = 1; tt <= t; tt++)
    {
        _();
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'void _()':
palindromic.cpp:54:9: warning: unused variable 'f' [-Wunused-variable]
   54 |     int f = 1;
      |         ^

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