Submission #634915

#	Time	Username	Problem	Language	Result	Execution time	Memory
634915		Son	Palindromes (APIO14_palindrome)	C++14	0 / 100	218 ms	26300 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define LL long long

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];


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;
    }

    map < pair < int , int > , int > occ;
    LL ans = 0;
    for ( int i = 1; i <= N; i++ ){
        int l = i - p[i], r = i + p[i];
        ans = max( ans, (++occ[make_pair(h(l,r-1),h2(l,r-1))]) * 1LL * (p[i] * 2 - 1) );
    }
    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;
    map < pair < int, int > , int > occ;
    for ( int i = 1; i <= N; i++ ){
        if ( s[i] == '#' ){
            int l = i - p[i], r = i + p[i];
            ans = max( ans, (++occ[make_pair(h(l,r-1),h2(l,r-1))]) * 1LL * (p[i] - 1));
        }
    }

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

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