oj.uz

답안 #24724

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24724 2017-06-12T12:02:24 Z Extazy 회문 (APIO14_palindrome) C++14
0 / 100
 1000 ms 17556 KB 
/*
example test starts

abacaba

www
example test ends
*/
#include <bits/stdc++.h>
#define left aklhglahjkga
#define right qioyhqhgjkqh

using namespace std;

const unsigned long long B1 = 137, B2 = 139, MOD = (1e9) + 7;
const int N = 300007;

struct rolling_hash {
    unsigned long long h1,h2;
    void initialize() {
        h1=0;
        h2=0;
    }
    void append(char a) {
        h1*=B1;
        h2*=B2;
        h1+=a;
        h2+=a;
        h1%=MOD;
        h2%=MOD;
    }
    bool operator ==(const rolling_hash &a) const {
        return (h1==a.h1 && h2==a.h2);
    }
    bool operator !=(const rolling_hash &a) const {
        return !(h1==a.h1 && h2==a.h2);
    }
};

int n;
char a[N];
rolling_hash ph[N];
int sa[N],lcp[N];
long long ans;
int left[N],right[N];
stack < int > s;
unsigned long long pw1[N],pw2[N];

rolling_hash get_hash(int l, int r) {
    rolling_hash hl=ph[l-1],hr=ph[r];
    hl.h1*=pw1[r-l+1];
    hl.h1%=MOD;
    hl.h2*=pw2[r-l+1];
    hl.h2%=MOD;
    
    hr.h1-=hl.h1;
    hr.h1+=MOD;
    hr.h1%=MOD;
    hr.h2-=hl.h2;
    hr.h2+=MOD;
    hr.h2%=MOD;

    return hr;
}

bool compare_suffixes(int x, int y) {
    int l1=n-x+1,l2=n-y+1,left=0,right=min(l1,l2),middle;

    if(get_hash(x,x+right-1)==get_hash(y,y+right-1)) return (x>y);

    while(right-left>1) {
        middle=(left+right)>>1;
        if(get_hash(x,x+middle-1)==get_hash(y,y+middle-1)) left=middle;
        else right=middle;
    }

    return (a[x+left]<a[y+left]);
}

void build_suffix_array() {
    for(int i=1;i<=n;i++) sa[i]=i;
    stable_sort(sa+1,sa+1+n,compare_suffixes);
}

void build_lcp() {
    int i,left,right,middle;
    for(i=1;i<n;i++) {
        left=0;
        right=min(n-sa[i]+1,n-sa[i+1]+1)+1;
        while(right-left>1) {
            middle=(left+right)>>1;
            if(get_hash(sa[i],sa[i]+middle-1)==get_hash(sa[i+1],sa[i+1]+middle-1)) left=middle;
            else right=middle;
        }
        lcp[i]=left;
    }
}

int main() {
    int tests,current_case;
    int i;
    rolling_hash h;

    pw1[0]=pw2[0]=1;
    for(i=1;i<N;i++) pw1[i]=pw1[i-1]*B1%MOD,pw2[i]=pw2[i-1]*B2%MOD;

    tests=1;
    //scanf("%d", &tests);
    for(current_case=1;current_case<=tests;current_case++) {
        scanf("%s", a+1);
        n=strlen(a+1);

        h.initialize();
        ph[0]=h;
        for(i=1;i<=n;i++) h.append(a[i]),ph[i]=h;

        build_suffix_array();
        build_lcp();

        while(!s.empty()) s.pop();
        for(i=1;i<n;i++) {
            while(!s.empty() && lcp[s.top()]>=lcp[i]) s.pop();
            if(s.empty()) left[i]=i-1;
            else left[i]=i-s.top()-1;
            s.push(i);
        }

        while(!s.empty()) s.pop();
        for(i=n-1;i>=1;i--) {
            while(!s.empty() && lcp[s.top()]>=lcp[i]) s.pop();
            if(s.empty()) right[i]=n-1-i;
            else right[i]=s.top()-i-1;
            s.push(i);
        }
    
        ans=n;
        for(i=1;i<n;i++) {
            ans=max(ans,(left[i]+right[i]+2)*1ll*lcp[i]);
        }
        
        printf("%lld\n", ans);
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 8.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 679 ms 17556 KB Output is correct
2 Execution timed out 1000 ms 17556 KB Execution timed out
3 Halted 0 ms 0 KB -