답안 #46172 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46172	2018-04-17T11:46:18 Z	Extazy	회문 (APIO14_palindrome)	C++17	73 / 100	714 ms	55716 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;
const int P = 30000;
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;
        }

		int to = (n>100000 ? P : 0);
        for(j=left;j>=to;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;
        }

        if(n>100000 && left<10000) continue;
 
      	int to = (n>100000 ? P : 0);
        for(j=left;j>=to;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];
    }

    for(i=n;i>2;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;
        }
    }
 
    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	17 ms	20344 KB	Output is correct
2	Correct	17 ms	20344 KB	Output is correct
3	Correct	18 ms	20396 KB	Output is correct
4	Correct	18 ms	20472 KB	Output is correct
5	Correct	17 ms	20548 KB	Output is correct
6	Correct	18 ms	20580 KB	Output is correct
7	Correct	19 ms	20588 KB	Output is correct
8	Correct	19 ms	20588 KB	Output is correct
9	Correct	18 ms	20588 KB	Output is correct
10	Correct	18 ms	20716 KB	Output is correct
11	Correct	22 ms	20716 KB	Output is correct
12	Correct	18 ms	20716 KB	Output is correct
13	Correct	17 ms	20716 KB	Output is correct
14	Correct	19 ms	20716 KB	Output is correct
15	Correct	17 ms	20716 KB	Output is correct
16	Correct	17 ms	20716 KB	Output is correct
17	Correct	18 ms	20716 KB	Output is correct
18	Correct	17 ms	20716 KB	Output is correct
19	Correct	19 ms	20716 KB	Output is correct
20	Correct	18 ms	20716 KB	Output is correct
21	Correct	19 ms	20716 KB	Output is correct
22	Correct	18 ms	20716 KB	Output is correct
23	Correct	18 ms	20716 KB	Output is correct
24	Correct	18 ms	20716 KB	Output is correct
25	Correct	18 ms	20716 KB	Output is correct
26	Correct	19 ms	20716 KB	Output is correct
27	Correct	18 ms	20716 KB	Output is correct
28	Correct	18 ms	20716 KB	Output is correct
29	Correct	20 ms	20716 KB	Output is correct
30	Correct	18 ms	20716 KB	Output is correct
31	Correct	18 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	18 ms	20736 KB	Output is correct
4	Correct	19 ms	20736 KB	Output is correct
5	Correct	19 ms	20736 KB	Output is correct
6	Correct	19 ms	20736 KB	Output is correct
7	Correct	18 ms	20736 KB	Output is correct
8	Correct	24 ms	20736 KB	Output is correct
9	Correct	18 ms	20808 KB	Output is correct
10	Correct	18 ms	20808 KB	Output is correct
11	Correct	18 ms	20808 KB	Output is correct
12	Correct	23 ms	20808 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	22140 KB	Output is correct
2	Correct	32 ms	22140 KB	Output is correct
3	Correct	32 ms	22140 KB	Output is correct
4	Correct	33 ms	22140 KB	Output is correct
5	Correct	25 ms	22140 KB	Output is correct
6	Correct	27 ms	22140 KB	Output is correct
7	Correct	31 ms	22144 KB	Output is correct
8	Correct	20 ms	22144 KB	Output is correct
9	Correct	20 ms	22144 KB	Output is correct
10	Correct	24 ms	22144 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	228 ms	36400 KB	Output is correct
2	Correct	247 ms	36400 KB	Output is correct
3	Correct	284 ms	36504 KB	Output is correct
4	Correct	282 ms	36504 KB	Output is correct
5	Correct	179 ms	36504 KB	Output is correct
6	Correct	144 ms	36504 KB	Output is correct
7	Correct	198 ms	36504 KB	Output is correct
8	Correct	53 ms	36504 KB	Output is correct
9	Correct	83 ms	36504 KB	Output is correct
10	Correct	149 ms	36504 KB	Output is correct

Subtask #5
0 / 27.0

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

답안 #46172

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