답안 #13187 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13187	2015-02-01T13:52:07 Z	baneling100	회문 (APIO14_palindrome)	C++	73 / 100	1000 ms	76516 KB

palindrome

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#define N_MAX 300000

using namespace std;

vector <int> PAL[2*N_MAX];
vector <int> PAL2[2*N_MAX+1];
int N, N_, MA[2*N_MAX], SA[2*N_MAX], LCP[2*N_MAX+1], STK[2][2*N_MAX], Top;
int Rank[4*N_MAX], Rtemp[4*N_MAX], Len, Loc[2*N_MAX];
long long Ans;
char S[2*N_MAX+1], S_[N_MAX+2];
bool comp1(int p, int q) {return S[p]<S[q];};
bool comp2(int p, int q) {return Rank[p]<Rank[q] || (Rank[p]==Rank[q] && Rank[p+Len]<Rank[q+Len]);};

void input(void) {

    int i;

    scanf("%s",&S_[1]);
    N_=strlen(&S_[1]);
    for(i=1 ; i<=N_ ; i++) {
        S[2*i-1]=S_[i];
        S[2*i  ]='#';
    }
    S[2*N_]=NULL;
    N=2*N_-1;
}

void manacher(void) {

    int i, j=0;

    for(i=1 ; i<=N ; i++) {
        i<=j+MA[j] ? MA[i]=min(j+MA[j]-i,MA[2*j-i]) : MA[i]=0;
        while(i+MA[i]+1<=N && S[i-MA[i]-1]==S[i+MA[i]+1]) MA[i]++;
        if(j+MA[j]<i+MA[i])
            j=i;
    }
}

void suffixArray(void) {

    int i;

    for(i=1 ; i<=N ; i++)
        SA[i]=i;
    sort(SA+1,SA+N+1,comp1);
    for(i=1 ; i<=N ; i++) {
        if(S[SA[i]]==S[SA[i-1]])
            Rank[SA[i]]=Rank[SA[i-1]];
        else
            Rank[SA[i]]=i;
    }
    for(Len=1 ; Len<N ; Len<<=1) {
        sort(SA+1,SA+N+1,comp2);
        for(i=1 ; i<=N ; i++) {
            if(Rank[SA[i]]>Rank[SA[i-1]] || (Rank[SA[i]]==Rank[SA[i-1]] && Rank[SA[i]+Len]>Rank[SA[i-1]+Len]))
                Rtemp[SA[i]]=i;
            else
                Rtemp[SA[i]]=Rtemp[SA[i-1]];
        }
        for(i=1 ; i<=N ; i++)
            Rank[i]=Rtemp[i];
    }
}

void longestCommonPrefix(void) {

    int i;

    for(i=1 ; i<=N ; i++)
        Loc[SA[i]]=i;
    for(i=1 ; i<=N ; i++) {
        if(LCP[Loc[i-1]])
            LCP[Loc[i]]=LCP[Loc[i-1]]-1;
        while(S[i+LCP[Loc[i]]]==S[SA[Loc[i]-1]+LCP[Loc[i]]]) LCP[Loc[i]]++;
    }
}

void calculate(void) {

    int i, j=0, k, p;

    for(i=1 ; i<=N ; i++)
        while(j+1<=i+MA[i]) {
            j++;
            PAL[Loc[2*i-j]].push_back(2*(j-i)+1);
        }
    STK[0][Top]=-1;
    for(i=1 ; i<=N ; i++) {
        while(STK[0][Top]>=LCP[i]) Top--;
        STK[0][++Top]=LCP[i];
        STK[1][  Top]=i;
        k=PAL[i].size();
        for(j=0 ; j<k ; j++) {
            p=lower_bound(STK[0]+1,STK[0]+Top+1,PAL[i][j])-STK[0]-1;
            PAL2[STK[1][p]].push_back(PAL[i][j]);
        }
    }
    for(i=1 ; i<=N ; i++)
        sort(PAL2[i].begin(),PAL2[i].end());
    Top=0;
    for(i=1 ; i<=N+1 ; i++) {
        while(STK[0][Top]>LCP[i]) {
            if(S[SA[STK[1][Top]]]=='#') {
                if(Ans<(long long)(STK[0][Top]/2)*(i-STK[1][Top]))
                    Ans=(long long)(STK[0][Top]/2)*(i-STK[1][Top]);
            }
            else
                if(Ans<(long long)((STK[0][Top]+1)/2)*(i-STK[1][Top]))
                    Ans=(long long)((STK[0][Top]+1)/2)*(i-STK[1][Top]);
            Top--;
        }
        k=PAL2[i].size();
        for(j=0 ; j<k ; j++) {
            if(j>0 && PAL2[i][j]==PAL2[i][j-1])
                continue;
            STK[0][++Top]=PAL2[i][j];
            STK[1][  Top]=i;
        }
    }
}

int main(void) {

    input();
    manacher();
    suffixArray();
    longestCommonPrefix();
    calculate();
    printf("%lld",Ans);

    return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	53660 KB	Output is correct - answer is '7'
2	Correct	3 ms	53660 KB	Output is correct - answer is '4'
3	Correct	8 ms	53660 KB	Output is correct - answer is '9'
4	Correct	3 ms	53660 KB	Output is correct - answer is '1'
5	Correct	11 ms	53660 KB	Output is correct - answer is '1'
6	Correct	4 ms	53660 KB	Output is correct - answer is '2'
7	Correct	11 ms	53660 KB	Output is correct - answer is '3'
8	Correct	3 ms	53660 KB	Output is correct - answer is '3'
9	Correct	4 ms	53660 KB	Output is correct - answer is '15'
10	Correct	4 ms	53660 KB	Output is correct - answer is '24'
11	Correct	7 ms	53660 KB	Output is correct - answer is '10'
12	Correct	3 ms	53660 KB	Output is correct - answer is '24'
13	Correct	4 ms	53660 KB	Output is correct - answer is '25'
14	Correct	7 ms	53660 KB	Output is correct - answer is '28'
15	Correct	3 ms	53660 KB	Output is correct - answer is '2'
16	Correct	0 ms	53660 KB	Output is correct - answer is '1'
17	Correct	3 ms	53660 KB	Output is correct - answer is '15'
18	Correct	0 ms	53660 KB	Output is correct - answer is '18'
19	Correct	3 ms	53660 KB	Output is correct - answer is '1176'
20	Correct	5 ms	53660 KB	Output is correct - answer is '1225'
21	Correct	3 ms	53660 KB	Output is correct - answer is '136'
22	Correct	7 ms	53660 KB	Output is correct - answer is '45'
23	Correct	11 ms	53660 KB	Output is correct - answer is '2500'
24	Correct	4 ms	53660 KB	Output is correct - answer is '380'
25	Correct	3 ms	53660 KB	Output is correct - answer is '2304'
26	Correct	4 ms	53660 KB	Output is correct - answer is '110'
27	Correct	0 ms	53660 KB	Output is correct - answer is '93'
28	Correct	3 ms	53660 KB	Output is correct - answer is '729'
29	Correct	8 ms	53660 KB	Output is correct - answer is '132'
30	Correct	3 ms	53660 KB	Output is correct - answer is '7'
31	Correct	3 ms	53660 KB	Output is correct - answer is '8'
32	Correct	3 ms	53660 KB	Output is correct - answer is '64'

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	53660 KB	Output is correct - answer is '124251'
2	Correct	9 ms	53660 KB	Output is correct - answer is '38226'
3	Correct	6 ms	53660 KB	Output is correct - answer is '249500'
4	Correct	6 ms	53660 KB	Output is correct - answer is '5778'
5	Correct	4 ms	53660 KB	Output is correct - answer is '247506'
6	Correct	10 ms	53660 KB	Output is correct - answer is '248004'
7	Correct	7 ms	53660 KB	Output is correct - answer is '973'
8	Correct	0 ms	53660 KB	Output is correct - answer is '123753'
9	Correct	9 ms	53660 KB	Output is correct - answer is '2346'
10	Correct	9 ms	53660 KB	Output is correct - answer is '53'
11	Correct	6 ms	53660 KB	Output is correct - answer is '52'
12	Correct	4 ms	53660 KB	Output is correct - answer is '976'

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	54348 KB	Output is correct - answer is '12497500'
2	Correct	35 ms	53924 KB	Output is correct - answer is '6481800'
3	Correct	34 ms	54340 KB	Output is correct - answer is '25000000'
4	Correct	38 ms	54248 KB	Output is correct - answer is '17816841'
5	Correct	37 ms	54584 KB	Output is correct - answer is '9945'
6	Correct	45 ms	54320 KB	Output is correct - answer is '504100'
7	Correct	41 ms	53924 KB	Output is correct - answer is '1512930'
8	Correct	32 ms	54320 KB	Output is correct - answer is '413'
9	Correct	34 ms	54320 KB	Output is correct - answer is '428'
10	Correct	43 ms	54452 KB	Output is correct - answer is '7232'

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	407 ms	60904 KB	Output is correct - answer is '1249925001'
2	Correct	417 ms	60908 KB	Output is correct - answer is '396337935'
3	Correct	401 ms	60892 KB	Output is correct - answer is '2500050000'
4	Correct	395 ms	57736 KB	Output is correct - answer is '1016525689'
5	Correct	510 ms	63956 KB	Output is correct - answer is '99645'
6	Correct	488 ms	59804 KB	Output is correct - answer is '78569380'
7	Correct	448 ms	60192 KB	Output is correct - answer is '82810000'
8	Correct	508 ms	60320 KB	Output is correct - answer is '3989'
9	Correct	493 ms	60688 KB	Output is correct - answer is '125529616'
10	Correct	514 ms	62504 KB	Output is correct - answer is '66664'

Subtask #5
0.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1000 ms	76516 KB	Program timed out
2	Halted	0 ms	0 KB	-

답안 #13187

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 26.0 / 26.0

Subtask #5 0.0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
26.0 / 26.0

Subtask #5
0.0 / 27.0