Submission #13053

#	Time	Username	Problem	Language	Result	Execution time	Memory
13053		tncks0121	Palindromes (APIO14_palindrome)	C++14	100 / 100	762 ms	103920 KiB

palindrome

#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 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27