제출 #24781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24781		Extazy	회문 (APIO14_palindrome)	C++14	47 / 100	1000 ms	60868 KiB

palindrome

/*
example test starts
1

aaaacacaa
example test ends
*/
#include <bits/stdc++.h>

using namespace std;

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

struct rolling_hash {
    unsigned long long h1,h2;
    void initialize() {
        h1=0;
        h2=0;
    }
    void append(char a) {
        h1*=B1;
        h1+=a-'a'+1;
        h1%=MOD;
        h2*=B2;
        h2+=a-'a'+1;
        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) ? h1<a.h1 : h2<a.h2);
    }
};

struct cmp {
    bool operator () (const pair < int, int > &a, const pair < int, int > &b) const {
        return ((a.second-a.first==b.second-b.first) ? a.first<b.first : a.second-a.first>b.second-b.first);
    }
};

unsigned long long pw1[N],pw2[N];
rolling_hash ph[N],sh[N];
char a[N];
map < rolling_hash, pair < int, int > > code;
map < pair < int, int >, int > value;
int n;
set < pair < int, int >, cmp > s;
long long ans;

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;
}

rolling_hash get_reversed_hash(int l, int r) {
    rolling_hash hl=sh[r+1],hr=sh[l];
    
    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 is_palindrome(int l, int r) {
    return get_hash(l,r)==get_reversed_hash(l,r);
}

int main() {
    int tests,current_case;
    int i,j,left,right,middle;
    pair < int, int > curr;
    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);

        //Compute prefix hash
        h.initialize();
        ph[0]=h;
        for(i=1;i<=n;i++) {
            h.append(a[i]);
            ph[i]=h;
        }

        //Compute suffix hash
        h.initialize();
        sh[n+1]=h;
        for(i=n;i>=1;i--) {
            h.append(a[i]);
            sh[i]=h;
        }

        code.clear();
        s.clear();
        value.clear();
        for(i=1;i<=n;i++) {
            left=0;
            right=min(i-1,n-i)+1;
            while(right-left>1) {
                middle=(left+right)>>1;
                if(is_palindrome(i-middle,i+middle)) left=middle;
                else right=middle;
            }
            for(j=left;j+j+1>0;j--) {
                if(code.find(get_hash(i-j,i+j))==code.end()) {
                    code[get_hash(i-j,i+j)]=make_pair(i-j,i+j);
                }
                else {
                    break;
                }
            }
            ++value[code[get_hash(i-left,i+left)]];
            if(s.find(code[get_hash(i-left,i+left)])==s.end()) s.insert(code[get_hash(i-left,i+left)]);
        }

        for(i=1;i<n;i++) if(a[i]==a[i+1]) {
            left=0;
            right=min(i-1,n-i-1)+1;
            while(right-left>1) {
                middle=(left+right)>>1;
                if(is_palindrome(i-middle,i+1+middle)) left=middle;
                else right=middle;
            }
            for(j=left;j+j+2>0;j--) {
                if(code.find(get_hash(i-j,i+1+j))==code.end()) {
                    code[get_hash(i-j,i+1+j)]=make_pair(i-j,i+1+j);
                }
                else {
                    break;
                }
            }
            ++value[code[get_hash(i-left,i+1+left)]];
            if(s.find(code[get_hash(i-left,i+1+left)])==s.end()) s.insert(code[get_hash(i-left,i+1+left)]);
        }

        ans=0;
        while(!s.empty()) {
            curr=*s.begin();
            s.erase(s.begin());
            ans=max(ans,(curr.second-curr.first+1)*1ll*value[curr]);
            if(curr.first+1<=curr.second-1) if(s.find(code[get_hash(curr.first+1,curr.second-1)])==s.end()) {
                value[code[get_hash(curr.first+1,curr.second-1)]]+=value[code[get_hash(curr.first,curr.second)]];
                s.insert(code[get_hash(curr.first+1,curr.second-1)]);
            }
            else {
                value[code[get_hash(curr.first+1,curr.second-1)]]+=value[code[get_hash(curr.first,curr.second)]];
            }
        }

        printf("%lld\n", ans);
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int main()':
palindrome.cpp:171:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
             if(curr.first+1<=curr.second-1) if(s.find(code[get_hash(curr.first+1,curr.second-1)])==s.end()) {
               ^
palindrome.cpp:104:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", a+1);
                         ^

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27