oj.uz

Submission #5525

# Submission time Handle Problem Language Result Execution time Memory
5525 2014-05-05T12:30:54 Z gs12117 Palindromes (APIO14_palindrome) C++
73 / 100
 1000 ms 54704 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#define N_ 300010
#define SZ 524288
using namespace std;
int D[N_ * 2], n, ord[20][N_], LCP[20][N_], C;
long long Res;
char p[N_], q[N_ * 2];
struct A{
    int a, b, num;
    bool operator <(const A &p)const{
        return a != p.a ? a<p.a : b<p.b;
    }
}w[N_];
void Do(int b, int e){
    int L = e - b + 1, t = ord[C][b], be = t, ed = t, i;
    for (i = C; i >= 0; i--){
        if (LCP[i][ed] >= L)ed += (1 << i);
    }
    for (i = C; i >= 0; i--){
        if (be >= (1<<i) && LCP[i][be - (1<<i)] >= L)be -= (1 << i);
    }
    Res = max(Res, (long long)(ed - be + 1)*L);
}
void DP(){
    int i, M = -1, mid, m;
    for (i = 0; p[i]; i++){
        q[i * 2] = p[i];
        q[i * 2 + 1] = '-';
    }
    m = n * 2 - 1;
    for (i = 0; i<m; i++){
        if (M >= i){
            if (D[mid * 2 - i] < M - i){
                D[i] = D[mid * 2 - i];
                continue;
            }
        }
        mid = i;
        while (M + 1 < m && M + 1 <= i * 2 && q[M + 1] == q[i * 2 - M - 1]){
            M++;
            if (M % 2 == 0){
                Do((i * 2 - M) / 2, M / 2);
            }
        }
        D[i] = M - i;
    }
}
void SA(){
    int i, K = 1, cnt;
    for (i = 0; p[i]; i++){
        w[i].a = p[i], w[i].b = 0, w[i].num = i;
    }
    n = i;
    while (1){
        sort(w, w + n);
        cnt = 0;
        for (i = 0; i<n; i++){
            if (!i || w[i].a != w[i - 1].a || w[i].b != w[i - 1].b)cnt++;
            ord[C][w[i].num] = cnt;
        }
        if (K >= n) break;
        for (i = 0; i<n; i++){
            w[i].a = ord[C][i];
            if (K + i >= n)w[i].b = 0;
            else w[i].b = ord[C][K + i];
            w[i].num = i;
        }
        K *= 2;
        C++;
    }
}
int Gap(int a, int b){
    int i, r = 0;
    for (i = C; i >= 0; i--){
        if (ord[i][a] == ord[i][b]){
            a += (1 << i);
            b += (1 << i);
            r += (1 << i);
        }
    }
    return r;
}
void PrePro(){
    int i, j;
    for (i = 0; i < n - 1; i++){
        LCP[0][i+1] = Gap(w[i].num, w[i + 1].num);
    }
    for (i = 0; i < C; i++){
        for (j = 1; j < n - (1 << i); j++){
            LCP[i + 1][j] = min(LCP[i][j], LCP[i][j + (1 << i)]);
        }
    }
}
int main()
{
    scanf("%s", p);
    SA();
    PrePro();
    DP();
    printf("%lld\n", Res);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 54704 KB Output is correct - answer is '7'
2 Correct 0 ms 54704 KB Output is correct - answer is '4'
3 Correct 0 ms 54704 KB Output is correct - answer is '9'
4 Correct 0 ms 54704 KB Output is correct - answer is '1'
5 Correct 0 ms 54704 KB Output is correct - answer is '1'
6 Correct 0 ms 54704 KB Output is correct - answer is '2'
7 Correct 0 ms 54704 KB Output is correct - answer is '3'
8 Correct 0 ms 54704 KB Output is correct - answer is '3'
9 Correct 0 ms 54704 KB Output is correct - answer is '15'
10 Correct 0 ms 54704 KB Output is correct - answer is '24'
11 Correct 0 ms 54704 KB Output is correct - answer is '10'
12 Correct 0 ms 54704 KB Output is correct - answer is '24'
13 Correct 0 ms 54704 KB Output is correct - answer is '25'
14 Correct 0 ms 54704 KB Output is correct - answer is '28'
15 Correct 0 ms 54704 KB Output is correct - answer is '2'
16 Correct 0 ms 54704 KB Output is correct - answer is '1'
17 Correct 0 ms 54704 KB Output is correct - answer is '15'
18 Correct 0 ms 54704 KB Output is correct - answer is '18'
19 Correct 0 ms 54704 KB Output is correct - answer is '1176'
20 Correct 0 ms 54704 KB Output is correct - answer is '1225'
21 Correct 0 ms 54704 KB Output is correct - answer is '136'
22 Correct 0 ms 54704 KB Output is correct - answer is '45'
23 Correct 0 ms 54704 KB Output is correct - answer is '2500'
24 Correct 0 ms 54704 KB Output is correct - answer is '380'
25 Correct 0 ms 54704 KB Output is correct - answer is '2304'
26 Correct 0 ms 54704 KB Output is correct - answer is '110'
27 Correct 0 ms 54704 KB Output is correct - answer is '93'
28 Correct 0 ms 54704 KB Output is correct - answer is '729'
29 Correct 0 ms 54704 KB Output is correct - answer is '132'
30 Correct 0 ms 54704 KB Output is correct - answer is '7'
31 Correct 0 ms 54704 KB Output is correct - answer is '8'
32 Correct 0 ms 54704 KB Output is correct - answer is '64'

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 54704 KB Output is correct - answer is '124251'
2 Correct 0 ms 54704 KB Output is correct - answer is '38226'
3 Correct 0 ms 54704 KB Output is correct - answer is '249500'
4 Correct 0 ms 54704 KB Output is correct - answer is '5778'
5 Correct 0 ms 54704 KB Output is correct - answer is '247506'
6 Correct 0 ms 54704 KB Output is correct - answer is '248004'
7 Correct 0 ms 54704 KB Output is correct - answer is '973'
8 Correct 0 ms 54704 KB Output is correct - answer is '123753'
9 Correct 0 ms 54704 KB Output is correct - answer is '2346'
10 Correct 0 ms 54704 KB Output is correct - answer is '53'
11 Correct 0 ms 54704 KB Output is correct - answer is '52'
12 Correct 0 ms 54704 KB Output is correct - answer is '976'

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 54704 KB Output is correct - answer is '12497500'
2 Correct 8 ms 54704 KB Output is correct - answer is '6481800'
3 Correct 8 ms 54704 KB Output is correct - answer is '25000000'
4 Correct 8 ms 54704 KB Output is correct - answer is '17816841'
5 Correct 12 ms 54704 KB Output is correct - answer is '9945'
6 Correct 12 ms 54704 KB Output is correct - answer is '504100'
7 Correct 8 ms 54704 KB Output is correct - answer is '1512930'
8 Correct 16 ms 54704 KB Output is correct - answer is '413'
9 Correct 16 ms 54704 KB Output is correct - answer is '428'
10 Correct 16 ms 54704 KB Output is correct - answer is '7232'

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 54704 KB Output is correct - answer is '1249925001'
2 Correct 184 ms 54704 KB Output is correct - answer is '396337935'
3 Correct 128 ms 54704 KB Output is correct - answer is '2500050000'
4 Correct 148 ms 54704 KB Output is correct - answer is '1016525689'
5 Correct 276 ms 54704 KB Output is correct - answer is '99645'
6 Correct 232 ms 54704 KB Output is correct - answer is '78569380'
7 Correct 172 ms 54704 KB Output is correct - answer is '82810000'
8 Correct 288 ms 54704 KB Output is correct - answer is '3989'
9 Correct 252 ms 54704 KB Output is correct - answer is '125529616'
10 Correct 268 ms 54704 KB Output is correct - answer is '66664'

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 54704 KB Output is correct - answer is '11250075000'
2 Correct 528 ms 54704 KB Output is correct - answer is '894243195'
3 Correct 472 ms 54704 KB Output is correct - answer is '22499400004'
4 Correct 452 ms 54704 KB Output is correct - answer is '2958163321'
5 Execution timed out 1000 ms 54704 KB Program timed out
6 Halted 0 ms 0 KB -