답안 #46160 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46160	2018-04-17T11:36:43 Z	Extazy	회문 (APIO14_palindrome)	C++17	73 / 100	687 ms	62412 KB

palindrome

#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
const unsigned long long B1 = 131, B2 = 137, MOD = (1e9) + 7;
const int N = 300007;
 
struct rolling_hash {
    unsigned long long h1;
    unsigned h2;
    
    rolling_hash(): h1(0), h2(0) {}
 
    void append(char a) {
        h1*=B1;
        h1+=a-'a'+1;
        h2=(h2*1llu*B2+a-'a'+1)%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 : h1<a.h1;
    }
};
 
struct hash_rolling_hash {
    unsigned long long operator () (const rolling_hash &a) const {
        return a.h1^(a.h2<<30);
    }
};
 
struct item {
    rolling_hash hash;
    int from,to;
 
    item(){}
    item(rolling_hash a, int b, int c): hash(a), from(b), to(c) {}
    
    bool operator <(const item &a) const {
        return to-from+1==a.to-a.from+1 ? hash<a.hash : to-from+1<a.to-a.from+1;
    }
};
 
int n;
char a[N];
unsigned long long pw1[N];
unsigned pw2[N];
rolling_hash ph[N],sh[N];
unordered_map < rolling_hash, pair < int, int >, hash_rolling_hash > interval;
unordered_map < rolling_hash, int, hash_rolling_hash > current_cnt;
priority_queue < item > q;
long long ans;
list < item > wait[N];
 
inline rolling_hash get_prefix_hash(rolling_hash *a, int l, int r) {
    rolling_hash hl=a[l-1],hr=a[r];
 
    hl.h1*=pw1[r-l+1];
    hl.h2=hl.h2*1llu*pw2[r-l+1]%MOD;
 
    hr.h1-=hl.h1;
    hr.h2-=hl.h2;
    hr.h2+=MOD;
    hr.h2%=MOD;
    
    return hr;
}
 
inline rolling_hash get_suffix_hash(rolling_hash *a, int l, int r) {
    rolling_hash hl=a[l],hr=a[r+1];
    
    hr.h1*=pw1[r-l+1];
    hr.h2=hr.h2*1llu*pw2[r-l+1]%MOD;
 
    hl.h1-=hr.h1;
    hl.h2-=hr.h2;
    hl.h2+=MOD;
    hl.h2%=MOD;
 
    return hl;
}
 
inline bool is_palindrome(int l, int r) {
    return get_prefix_hash(ph,l,r)==get_suffix_hash(sh,l,r);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j;
    rolling_hash h;
 
    pw1[0]=pw2[0]=1;
    for(i=1;i<N;i++) {
        pw1[i]=pw1[i-1]*B1;
        pw2[i]=pw2[i-1]*1llu*B2%MOD;
    }
 
    while((a[++n]=getchar_unlocked())!='\n');
    --n;
 
    h=rolling_hash();
    for(i=1;i<=n;i++) {
        h.append(a[i]);
        ph[i]=h;
    }
 
    h=rolling_hash();
    for(i=n;i>=1;i--) {
        h.append(a[i]);
        sh[i]=h;
    }
 
    for(i=1;i<=n;i++) {
        int left=0,right=min(i,n-i+1),middle;
 
        while(right-left>1) {
            middle=(left+right)/2;
            
            if(is_palindrome(i-middle,i+middle)) left=middle;
            else right=middle;
        }
 
        for(j=left;j>=0;j--) {
            h=get_prefix_hash(ph,i-j,i+j);
 
            if(interval.find(h)!=interval.end()) break;
            
            wait[2*j+1].push_back(item(h,i-j,i+j));
            interval[h]=make_pair(i-j,i+j);
        }
 
        h=get_prefix_hash(ph,i-left,i+left);
        ++current_cnt[h];
    }
 
    for(i=1;i<n;i++) if(a[i]==a[i+1]) {
        int left=0,right=min(i,n-i),middle;
        
        while(right-left>1) {
            middle=(left+right)/2;
 
            if(is_palindrome(i-middle,i+1+middle)) left=middle;
            else right=middle;
        }
 
        for(j=left;j>=0;j--) {
            h=get_prefix_hash(ph,i-j,i+1+j);
 
            if(interval.find(h)!=interval.end()) break;
            
            wait[2*j+2].push_back(item(h,i-j,i+1+j));
            interval[h]=make_pair(i-j,i+1+j);
        }
 
        h=get_prefix_hash(ph,i-left,i+1+left);
        ++current_cnt[h];
    }
 
    int T = n<=100000 ? 2 : 100000;

    for(i=n;i>T;i--) {
        for(item curr: wait[i]) {
            int cnt=current_cnt[curr.hash];
            long long curr_ans=cnt*1ll*i;
            current_cnt.erase(curr.hash);
 
            if(curr_ans>ans) {
                ans=curr_ans;
            }
 
            curr.hash=get_prefix_hash(ph,curr.from+1,curr.to-1);
            pair < int, int > seg=interval[curr.hash];
            curr.from=seg.first;
            curr.to=seg.second;
            current_cnt[curr.hash]+=cnt;
        }
    }
 
    if(n<=100000) for(;i>=1;i--) {
        for(item curr: wait[i]) { 
            int cnt=current_cnt[curr.hash];
            long long curr_ans=cnt*1ll*i;
 
            if(curr_ans>ans) {
                ans=curr_ans;
            }
        }
    }
 
    printf("%lld\n", ans);
    
    return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	20216 KB	Output is correct
2	Correct	18 ms	20324 KB	Output is correct
3	Correct	18 ms	20400 KB	Output is correct
4	Correct	17 ms	20436 KB	Output is correct
5	Correct	18 ms	20436 KB	Output is correct
6	Correct	18 ms	20564 KB	Output is correct
7	Correct	18 ms	20564 KB	Output is correct
8	Correct	17 ms	20564 KB	Output is correct
9	Correct	18 ms	20580 KB	Output is correct
10	Correct	17 ms	20580 KB	Output is correct
11	Correct	17 ms	20580 KB	Output is correct
12	Correct	18 ms	20588 KB	Output is correct
13	Correct	18 ms	20588 KB	Output is correct
14	Correct	19 ms	20588 KB	Output is correct
15	Correct	18 ms	20716 KB	Output is correct
16	Correct	18 ms	20716 KB	Output is correct
17	Correct	17 ms	20716 KB	Output is correct
18	Correct	19 ms	20716 KB	Output is correct
19	Correct	18 ms	20716 KB	Output is correct
20	Correct	17 ms	20716 KB	Output is correct
21	Correct	17 ms	20716 KB	Output is correct
22	Correct	18 ms	20716 KB	Output is correct
23	Correct	17 ms	20716 KB	Output is correct
24	Correct	17 ms	20716 KB	Output is correct
25	Correct	17 ms	20716 KB	Output is correct
26	Correct	17 ms	20716 KB	Output is correct
27	Correct	17 ms	20716 KB	Output is correct
28	Correct	19 ms	20716 KB	Output is correct
29	Correct	18 ms	20716 KB	Output is correct
30	Correct	18 ms	20716 KB	Output is correct
31	Correct	17 ms	20716 KB	Output is correct
32	Correct	18 ms	20716 KB	Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	22140 KB	Output is correct
2	Correct	28 ms	22140 KB	Output is correct
3	Correct	30 ms	22140 KB	Output is correct
4	Correct	30 ms	22140 KB	Output is correct
5	Correct	26 ms	22140 KB	Output is correct
6	Correct	27 ms	22140 KB	Output is correct
7	Correct	29 ms	22140 KB	Output is correct
8	Correct	20 ms	22140 KB	Output is correct
9	Correct	21 ms	22140 KB	Output is correct
10	Correct	24 ms	22140 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	236 ms	36504 KB	Output is correct
2	Correct	204 ms	36504 KB	Output is correct
3	Correct	273 ms	36508 KB	Output is correct
4	Correct	259 ms	36508 KB	Output is correct
5	Correct	151 ms	36508 KB	Output is correct
6	Correct	133 ms	36508 KB	Output is correct
7	Correct	229 ms	36508 KB	Output is correct
8	Correct	47 ms	36508 KB	Output is correct
9	Correct	78 ms	36508 KB	Output is correct
10	Correct	142 ms	36508 KB	Output is correct

Subtask #5
0 / 27.0

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

답안 #46160

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 / 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 / 27.0