답안 #46169 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46169	2018-04-17T11:43:41 Z	Extazy	회문 (APIO14_palindrome)	C++17	73 / 100	1000 ms	69144 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;
        }

        if(n>100000 && left<10000) continue;

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

        if(n>100000 && left<10000) continue;
 
        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];
    }

    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	20 ms	20344 KB	Output is correct
2	Correct	18 ms	20344 KB	Output is correct
3	Correct	17 ms	20396 KB	Output is correct
4	Correct	18 ms	20460 KB	Output is correct
5	Correct	19 ms	20632 KB	Output is correct
6	Correct	18 ms	20636 KB	Output is correct
7	Correct	18 ms	20636 KB	Output is correct
8	Correct	18 ms	20636 KB	Output is correct
9	Correct	19 ms	20636 KB	Output is correct
10	Correct	21 ms	20636 KB	Output is correct
11	Correct	18 ms	20636 KB	Output is correct
12	Correct	18 ms	20636 KB	Output is correct
13	Correct	18 ms	20636 KB	Output is correct
14	Correct	18 ms	20636 KB	Output is correct
15	Correct	18 ms	20636 KB	Output is correct
16	Correct	19 ms	20636 KB	Output is correct
17	Correct	18 ms	20636 KB	Output is correct
18	Correct	17 ms	20636 KB	Output is correct
19	Correct	18 ms	20636 KB	Output is correct
20	Correct	18 ms	20636 KB	Output is correct
21	Correct	21 ms	20636 KB	Output is correct
22	Correct	18 ms	20636 KB	Output is correct
23	Correct	18 ms	20636 KB	Output is correct
24	Correct	18 ms	20636 KB	Output is correct
25	Correct	18 ms	20636 KB	Output is correct
26	Correct	17 ms	20636 KB	Output is correct
27	Correct	18 ms	20636 KB	Output is correct
28	Correct	18 ms	20636 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	18 ms	20716 KB	Output is correct
2	Correct	19 ms	20732 KB	Output is correct
3	Correct	19 ms	20732 KB	Output is correct
4	Correct	19 ms	20732 KB	Output is correct
5	Correct	19 ms	20732 KB	Output is correct
6	Correct	19 ms	20864 KB	Output is correct
7	Correct	23 ms	20864 KB	Output is correct
8	Correct	22 ms	20864 KB	Output is correct
9	Correct	21 ms	20864 KB	Output is correct
10	Correct	18 ms	20864 KB	Output is correct
11	Correct	18 ms	20864 KB	Output is correct
12	Correct	18 ms	20864 KB	Output is correct

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	257 ms	36424 KB	Output is correct
2	Correct	222 ms	36424 KB	Output is correct
3	Correct	314 ms	36424 KB	Output is correct
4	Correct	279 ms	36504 KB	Output is correct
5	Correct	188 ms	36504 KB	Output is correct
6	Correct	128 ms	36504 KB	Output is correct
7	Correct	215 ms	36504 KB	Output is correct
8	Correct	49 ms	36504 KB	Output is correct
9	Correct	79 ms	36504 KB	Output is correct
10	Correct	139 ms	36504 KB	Output is correct

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	823 ms	61056 KB	Output is correct
2	Correct	679 ms	61056 KB	Output is correct
3	Execution timed out	1090 ms	69144 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

답안 #46169

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