답안 #47178 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47178	2018-04-28T14:24:50 Z	dongwon0427	회문 (APIO14_palindrome)	C++11	58 / 100	1000 ms	38076 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-1) 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	484 KB	Output is correct
3	Correct	2 ms	560 KB	Output is correct
4	Correct	2 ms	636 KB	Output is correct
5	Correct	2 ms	692 KB	Output is correct
6	Correct	2 ms	692 KB	Output is correct
7	Correct	2 ms	772 KB	Output is correct
8	Correct	2 ms	772 KB	Output is correct
9	Correct	2 ms	772 KB	Output is correct
10	Correct	2 ms	772 KB	Output is correct
11	Correct	2 ms	772 KB	Output is correct
12	Correct	2 ms	772 KB	Output is correct
13	Correct	4 ms	772 KB	Output is correct
14	Correct	2 ms	772 KB	Output is correct
15	Correct	2 ms	772 KB	Output is correct
16	Correct	2 ms	772 KB	Output is correct
17	Correct	2 ms	772 KB	Output is correct
18	Correct	2 ms	772 KB	Output is correct
19	Correct	2 ms	772 KB	Output is correct
20	Correct	2 ms	772 KB	Output is correct
21	Correct	2 ms	772 KB	Output is correct
22	Correct	2 ms	772 KB	Output is correct
23	Correct	2 ms	772 KB	Output is correct
24	Correct	2 ms	772 KB	Output is correct
25	Correct	2 ms	772 KB	Output is correct
26	Correct	2 ms	772 KB	Output is correct
27	Correct	2 ms	772 KB	Output is correct
28	Correct	3 ms	772 KB	Output is correct
29	Correct	2 ms	772 KB	Output is correct
30	Correct	2 ms	772 KB	Output is correct
31	Correct	2 ms	772 KB	Output is correct
32	Correct	2 ms	772 KB	Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	107 ms	13040 KB	Output is correct
2	Correct	88 ms	13040 KB	Output is correct
3	Correct	99 ms	13040 KB	Output is correct
4	Correct	93 ms	13040 KB	Output is correct
5	Correct	188 ms	13164 KB	Output is correct
6	Correct	151 ms	13164 KB	Output is correct
7	Correct	120 ms	13164 KB	Output is correct
8	Correct	168 ms	13164 KB	Output is correct
9	Correct	174 ms	13164 KB	Output is correct
10	Correct	151 ms	13200 KB	Output is correct

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	394 ms	37892 KB	Output is correct
2	Correct	369 ms	37892 KB	Output is correct
3	Correct	355 ms	37892 KB	Output is correct
4	Correct	314 ms	37892 KB	Output is correct
5	Correct	847 ms	37892 KB	Output is correct
6	Correct	412 ms	37892 KB	Output is correct
7	Correct	508 ms	38076 KB	Output is correct
8	Execution timed out	1034 ms	38076 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

답안 #47178

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