oj.uz

Submission #209733

# Submission time Handle Problem Language Result Execution time Memory
209733 2020-03-15T12:50:23 Z jhnah917 Palindromes (APIO14_palindrome) C++14
0 / 100
 1000 ms 38480 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pi;
const ll p1 = 917, mod1 = 524287;
const ll p2 = 179, mod2 = 993244853;
struct Hashing{
    vector<ll> ha, ba;
    ll p, mod;
    Hashing(){ }
    Hashing(string &s, ll p1, ll mod1) : p(p1), mod(mod1) {
        int n = s.size();
        ha.resize(n+1); ba.resize(n+1);
        ba[0] = 1, ba[1] = p;
        for(int i=n-1; i>=0; i--) ha[i] = (ha[i+1] * p + s[i]) % mod;
        for(int i=2; i<=n; i++) ba[i] = ba[i-1] * p % mod;
    }
    int substr(int l, int r){
        ll ret = ha[l] - ha[r+1] * ba[r-l+1];
        ret %= mod; ret += mod; ret %= mod;
        return ret;
    }
}h1, h2;

int n;
char inp[606060];
string s;
int pal[606060];

map<pi, ll> mp[mod1]; //{h2, len}

void manacher(){
    for(int i=n-1; i>=0; i--){
        inp[i << 1 | 1] = inp[i];
        inp[i << 1] = '#';
    }
    n <<= 1; inp[n++] = '#';
    s = string(inp);

    int r = -1, p = -1;
    for(int i=0; i<n; i++){
        pal[i] = (i <= r ? min(pal[p*2-i], r-i) : 0);
        while(i-pal[i]-1 >= 0 && i+pal[i]+1 < n && s[i-pal[i]-1] == s[i+pal[i]+1]) pal[i]++;
        if(i+pal[i] > r) r = i+pal[i], p = i;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> inp; s = string(inp); n = s.size();
    h1 = Hashing(s, p1, mod1);
    h2 = Hashing(s, p2, mod2);
    manacher();

    for(int i=0; i<n; i++){
        if(!pal[i]) continue;
        if(i & 1){
            for(int j=1; j<=pal[i]; j+=2){
                int s = i/2 - j/2;
                int e = i/2 + j/2;
                mp[h1.substr(s, e)][pi(h2.substr(s, e), e-s+1)]++;
            }
        }else{
            for(int j=2; j<=pal[i]; j+=2){
                int s = i - j/2; s /= 2;
                int e = i + j/2; e /= 2;
                mp[h1.substr(s, e)][pi(h2.substr(s, e), e-s+1)]++;
            }
        }
    }

    ll ans = 0;
    for(int i=0; i<mod1; i++){
        for(auto j : mp[i]){
            //cout << j.second << " " << j.first.second << "\n";
            ans = max(ans, j.second * j.first.second);
        }
    }
    cout << ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24952 KB Output is correct
2 Correct 22 ms 24956 KB Output is correct
3 Correct 22 ms 24952 KB Output is correct
4 Correct 22 ms 24952 KB Output is correct
5 Correct 22 ms 24952 KB Output is correct
6 Correct 22 ms 24952 KB Output is correct
7 Correct 21 ms 24952 KB Output is correct
8 Correct 22 ms 24952 KB Output is correct
9 Correct 21 ms 24952 KB Output is correct
10 Incorrect 23 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 25080 KB Output is correct
2 Correct 28 ms 25080 KB Output is correct
3 Incorrect 44 ms 25080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 25976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1101 ms 29944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1101 ms 38480 KB Time limit exceeded
2 Halted 0 ms 0 KB -