oj.uz

Submission #634921

# Submission time Handle Problem Language Result Execution time Memory
634921 2022-08-25T08:59:27 Z Son Palindromes (APIO14_palindrome) C++14
100 / 100
 754 ms 80736 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Correct 13 ms 28500 KB Output is correct
3 Correct 13 ms 28524 KB Output is correct
4 Correct 14 ms 28492 KB Output is correct
5 Correct 13 ms 28484 KB Output is correct
6 Correct 13 ms 28536 KB Output is correct
7 Correct 15 ms 28500 KB Output is correct
8 Correct 13 ms 28464 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 13 ms 28432 KB Output is correct
11 Correct 13 ms 28472 KB Output is correct
12 Correct 13 ms 28496 KB Output is correct
13 Correct 13 ms 28500 KB Output is correct
14 Correct 14 ms 28488 KB Output is correct
15 Correct 13 ms 28520 KB Output is correct
16 Correct 13 ms 28468 KB Output is correct
17 Correct 16 ms 28500 KB Output is correct
18 Correct 13 ms 28536 KB Output is correct
19 Correct 17 ms 28500 KB Output is correct
20 Correct 14 ms 28500 KB Output is correct
21 Correct 13 ms 28500 KB Output is correct
22 Correct 14 ms 28500 KB Output is correct
23 Correct 13 ms 28516 KB Output is correct
24 Correct 13 ms 28500 KB Output is correct
25 Correct 13 ms 28492 KB Output is correct
26 Correct 13 ms 28436 KB Output is correct
27 Correct 13 ms 28500 KB Output is correct
28 Correct 14 ms 28548 KB Output is correct
29 Correct 14 ms 28464 KB Output is correct
30 Correct 17 ms 28464 KB Output is correct
31 Correct 15 ms 28444 KB Output is correct
32 Correct 15 ms 28540 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28696 KB Output is correct
2 Correct 14 ms 28608 KB Output is correct
3 Correct 14 ms 28620 KB Output is correct
4 Correct 14 ms 28628 KB Output is correct
5 Correct 14 ms 28620 KB Output is correct
6 Correct 14 ms 28616 KB Output is correct
7 Correct 14 ms 28628 KB Output is correct
8 Correct 15 ms 28648 KB Output is correct
9 Correct 14 ms 28648 KB Output is correct
10 Correct 15 ms 28576 KB Output is correct
11 Correct 14 ms 28500 KB Output is correct
12 Correct 15 ms 28576 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30224 KB Output is correct
2 Correct 24 ms 30160 KB Output is correct
3 Correct 31 ms 29768 KB Output is correct
4 Correct 25 ms 29700 KB Output is correct
5 Correct 22 ms 30292 KB Output is correct
6 Correct 22 ms 30160 KB Output is correct
7 Correct 24 ms 30292 KB Output is correct
8 Correct 16 ms 29100 KB Output is correct
9 Correct 17 ms 29152 KB Output is correct
10 Correct 21 ms 29920 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 45676 KB Output is correct
2 Correct 193 ms 45564 KB Output is correct
3 Correct 169 ms 40840 KB Output is correct
4 Correct 192 ms 40844 KB Output is correct
5 Correct 149 ms 45620 KB Output is correct
6 Correct 113 ms 42132 KB Output is correct
7 Correct 144 ms 41268 KB Output is correct
8 Correct 42 ms 34600 KB Output is correct
9 Correct 69 ms 35852 KB Output is correct
10 Correct 131 ms 44956 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 80460 KB Output is correct
2 Correct 716 ms 79840 KB Output is correct
3 Correct 690 ms 65436 KB Output is correct
4 Correct 754 ms 65380 KB Output is correct
5 Correct 496 ms 79848 KB Output is correct
6 Correct 576 ms 71340 KB Output is correct
7 Correct 587 ms 65636 KB Output is correct
8 Correct 104 ms 46768 KB Output is correct
9 Correct 110 ms 46704 KB Output is correct
10 Correct 411 ms 76708 KB Output is correct
11 Correct 556 ms 80736 KB Output is correct
12 Correct 140 ms 47840 KB Output is correct