Submission #44683

#	Time	Username	Problem	Language	Result	Execution time	Memory
44683		bogdan10bos	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	184 ms	42368 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<char, char> pcc;
typedef long long LL;

const int base = 31;

int N;
int dp[1000005];
char s[1000005];
LL pw[1000005], hsh[1000005];
vector<int> mp[35][35];

int get_hash(int st, int dr)
{
    return hsh[dr] - hsh[st - 1] * pw[dr - st + 1];
}

void solve_test()
{
    scanf("%s", s + 1);
    N = strlen(s + 1);
    for(int i = 1; i <= N; i++)
        hsh[i] = (1LL * hsh[i - 1] * base) + s[i] - 'a' + 1;
    int ans = 1;

    for(int i = 0; i < 26; i++)
        for(int j = 0; j < 26; j++)
            mp[i][j].clear();

    for(int st = 1, dr = N; st < dr; st++, dr--)
    {
        dp[st] = 0;
        for(auto pos: mp[s[dr] - 'a'][s[st] - 'a'])
        {
            int lgt = st - pos + 1;
            if(dp[pos - 1] > 0 && get_hash(pos, st) == get_hash(dr, dr + lgt - 1))
                dp[st] = max(dp[st], dp[pos - 1] + 2);
        }
        if(get_hash(1, st) == get_hash(dr, N))
            dp[st] = max(dp[st], 2);
        if(s[st] == s[dr] && dp[st - 1])
            dp[st] = max(dp[st], dp[st - 1] + 2);
        ans = max(ans, dp[st] + (st + 1 < dr ? 1 : 0));
        if(dp[st - 1] != 0)
        {
            mp[ s[st] - 'a' ][ s[dr] - 'a' ].clear();
            mp[s[st] - 'a'][ s[dr] - 'a'].push_back(st);
        }
    }

    printf("%d\n", ans);
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    pw[0] = 1;
    int N = 1e6;
    for(int i = 1; i <= N; i++)
        pw[i] = 1LL * pw[i - 1] * base;

    int T;
    scanf("%d\n", &T);
    for(int t = 1; t <= T; t++)
        solve_test();

    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve_test()':
palindromic.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s + 1);
     ~~~~~^~~~~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &T);
     ~~~~~^~~~~~~~~~~~

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