oj.uz

Submission #20397

# Submission time Handle Problem Language Result Execution time Memory
20397 2017-02-10T18:59:50 Z admin Palindromes (APIO14_palindrome) C++14
100 / 100
 839 ms 103952 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_occurence (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_occurence((i - t) / 2, (i + t) / 2));
            ++t;
        }
        --t;
    }
      
    printf("%lld", res);
      
    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:131:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", S+1); N = strlen(S+1);
                     ^

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 103952 KB Output is correct
2 Correct 3 ms 103952 KB Output is correct
3 Correct 6 ms 103952 KB Output is correct
4 Correct 6 ms 103952 KB Output is correct
5 Correct 9 ms 103952 KB Output is correct
6 Correct 6 ms 103952 KB Output is correct
7 Correct 6 ms 103952 KB Output is correct
8 Correct 9 ms 103952 KB Output is correct
9 Correct 13 ms 103952 KB Output is correct
10 Correct 6 ms 103952 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 103952 KB Output is correct
2 Correct 63 ms 103952 KB Output is correct
3 Correct 56 ms 103952 KB Output is correct
4 Correct 73 ms 103952 KB Output is correct
5 Correct 119 ms 103952 KB Output is correct
6 Correct 129 ms 103952 KB Output is correct
7 Correct 79 ms 103952 KB Output is correct
8 Correct 166 ms 103952 KB Output is correct
9 Correct 146 ms 103952 KB Output is correct
10 Correct 126 ms 103952 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 103952 KB Output is correct
2 Correct 213 ms 103952 KB Output is correct
3 Correct 179 ms 103952 KB Output is correct
4 Correct 176 ms 103952 KB Output is correct
5 Correct 719 ms 103952 KB Output is correct
6 Correct 326 ms 103952 KB Output is correct
7 Correct 303 ms 103952 KB Output is correct
8 Correct 839 ms 103952 KB Output is correct
9 Correct 809 ms 103952 KB Output is correct
10 Correct 659 ms 103952 KB Output is correct
11 Correct 206 ms 103952 KB Output is correct
12 Correct 679 ms 103952 KB Output is correct