oj.uz

Submission #752807

# Submission time Handle Problem Language Result Execution time Memory
752807 2023-06-04T01:18:32 Z Username4132 Palindromes (APIO14_palindrome) C++14
100 / 100
 790 ms 59140 KB 
#include<iostream>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define F first
#define S second

struct hsh{
    int a, b;
    hsh(int A=0, int B=0) : a(A), b(B) {}
};

bool operator<(hsh x, hsh y){
    return x.a==y.a? x.b<y.b : x.a<y.a;
}

const int MOD1=1000000007, MOD2=1000000009, MAXN=600010;
const hsh base = hsh(124523, 3465354);
int n;
ll ans;
map<hsh, int> id;

hsh operator+(hsh x, hsh y){
    int a=(x.a+y.a)%MOD1, b=(x.b+y.b)%MOD2;
    return hsh(a, b);
}

hsh operator-(hsh x, hsh y){
    int a=(x.a-y.a+MOD1)%MOD1, b=(x.b-y.b+MOD2)%MOD2;
    return hsh(a, b);
}

hsh operator*(hsh x, hsh y){
    int a=(((ll)x.a)*y.a)%MOD1, b=(((ll)x.b)*y.b)%MOD2;
    return hsh(a, b);
}

string aux, str;
hsh arr[MAXN], pot[MAXN];
int l=1, r=1, cur, len[MAXN], val[MAXN], par[MAXN], cnt[MAXN];

hsh calc(int le, int ri){
    return arr[ri]-(arr[le]*pot[ri-le]);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> aux;
    str.resize(2*aux.size() + 1);
    forn(i, aux.size()) str[2*i+1]=aux[i];
    forn(i, aux.size()-1) str[2*i+2]='{';
    str.front()='$', str.back()='^';
    n = str.size();
    pot[0]=hsh(1, 1);
    forn(i, n) arr[i+1]=arr[i]*base+hsh(str[i]-'a'+1, str[i]-'a'+1);
    forn(i, n) pot[i+1]=pot[i]*base;
    forsn(i, 1, n-1){
        int pr=-1;
        if(i<r){
            len[i]=min(r-i, len[l+r-i]);
            pr=id[calc(i-len[i]+1, i+len[i])];
        }
        while(str[i+len[i]]==str[i-len[i]]){
            char ch=str[i+len[i]];
            ++len[i];
            hsh nw=calc(i-len[i]+1, i+len[i]);
            auto itr=id.find(nw);
            if(itr==id.end()){
                id[nw]=cur;
                par[cur]=pr;
                if(ch!='{') val[cur]=len[i];
                pr=cur++;
            }
            else pr=itr->S;
        }
        if(r<i+len[i]) r=i+len[i], l=i-len[i];
        cnt[pr]++;
    }
    dforn(i, cur){
        if(par[i]!=-1) cnt[par[i]]+=cnt[i];
        ans=max(ans, ((ll)val[i])*cnt[i]);
    }
    cout << ans << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9656 KB Output is correct
8 Correct 5 ms 9688 KB Output is correct
9 Correct 5 ms 9692 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 5 ms 9752 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 4 ms 9684 KB Output is correct
23 Correct 4 ms 9684 KB Output is correct
24 Correct 4 ms 9684 KB Output is correct
25 Correct 4 ms 9684 KB Output is correct
26 Correct 5 ms 9748 KB Output is correct
27 Correct 4 ms 9700 KB Output is correct
28 Correct 5 ms 9704 KB Output is correct
29 Correct 5 ms 9684 KB Output is correct
30 Correct 4 ms 9672 KB Output is correct
31 Correct 5 ms 9684 KB Output is correct
32 Correct 5 ms 9700 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9904 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9808 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11236 KB Output is correct
2 Correct 14 ms 11272 KB Output is correct
3 Correct 14 ms 11220 KB Output is correct
4 Correct 13 ms 11304 KB Output is correct
5 Correct 14 ms 11268 KB Output is correct
6 Correct 15 ms 11224 KB Output is correct
7 Correct 13 ms 11248 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 11 ms 10804 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 25580 KB Output is correct
2 Correct 163 ms 25588 KB Output is correct
3 Correct 182 ms 25636 KB Output is correct
4 Correct 154 ms 25640 KB Output is correct
5 Correct 128 ms 25676 KB Output is correct
6 Correct 105 ms 21560 KB Output is correct
7 Correct 131 ms 23364 KB Output is correct
8 Correct 24 ms 10880 KB Output is correct
9 Correct 44 ms 14212 KB Output is correct
10 Correct 111 ms 23436 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 57740 KB Output is correct
2 Correct 707 ms 59140 KB Output is correct
3 Correct 788 ms 57976 KB Output is correct
4 Correct 790 ms 57824 KB Output is correct
5 Correct 576 ms 57752 KB Output is correct
6 Correct 591 ms 52864 KB Output is correct
7 Correct 626 ms 50320 KB Output is correct
8 Correct 69 ms 13400 KB Output is correct
9 Correct 69 ms 13436 KB Output is correct
10 Correct 496 ms 49784 KB Output is correct
11 Correct 644 ms 57936 KB Output is correct
12 Correct 90 ms 17524 KB Output is correct