oj.uz

Submission #13053

# Submission time Handle Problem Language Result Execution time Memory
13053 2015-01-27T15:41:42 Z tncks0121 Palindromes (APIO14_palindrome) C++14
100 / 100
 762 ms 103920 KB 
#define _CRT_SECURE_NO_WARNINGS
  
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
  
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
  
const int N_ = 300005, lgN_ = 20;
char S[N_]; int N;
  
int SA[N_], CP[lgN_][N_+N_];
int start[N_], lnk[N_], temp[N_];
  
int RMQ[lgN_][N_+N_];
int lg2[N_];
  
void build_suffix_array() {
    for(int i = 1; i <= N; i++) SA[i] = i, CP[0][i] = S[i] - 'a' + 1;
    for(int k = 0; k+1 < lgN_; k++) {
        for(int c = 1; c >= 0; c--) {
            for(int i = N; i > 0; i--) {
                int x = SA[i] + (c<<k); if(x > N) x = 0;
                int v = CP[k][x];
                lnk[i] = start[v]; start[v] = i;
                temp[i] = SA[i];
            }
            for(int i = 0, p = 0; i <= N || i <= 26; i++) {
                for(int j = start[i]; j > 0; j = lnk[j]) SA[++p] = temp[j];
                start[i] = -1;
            }
        }
          
        int *now = CP[k], *nxt = CP[k+1];
        nxt[SA[1]] = 1;
        for(int i = 2, v = 1; i <= N; i++) {
            int ap = now[SA[i-1]], bp = now[SA[i]];
            int an = (SA[i-1] + (1<<k) <= N) ? now[SA[i-1] + (1<<k)] : 0;
            int bn = (SA[i] + (1<<k) <= N) ? now[SA[i] + (1<<k)] : 0;
            if(ap < bp || (ap == bp && an < bn)) ++v;
            nxt[SA[i]] = v;
        }
    }
}
  
int lcp_logn (int x, int y) {
    int r = 0;
    if(x == y) return N-x+1;
    for(int k = lgN_; --k >= 0; ) {
        if(CP[k][x+r] == CP[k][y+r]) r += 1<<k;
    }
    return r;
}
  
void build_lcp () {
    for(int i = 1; i < N; i++) RMQ[0][i] = lcp_logn(SA[i], SA[i+1]);
    for(int i = 1, v = 0; i <= N; i++) v += (i>>v), lg2[i] = v-1;
  
    for(int k = 1; k < lgN_; k++) {
        for(int i = 1; i + (1<<k) - 1 <= N - 1; i++) RMQ[k][i] = min(RMQ[k-1][i], RMQ[k-1][i + (1<<(k-1))]);
    }
}
  
int lcp_constant (int x, int y) {
    if(x == y) return N-x+1;
  
    x = CP[lgN_-1][x]; y = CP[lgN_-1][y];
    if(x > y) swap(x, y);
    int l = y-x; int k = lg2[l];
  
    //printf("%d %d: %d: %d\n", x, y, l, 1<<k);
    return min(RMQ[k][x], RMQ[k][y-(1<<k)]);
}
  
int num_occurance (int x, int y) { // S[x..|S|]∞˙¿? √÷¿?∞???¡??Œª? ±?¿?∞° y-x+1 ¿?ª?¿?∏? ?
    int w = CP[lgN_-1][x];
    int low, high, ret1 = 0, ret2 = 0;
  
    for(low = 1, high = w-1; low <= high; ) {
        int mid = (low + high) >> 1;
        if(lcp_constant(x, SA[mid]) >= y-x+1) {
            ret1 = w - mid;
            high = mid - 1;
        }else {
            low = mid + 1;
        }
    }
  
    for(low = w+1, high = N; low <= high; ) {
        int mid = (low + high) >> 1;
        if(lcp_constant(x, SA[mid]) >= y-x+1) {
            ret2 = mid - w;
            low = mid + 1;
        }else {
            high = mid - 1;
        }
    }
  
    return ret1 + ret2 + 1;
}
  
char T[N_+N_]; int TN;
  
int Table[N_+N_];
  
ll res;
  
int main() {
    scanf("%s", S+1); N = strlen(S+1);
  
    build_suffix_array();
    build_lcp();
  
    T[++TN] = '.';
    for(int i = 1; i <= N; i++) T[++TN] = S[i], T[++TN] = '.';
  
    int pr = -1, pm = -1;
    for(int i = 1; i <= TN; i++) {
        int &t = Table[i];
        if(i <= pr) t = min(Table[pm + pm - i], pr - i);
        while(i-t > 0 && i+t <= TN && T[i-t] == T[i+t]) {
            if(pr < i+t) pr = i+t, pm = i;
            if((i + t) % 2 == 0) res = max(res, (ll)(t + 1) * num_occurance((i - t) / 2, (i + t) / 2));
            ++t;
        }
        --t;
    }
  
    printf("%lld\n", res);
  
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 103920 KB Output is correct - answer is '1249925001'
2 Correct 79 ms 103920 KB Output is correct - answer is '396337935'
3 Correct 66 ms 103920 KB Output is correct - answer is '2500050000'
4 Correct 88 ms 103920 KB Output is correct - answer is '1016525689'
5 Correct 155 ms 103920 KB Output is correct - answer is '99645'
6 Correct 136 ms 103920 KB Output is correct - answer is '78569380'
7 Correct 86 ms 103920 KB Output is correct - answer is '82810000'
8 Correct 174 ms 103920 KB Output is correct - answer is '3989'
9 Correct 149 ms 103920 KB Output is correct - answer is '125529616'
10 Correct 152 ms 103920 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 103920 KB Output is correct - answer is '11250075000'
2 Correct 253 ms 103920 KB Output is correct - answer is '894243195'
3 Correct 232 ms 103920 KB Output is correct - answer is '22499400004'
4 Correct 241 ms 103920 KB Output is correct - answer is '2958163321'
5 Correct 723 ms 103920 KB Output is correct - answer is '298935'
6 Correct 361 ms 103920 KB Output is correct - answer is '1210831209'
7 Correct 375 ms 103920 KB Output is correct - answer is '303195156'
8 Correct 762 ms 103920 KB Output is correct - answer is '11804'
9 Correct 744 ms 103920 KB Output is correct - answer is '11813'
10 Correct 743 ms 103920 KB Output is correct - answer is '262144'
11 Correct 285 ms 103920 KB Output is correct - answer is '3750025000'
12 Correct 687 ms 103920 KB Output is correct - answer is '184796836'