답안 #47177 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47177	2018-04-28T14:15:48 Z	dongwon0427	회문 (APIO14_palindrome)	C++11	58 / 100	892 ms	37976 KB

palindrome

/*
god taekyu
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define MAX 300005
int n;
char A[MAX];

int SA[MAX], lcp[MAX];
int ord[MAX],x[MAX],cnt[MAX];
void init() {
    int m = 256;
    for(int i=0;i<n;i++) ord[i] = A[i];
    for(int i=0;i<n;i++) cnt[ord[i]]++;
    for(int i=1;i<=m;i++) cnt[i] += cnt[i-1];
    for(int i=n-1;i>=0;i--) SA[--cnt[ord[i]]] = i;
    for(int j=1;;j<<=1) {
        int p = 0;
        for(int i=n-j;i<n;i++) x[p++] = i;
        for(int i=0;i<n;i++) if(SA[i]>=j) x[p++] = SA[i]-j;
        for(int i=0;i<=m;i++) cnt[i] = 0;
        for(int i=0;i<n;i++) cnt[ord[i]]++;
        for(int i=1;i<=m;i++) cnt[i] += cnt[i-1];
        for(int i=n-1;i>=0;i--) SA[--cnt[ord[x[i]]]] = x[i];
        x[SA[0]] = 0;
        for(int i=1;i<n;i++) {
            x[SA[i]] = x[SA[i-1]];
            if(ord[SA[i]] == ord[SA[i-1]]) {
                if(SA[i]+j < n && SA[i-1]+j < n) {
                    if(ord[SA[i]+j] == ord[SA[i-1]+j]) continue;
                }
            }
            x[SA[i]]++;
        }
        for(int i=0;i<n;i++) ord[i] = x[i];
        m = ord[SA[n-1]];
        if(m == n-1) break;
    }
    int p = 0;
    for(int i=0;i<n;i++) {
        int j = ord[i];
        if(j == 0) {
            if(p != 0) p--;
            continue;
        }
        while(SA[j]+p<n && SA[j-1]+p<n && A[SA[j]+p] == A[SA[j-1]+p]) p++;
        lcp[j] = p;
        if(p!=0) p--;
    }

    //for(int i=0;i<n;i++) {
    //    for(int j=SA[i];j<n;j++) cout<<A[j];
    //    cout<<' '<<lcp[i]<<'\n';
    //}
}
char B[MAX*2];
int dp[MAX*2];
vector<pii> P;
void palin() {
    for(int i=0;i<n;i++) {
        B[2*i] = A[i];
        B[2*i+1] = '*';
    }
    int len = 2*n-1;
    //for(int i=0;i<len;i++) {
    //    cout<<B[i];
    //}
    //cout<<'\n';

    dp[0] = 0;
    int p=0, r=0;
    //cout<<B[0]<<'\n';
    P.push_back(pii(0,1));
    for(int i=1;i<len;i++) {
        if(i<=r) dp[i] = dp[2*p-i];
        else dp[i] = 0;
        while(i+dp[i]+1<len && i-dp[i]-1>=0 && B[i+dp[i]+1] == B[i-dp[i]-1]) {
            dp[i]++;
            if(r < i+dp[i]) {
                r = i+dp[i];
                p = i;
                //for(int j=i-dp[i];j<=dp[i]+i;j++) if(j%2==0) cout<<B[j];
                int st = (i-dp[i]+1)/2;
                int rad;
                if((i+dp[i])%2 == 0) rad = dp[i]+1;
                else rad =  dp[i];
                P.push_back(pii(st,rad));
                //cout<<'\n';
            }
        }
    }
}
int SP[MAX][20];
void spar() {
    for(int i=0;i<n;i++) SP[i][0] = lcp[i];
    int len = 1;
    for(int j=1;j<20;j++) {
        len*=2;
        for(int i=0;i<n-len+1;i++) {
            SP[i][j] = min(SP[i][j-1], SP[i+len/2][j-1]);
        }
    }

}
int query(int s,int e) {
    int len = e-s+1;
    int j = 1;
    int cnt = 0;
    while(j<=len) j*=2,cnt++;
    j/=2; cnt--;
    return min(SP[s][cnt] , SP[e-j+1][cnt]);
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>A;
    n = strlen(A);

    init();
    palin();


    spar();

    ll ret = 0;
    for(pii x : P) {
        int st = ord[x.first]+1, ed = n-1;
        int ans = st-1;
        while(st<=ed) {
            int mid = (st+ed)/2;
            if(query(ord[x.first]+1 , mid) >= x.second) {
                ans = max(ans , mid);
                st = mid+1;
            } else ed = mid-1;
        }

        int ans2 = ord[x.first]+1;
        st = 1, ed = ord[x.first];
        while(st<=ed) {
            int mid = (st+ed)/2;
            if(query(mid , ord[x.first]) >= x.second) {
                ans2 = min(ans2 , mid);
                ed = mid-1;
            } else st = mid+1;
        }
        //for(int i=x.first;i<x.first+x.second;i++) cout<<A[i];
        //cout<<' '<<(ll)(ans - ans2 + 2) * (ll)x.second<<'\n';
        ret = max(ret , (ll)(ans - ans2 + 2) * (ll)x.second);
    }
    cout<<ret;
    return 0;
}

/*
god taekyu
*/

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	544 KB	Output is correct
4	Correct	2 ms	544 KB	Output is correct
5	Correct	2 ms	544 KB	Output is correct
6	Correct	2 ms	692 KB	Output is correct
7	Correct	2 ms	700 KB	Output is correct
8	Correct	2 ms	700 KB	Output is correct
9	Correct	2 ms	700 KB	Output is correct
10	Correct	2 ms	700 KB	Output is correct
11	Correct	2 ms	700 KB	Output is correct
12	Correct	2 ms	700 KB	Output is correct
13	Correct	2 ms	760 KB	Output is correct
14	Correct	2 ms	760 KB	Output is correct
15	Correct	2 ms	760 KB	Output is correct
16	Correct	2 ms	760 KB	Output is correct
17	Correct	2 ms	760 KB	Output is correct
18	Correct	2 ms	760 KB	Output is correct
19	Correct	2 ms	760 KB	Output is correct
20	Correct	2 ms	760 KB	Output is correct
21	Correct	2 ms	760 KB	Output is correct
22	Correct	2 ms	760 KB	Output is correct
23	Correct	2 ms	760 KB	Output is correct
24	Correct	2 ms	760 KB	Output is correct
25	Correct	2 ms	760 KB	Output is correct
26	Correct	2 ms	760 KB	Output is correct
27	Correct	2 ms	760 KB	Output is correct
28	Correct	2 ms	760 KB	Output is correct
29	Correct	2 ms	760 KB	Output is correct
30	Correct	2 ms	760 KB	Output is correct
31	Correct	2 ms	760 KB	Output is correct
32	Correct	2 ms	760 KB	Output is correct

Subtask #2
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	764 KB	Output is correct
2	Incorrect	2 ms	764 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	2044 KB	Output is correct
2	Correct	8 ms	2044 KB	Output is correct
3	Correct	11 ms	2044 KB	Output is correct
4	Correct	8 ms	2044 KB	Output is correct
5	Correct	10 ms	2044 KB	Output is correct
6	Correct	10 ms	2044 KB	Output is correct
7	Correct	9 ms	2044 KB	Output is correct
8	Correct	9 ms	2044 KB	Output is correct
9	Correct	8 ms	2044 KB	Output is correct
10	Correct	10 ms	2044 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	13040 KB	Output is correct
2	Correct	87 ms	13040 KB	Output is correct
3	Correct	102 ms	13040 KB	Output is correct
4	Correct	95 ms	13040 KB	Output is correct
5	Correct	162 ms	13248 KB	Output is correct
6	Correct	186 ms	13248 KB	Output is correct
7	Correct	115 ms	13292 KB	Output is correct
8	Correct	53 ms	13292 KB	Output is correct
9	Correct	106 ms	13292 KB	Output is correct
10	Correct	134 ms	13292 KB	Output is correct

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	379 ms	37848 KB	Output is correct
2	Correct	371 ms	37848 KB	Output is correct
3	Correct	386 ms	37848 KB	Output is correct
4	Correct	310 ms	37848 KB	Output is correct
5	Correct	892 ms	37848 KB	Output is correct
6	Correct	403 ms	37848 KB	Output is correct
7	Correct	552 ms	37976 KB	Output is correct
8	Correct	189 ms	37976 KB	Output is correct
9	Correct	202 ms	37976 KB	Output is correct
10	Correct	881 ms	37976 KB	Output is correct
11	Correct	416 ms	37976 KB	Output is correct
12	Incorrect	352 ms	37976 KB	Output isn't correct

답안 #47177

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 26.0 / 26.0

Subtask #5 0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
26.0 / 26.0

Subtask #5
0 / 27.0