oj.uz

Submission #982706

# Submission time Handle Problem Language Result Execution time Memory
982706 2024-05-14T16:25:05 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 278 ms 55008 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define ff first
#define ss second
using namespace std;
const int mod = 1e9 + 7;
const int p1 = 97;
const int p2 = 107;
const int binv = 268041239;
const int binv2 = 224299067;
const int maxn = 1e6;
vector<int> pows(maxn+7,1);
vector<int> invs(maxn+7,1);
vector<int> pows2(maxn+7,1);
vector<int> invs2(maxn+7,1);
void init()
{
    for (int i = 1; i < maxn; i++)
        pows[i] = pows[i-1]*p1%mod;
    for (int i = 1; i < maxn; i++)
        invs[i] = invs[i-1]*binv%mod;
        
    for (int i = 1; i < maxn; i++)
        pows2[i] = pows2[i-1]*p2%mod;
    for (int i = 1; i < maxn; i++)
        invs2[i] = invs2[i-1]*binv2%mod;
    
}

void solve()
{
    
    string s;
    cin >> s;
    int n = s.length();
    vector<int> dp(n/2+2,0);
    int back = n-1;
    vector<int> hash(n);
    hash[0] = s[0]*pows[0]%mod;
    for (int i = 1; i < n; i++)
    {
        hash[i] = hash[i-1] + (s[i]*pows[i]%mod);
        hash[i] %= mod;
    }
    vector<int> hash2(n);
    hash2[0] = s[0]*pows2[0]%mod;
    for (int i = 1; i < n; i++)
    {
        hash2[i] = hash2[i-1] + (s[i]*pows2[i]%mod);
        hash2[i] %= mod;
    }
    auto mile = [&](int i,int j)
    {
        pii base = {hash[j],hash2[j]};
        if (i > 0)
        {
            base.ff-=hash[i-1]-2*mod;
            base.ss-=hash2[i-1]-2*mod;
            base.ff%=mod;
            base.ss%=mod;
            base.ff*=invs[i];
            base.ss*=invs2[i];
            base.ff%=mod;
            base.ss%=mod;
        }
        return ((pii)base);
        
    };
    int lst = 0;
    for (int i = 0; i < n/2+1; i++)
    {
        if (i >= back)
            break;
        
            //cout << s.substr(j,i-j+1) << ' ' << s.substr(back,i-j+1) << " i: " << i << " j: " << j << '\n';
            pii alpha = mile(lst,i);
            pii sigma = mile(back,back+(i-lst));
            if (alpha == sigma)
            {
                if (lst==0)
                    dp[i] = max(dp[i],2ll);
                else if (dp[lst-1] > 0)
                    dp[i] = max(dp[i],dp[lst-1]+2);
                lst = i+1;
            }
        
        back--;
    }
    int ans = 1;
    if (n%2)
    {
        for (int i = 0; i < n/2+1; i++)
        {
            ans = max(ans,dp[i]+1);   
        }
    }
    else
    {
        for (int i = 0; i < n/2-1; i++)
        {
            ans = max(ans,dp[i]+1);
        }
        ans = max(ans,dp[n/2-1]);
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    init();
    while(t--)
    {
       solve();
    }
    
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31764 KB Output is correct
2 Correct 32 ms 31580 KB Output is correct
3 Correct 34 ms 31760 KB Output is correct
4 Correct 34 ms 31576 KB Output is correct
5 Correct 35 ms 31580 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31764 KB Output is correct
2 Correct 32 ms 31580 KB Output is correct
3 Correct 34 ms 31760 KB Output is correct
4 Correct 34 ms 31576 KB Output is correct
5 Correct 35 ms 31580 KB Output is correct
6 Correct 34 ms 31580 KB Output is correct
7 Correct 35 ms 31576 KB Output is correct
8 Correct 35 ms 31580 KB Output is correct
9 Correct 37 ms 31580 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31764 KB Output is correct
2 Correct 32 ms 31580 KB Output is correct
3 Correct 34 ms 31760 KB Output is correct
4 Correct 34 ms 31576 KB Output is correct
5 Correct 35 ms 31580 KB Output is correct
6 Correct 34 ms 31580 KB Output is correct
7 Correct 35 ms 31576 KB Output is correct
8 Correct 35 ms 31580 KB Output is correct
9 Correct 37 ms 31580 KB Output is correct
10 Correct 36 ms 31912 KB Output is correct
11 Correct 37 ms 31928 KB Output is correct
12 Correct 37 ms 31960 KB Output is correct
13 Correct 36 ms 31916 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31764 KB Output is correct
2 Correct 32 ms 31580 KB Output is correct
3 Correct 34 ms 31760 KB Output is correct
4 Correct 34 ms 31576 KB Output is correct
5 Correct 35 ms 31580 KB Output is correct
6 Correct 34 ms 31580 KB Output is correct
7 Correct 35 ms 31576 KB Output is correct
8 Correct 35 ms 31580 KB Output is correct
9 Correct 37 ms 31580 KB Output is correct
10 Correct 36 ms 31912 KB Output is correct
11 Correct 37 ms 31928 KB Output is correct
12 Correct 37 ms 31960 KB Output is correct
13 Correct 36 ms 31916 KB Output is correct
14 Correct 278 ms 55008 KB Output is correct
15 Correct 156 ms 54704 KB Output is correct
16 Correct 261 ms 54540 KB Output is correct
17 Correct 158 ms 43700 KB Output is correct