oj.uz

Submission #982643

# Submission time Handle Problem Language Result Execution time Memory
982643 2024-05-14T14:40:13 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 53468 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);
        
    };
    for (int i = 0; i < n/2+1; i++)
    {
        if (i >= back)
            break;
        for(int j = 0; j <= i; j++)
        {
            //cout << s.substr(j,i-j+1) << ' ' << s.substr(back,i-j+1) << " i: " << i << " j: " << j << '\n';
            pii alpha = mile(j,i);
            pii sigma = mile(back,back+(i-j));
            if (alpha == sigma)
            {
                if (j==0)
                    dp[i] = max(dp[i],2ll);
                else if (dp[j-1] > 0)
                    dp[i] = max(dp[i],dp[j-1]+2);
            }
        }
        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 31 ms 32088 KB Output is correct
2 Correct 31 ms 31832 KB Output is correct
3 Correct 31 ms 31580 KB Output is correct
4 Correct 31 ms 31580 KB Output is correct
5 Correct 31 ms 31580 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32088 KB Output is correct
2 Correct 31 ms 31832 KB Output is correct
3 Correct 31 ms 31580 KB Output is correct
4 Correct 31 ms 31580 KB Output is correct
5 Correct 31 ms 31580 KB Output is correct
6 Correct 33 ms 31580 KB Output is correct
7 Correct 34 ms 31788 KB Output is correct
8 Correct 32 ms 31580 KB Output is correct
9 Correct 32 ms 31580 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32088 KB Output is correct
2 Correct 31 ms 31832 KB Output is correct
3 Correct 31 ms 31580 KB Output is correct
4 Correct 31 ms 31580 KB Output is correct
5 Correct 31 ms 31580 KB Output is correct
6 Correct 33 ms 31580 KB Output is correct
7 Correct 34 ms 31788 KB Output is correct
8 Correct 32 ms 31580 KB Output is correct
9 Correct 32 ms 31580 KB Output is correct
10 Correct 1216 ms 32160 KB Output is correct
11 Correct 537 ms 32004 KB Output is correct
12 Correct 937 ms 32136 KB Output is correct
13 Correct 676 ms 32024 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32088 KB Output is correct
2 Correct 31 ms 31832 KB Output is correct
3 Correct 31 ms 31580 KB Output is correct
4 Correct 31 ms 31580 KB Output is correct
5 Correct 31 ms 31580 KB Output is correct
6 Correct 33 ms 31580 KB Output is correct
7 Correct 34 ms 31788 KB Output is correct
8 Correct 32 ms 31580 KB Output is correct
9 Correct 32 ms 31580 KB Output is correct
10 Correct 1216 ms 32160 KB Output is correct
11 Correct 537 ms 32004 KB Output is correct
12 Correct 937 ms 32136 KB Output is correct
13 Correct 676 ms 32024 KB Output is correct
14 Execution timed out 10033 ms 53468 KB Time limit exceeded
15 Halted 0 ms 0 KB -