oj.uz

Submission #680627

# Submission time Handle Problem Language Result Execution time Memory
680627 2023-01-11T11:26:27 Z voriat Palindromes (APIO14_palindrome) C++14
100 / 100
 899 ms 53732 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 ", res);
     
    return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 708 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 680 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2092 KB Output is correct
2 Correct 8 ms 2092 KB Output is correct
3 Correct 7 ms 2132 KB Output is correct
4 Correct 8 ms 2104 KB Output is correct
5 Correct 10 ms 2092 KB Output is correct
6 Correct 8 ms 2132 KB Output is correct
7 Correct 8 ms 2132 KB Output is correct
8 Correct 10 ms 2148 KB Output is correct
9 Correct 10 ms 2132 KB Output is correct
10 Correct 9 ms 2068 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 17616 KB Output is correct
2 Correct 86 ms 17692 KB Output is correct
3 Correct 75 ms 17656 KB Output is correct
4 Correct 79 ms 17604 KB Output is correct
5 Correct 151 ms 17688 KB Output is correct
6 Correct 137 ms 17652 KB Output is correct
7 Correct 107 ms 17688 KB Output is correct
8 Correct 188 ms 17664 KB Output is correct
9 Correct 167 ms 17628 KB Output is correct
10 Correct 203 ms 17620 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 53636 KB Output is correct
2 Correct 246 ms 53612 KB Output is correct
3 Correct 214 ms 53648 KB Output is correct
4 Correct 218 ms 53560 KB Output is correct
5 Correct 699 ms 53604 KB Output is correct
6 Correct 431 ms 53548 KB Output is correct
7 Correct 363 ms 53532 KB Output is correct
8 Correct 764 ms 53708 KB Output is correct
9 Correct 899 ms 53672 KB Output is correct
10 Correct 855 ms 53616 KB Output is correct
11 Correct 246 ms 53732 KB Output is correct
12 Correct 741 ms 53552 KB Output is correct