Submission #634921

#	Time	Username	Problem	Language	Result	Execution time	Memory
634921		Son	Palindromes (APIO14_palindrome)	C++14	100 / 100	754 ms	80736 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define mp make_pair
#define fi first
#define se second

string s;
char inp[300005];
int n;

int mo = 1e9 + 7;
int base = 16290047;
int base2 = 9999991;
int mo2 = 999999937;
int p_pow[300000 * 2 + 10];
int i_pow[300000 * 2 + 10];
int pfx[300000 * 2 + 10];
int p_pow2[300000 * 2 + 10];
int i_pow2[300000 * 2 + 10];
int pfx2[300000 * 2 + 10];
map < pair < int , int > , int > occ;
map < pair < int , int > , pair < int , int > > dp[300000* 2+ 10];


int expo(int a, int b){
    if ( b == 0 ) return 1;
    int half = expo(a,b/2);
    half = ( 1LL * half * half ) % mo;
    if ( b & 1 ) half = (1LL * half * a ) % mo;
    return half;
}

int expo2(int a, int b){
    if ( b == 0 ) return 1;
    int half = expo2(a,b/2);
    half = ( 1LL * half * half ) % mo2;
    if ( b & 1 ) half = (1LL * half * a ) % mo2;
    return half;
}

int h( int l, int r ){
    int ans = pfx[r] - pfx[l];
    if ( ans < 0 ) ans += mo;
    ans = ( ans * 1LL * i_pow[l] ) % mo;
    return ans;
}

int h2( int l, int r ){
    int ans = pfx2[r] - pfx2[l];
    if ( ans < 0 ) ans += mo2;
    ans = ( ans * 1LL * i_pow2[l] ) % mo2;
    return ans;
}

vector < int > manacher_odd(string s){
    vector < int > p(s.size(), 0);
    int l = 1, r = 1;
    for ( int i = 1; i <= s.size()-2; i++ ){
        p[i] = max(0, min(r-i, p[l + (r-i)]) );
        while ( s[i-p[i]] == s[i+p[i]] ){
            p[i]++;
        } 
        if ( i + p[i] > r ){
            l = i - p[i];
            r = i + p[i];
        }
    }
    return p;
}

LL solve1(){
    s = inp;
    s = "$" + s + "^";
    vector < int > p = manacher_odd(s);

    int N = s.size() - 2;

    for ( int i = 0; i < s.size(); i++ ){
        pfx[i] = (s[i] * 1LL * p_pow[i]) % mo;
        if ( i ) pfx[i] += pfx[i-1];
        if ( pfx[i] >= mo ) pfx[i] -= mo;

        pfx2[i] = (s[i] * 1LL * p_pow2[i]) % mo2;
        if ( i ) pfx2[i] += pfx2[i-1];
        if ( pfx2[i] >= mo2 ) pfx2[i] -= mo2;
    }

    // p[i] * 2 - 1
    LL ans = 0;
    for ( int i = 1; i <= N; i++ ){
        int l = i - p[i], r = i + p[i];
        auto it = make_pair(h(l,r-1),h2(l,r-1)); 
        if ( occ.find(it) == occ.end() ) dp[p[i]][it] = mp(l,r-1);
        ++occ[it];
    }

    for ( int i = s.size(); i >= 1; i-- ){
        for ( auto it : dp[i] ){
            auto ff = it.fi, ss = it.se;
            ans = max( ans, occ[ff] * 1LL * (i * 2 - 1));

            if ( ss.fi + 1 < ss.se - 1 ){
                auto enc = mp(h(ss.fi+1,ss.se-1), h2(ss.fi+1,ss.se-1));
                if ( occ.find(enc) == occ.end() ) dp[i-1][enc] = mp(ss.fi+1,ss.se-1);
                occ[enc] += occ[ff];
            }
        }
    }
    return ans;
}

LL solve2(){
    s = "$";
    for ( int i = 0; i < n; i++ ){
        s += "#";
        s += inp[i];
    }
    s += "#^";
    vector < int > p = manacher_odd(s);

    int N = s.size()-2;

    for ( int i = 0; i < s.size(); i++ ){
        pfx[i] = (s[i] * 1LL * p_pow[i]) % mo;
        if ( i ) pfx[i] += pfx[i-1];
        if ( pfx[i] >= mo ) pfx[i] -= mo;

        pfx2[i] = (s[i] * 1LL * p_pow2[i]) % mo2;
        if ( i ) pfx2[i] += pfx2[i-1];
        if ( pfx2[i] >= mo2 ) pfx2[i] -= mo2;
    }

    LL ans = 0;
    for ( int i = 1; i <= N; i++ ){
        if ( s[i] == '#' ){
            int l = i - p[i], r = i + p[i];
            auto it = make_pair(h(l,r-1),h2(l,r-1));
            if ( occ.find(it) == occ.end() ) dp[p[i]][it] = mp(l,r-1);
            ++occ[it];
        }
    }

    for ( int i = s.size(); i > 1; i-- ){
        for ( auto it : dp[i] ){
            auto ff = it.fi, ss = it.se;
            ans = max( ans, occ[ff] * 1LL * (i-1));

            if ( ss.fi + 2 < ss.se - 2 ){
                auto enc = mp(h(ss.fi+2,ss.se-2), h2(ss.fi+2,ss.se-2));
                if ( occ.find(enc) == occ.end() ) dp[i-2][enc] = mp(ss.fi+2,ss.se-2);
                occ[enc] += occ[ff];
            }
        }
    }

    return ans;
}

int main(){

    scanf("%s",&inp);
    n = strlen(inp);
    
    int p = 1;
    for ( int i = 0; i <= (n + 3) * 2; i++ ){
        p_pow[i] = p;
        p = (p * 1LL * base) % mo;
    }
    int inv = expo(base,mo-2);
    int ip = 1;
    for ( int i = 0; i <= (n+3) * 2 ; i++ ){
        i_pow[i] = ip;
        ip = (1LL * ip * inv) % mo;
    }

    p = 1;
    for ( int i = 0; i <= (n + 3) * 2; i++ ){
        p_pow2[i] = p;
        p = (p * 1LL * base2) % mo2;
    }
    inv = expo2(base2,mo2-2);
    ip = 1;
    for ( int i = 0; i <= (n+3) * 2 ; i++ ){
        i_pow2[i] = ip;
        ip = (1LL * ip * inv) % mo2;
    }

    LL ans1 = solve1();
    occ.clear();
    for ( int i = 0; i <= (n+3) * 2; i++ ){
        dp[i].clear();
    }
    LL ans2 = solve2();
    if ( ans1 > ans2 ) printf("%lld\n",ans1);
    else printf("%lld\n",ans2);
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'std::vector<int> manacher_odd(std::string)':
palindrome.cpp:59:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for ( int i = 1; i <= s.size()-2; i++ ){
      |                      ~~^~~~~~~~~~~~~
palindrome.cpp: In function 'long long int solve1()':
palindrome.cpp:79:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for ( int i = 0; i < s.size(); i++ ){
      |                      ~~^~~~~~~~~~
palindrome.cpp: In function 'long long int solve2()':
palindrome.cpp:124:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for ( int i = 0; i < s.size(); i++ ){
      |                      ~~^~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:162:13: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
  162 |     scanf("%s",&inp);
      |            ~^  ~~~~
      |             |  |
      |             |  char (*)[300005]
      |             char*
palindrome.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |     scanf("%s",&inp);
      |     ~~~~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27