oj.uz

Submission #682953

# Submission time Handle Problem Language Result Execution time Memory
682953 2023-01-17T10:40:24 Z 79brue Palindromes (APIO14_palindrome) C++17
100 / 100
 545 ms 38736 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
char str[400002];
ll ans;

void input();
void init();
void dnc();

int main(){
    input();
    init();
    dnc();
    printf("%lld", ans);
}

void input(){
//    n=300000;
//    for(int i=1; i<=n; i++) str[i] = 'a';
    scanf("%s", str+1);
    n = strlen(str+1);
    if(n==1){
        printf("1");
        exit(0);
    }
}

int sa[400005], pos[400005], lcp[400005];
int d;

bool cmp(int i, int j){
    if(pos[i] != pos[j]) return pos[i] < pos[j];
    i += d;
    j += d;
    return (i <= n && j <= n) ? (pos[i] < pos[j]) : (i > j);
}

int temp[600005] = {0};
void constructSA(){
    for(int i=1; i<=n; i++){
        sa[i] = i;
        pos[i] = str[i];
    }
    for(d=1; ; d*=2){
        sort(sa+1, sa+n+1, cmp);
        memset(temp, 0, sizeof(temp));
        for(int i=0; i<=n; i++) temp[i] = 1;
        for(int i=1; i<n; i++)
            temp[i+1] = temp[i] + cmp(sa[i], sa[i+1]);
        for(int i=1; i<=n; i++)
            pos[sa[i]] = temp[i];
        if(temp[n] == n) break;
    }
}

void constructLCP(){
    for(int i=1, k=0; i<=n; i++, k=max(k-1, 0)){
        if(pos[i] == n) continue;

        for(int j=sa[pos[i]+1]; str[i+k]==str[j+k]; k++);
        lcp[pos[i]] = k;
    }
}

int pal[400005];

void manacher(){
    char arr[700005] = {0};
    for(int i=1; i<=n; i++) arr[i*2-1] = arr[i*2+1] = '#', arr[i*2] = str[i];
    arr[0] = 'S', arr[n*2+2] = 'T';
    int maxVal = -1, maxIdx = -1;
    for(int i=1; i<=n*2+1; i++){
        if(maxVal < i) pal[i] = 0;
        else pal[i] = min(pal[maxIdx*2-i], maxVal-i);
        while(arr[i-pal[i]-1] == arr[i+pal[i]+1]) pal[i]++;
        if(i + pal[i] > maxVal) maxVal = i+pal[i], maxIdx = i;
    }

    /// 한 번 나오는 케이스 처리
    for(int i=1; i<=n*2+1; i++){
        if(i%2==1) ans = max(ans, ll(pal[i]+1)/2*2);
        else       ans = max(ans, ll(pal[i])/2*2+1);
    }
}

pair<int, int> tree[1400002];

void init(int i, int l, int r){
    if(l==r){
        tree[i] = make_pair(lcp[l], l);
        return;
    }
    int m = (l+r)>>1;
    init(i*2, l, m);
    init(i*2+1, m+1, r);
    tree[i] = min(tree[i*2], tree[i*2+1]);
}

pair<int, int> query(int i, int l, int r, int s, int e){
    if(r<s || e<l) return make_pair(1000000000, -1);
    if(s<=l && r<=e) return tree[i];
    int m = (l+r)>>1;
    return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}

int tree2[2800002];

void init2(int i, int l, int r){
    if(l==r){
        tree2[i] = l-pal[l];
        return;
    }
    int m = (l+r)>>1;
    init2(i*2, l, m);
    init2(i*2+1, m+1, r);
    tree2[i] = min(tree2[i*2], tree2[i*2+1]);
}

int query2(int i, int l, int r, int s, int e, int v){
    if(r<s || e<l || tree2[i] > v) return 0;
    if(l==r) return l;
    int m = (l+r)>>1;
    int tmp = query2(i*2+1, m+1, r, s, e, v);
    if(tmp) return tmp;
    return query2(i*2, l, m, s, e, v);
}

void init(){
    constructSA();
    constructLCP();
    manacher();
    init(1, 1, n-1);
    init2(1, 1, n+n+1);

    #ifdef TEST
//    for(int i=1; i<=n; i++) printf("%d ", sa[i]); puts("");
//    for(int i=1; i<=n; i++) printf("%d ", lcp[i]); puts("");
//    for(int i=1; i<=n*2+1; i++) printf("%d ", pal[i]); puts("");

    for(int i=1; i<=n; i++) assert(sa[i] == n+1-i);
    for(int i=1; i<n; i++) assert(lcp[i] == i);
    #endif // TEST
}

void dnc(int l, int r){
    if(l>r) return;
    pair<int, int> p = query(1, 1, n-1, l, r);
    dnc(l, p.second-1);
    dnc(p.second+1, r);

    /// 현재 상황 처리하기
    int s = sa[l];
    int e = s + p.first - 1;
    int tmp = query2(1, 1, n+n+1, s+s, s+e, s+s);
    if(!tmp) return;
    ans = max(ans, ll(tmp-(s+s)+1) * ll(r-l+2));
}

void dnc(){
    return dnc(1, n-1);
}

Compilation message

palindrome.cpp: In function 'void input()':
palindrome.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%s", str+1);
      |     ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3284 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 2 ms 3284 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 1 ms 3284 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 3 ms 3284 KB Output is correct
15 Correct 2 ms 3284 KB Output is correct
16 Correct 2 ms 3284 KB Output is correct
17 Correct 2 ms 3284 KB Output is correct
18 Correct 2 ms 3332 KB Output is correct
19 Correct 2 ms 3284 KB Output is correct
20 Correct 2 ms 3284 KB Output is correct
21 Correct 2 ms 3284 KB Output is correct
22 Correct 2 ms 3284 KB Output is correct
23 Correct 2 ms 3284 KB Output is correct
24 Correct 2 ms 3284 KB Output is correct
25 Correct 2 ms 3284 KB Output is correct
26 Correct 2 ms 3284 KB Output is correct
27 Correct 2 ms 3284 KB Output is correct
28 Correct 2 ms 3284 KB Output is correct
29 Correct 2 ms 3284 KB Output is correct
30 Correct 2 ms 3284 KB Output is correct
31 Correct 2 ms 3284 KB Output is correct
32 Correct 2 ms 3284 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4056 KB Output is correct
2 Correct 12 ms 4044 KB Output is correct
3 Correct 12 ms 4044 KB Output is correct
4 Correct 13 ms 4044 KB Output is correct
5 Correct 16 ms 4052 KB Output is correct
6 Correct 12 ms 4056 KB Output is correct
7 Correct 12 ms 4052 KB Output is correct
8 Correct 8 ms 4044 KB Output is correct
9 Correct 8 ms 4052 KB Output is correct
10 Correct 12 ms 3980 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 11084 KB Output is correct
2 Correct 124 ms 10064 KB Output is correct
3 Correct 130 ms 13520 KB Output is correct
4 Correct 130 ms 11724 KB Output is correct
5 Correct 140 ms 9436 KB Output is correct
6 Correct 145 ms 9420 KB Output is correct
7 Correct 123 ms 9652 KB Output is correct
8 Correct 71 ms 9432 KB Output is correct
9 Correct 143 ms 9776 KB Output is correct
10 Correct 135 ms 9420 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 31408 KB Output is correct
2 Correct 412 ms 26708 KB Output is correct
3 Correct 441 ms 38736 KB Output is correct
4 Correct 397 ms 29796 KB Output is correct
5 Correct 545 ms 25428 KB Output is correct
6 Correct 435 ms 27984 KB Output is correct
7 Correct 493 ms 26376 KB Output is correct
8 Correct 244 ms 25484 KB Output is correct
9 Correct 265 ms 25432 KB Output is correct
10 Correct 534 ms 25428 KB Output is correct
11 Correct 507 ms 27084 KB Output is correct
12 Correct 521 ms 25932 KB Output is correct