답안 #46175 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46175	2018-04-17T12:11:49 Z	Extazy	회문 (APIO14_palindrome)	C++17	73 / 100	1000 ms	69296 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	18 ms	20344 KB	Output is correct
2	Correct	21 ms	20456 KB	Output is correct
3	Correct	18 ms	20456 KB	Output is correct
4	Correct	18 ms	20456 KB	Output is correct
5	Correct	19 ms	20456 KB	Output is correct
6	Correct	19 ms	20456 KB	Output is correct
7	Correct	18 ms	20456 KB	Output is correct
8	Correct	19 ms	20480 KB	Output is correct
9	Correct	18 ms	20596 KB	Output is correct
10	Correct	18 ms	20596 KB	Output is correct
11	Correct	18 ms	20596 KB	Output is correct
12	Correct	18 ms	20696 KB	Output is correct
13	Correct	19 ms	20696 KB	Output is correct
14	Correct	18 ms	20716 KB	Output is correct
15	Correct	20 ms	20716 KB	Output is correct
16	Correct	18 ms	20716 KB	Output is correct
17	Correct	22 ms	20716 KB	Output is correct
18	Correct	18 ms	20716 KB	Output is correct
19	Correct	18 ms	20716 KB	Output is correct
20	Correct	18 ms	20732 KB	Output is correct
21	Correct	19 ms	20732 KB	Output is correct
22	Correct	22 ms	20732 KB	Output is correct
23	Correct	19 ms	20732 KB	Output is correct
24	Correct	18 ms	20732 KB	Output is correct
25	Correct	18 ms	20732 KB	Output is correct
26	Correct	18 ms	20732 KB	Output is correct
27	Correct	19 ms	20732 KB	Output is correct
28	Correct	20 ms	20732 KB	Output is correct
29	Correct	18 ms	20732 KB	Output is correct
30	Correct	21 ms	20732 KB	Output is correct
31	Correct	21 ms	20732 KB	Output is correct
32	Correct	18 ms	20732 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	20732 KB	Output is correct
2	Correct	22 ms	20732 KB	Output is correct
3	Correct	20 ms	20732 KB	Output is correct
4	Correct	21 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	21 ms	20736 KB	Output is correct
8	Correct	24 ms	20736 KB	Output is correct
9	Correct	19 ms	20736 KB	Output is correct
10	Correct	19 ms	20736 KB	Output is correct
11	Correct	19 ms	20736 KB	Output is correct
12	Correct	19 ms	20736 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	22140 KB	Output is correct
2	Correct	29 ms	22140 KB	Output is correct
3	Correct	31 ms	22140 KB	Output is correct
4	Correct	40 ms	22140 KB	Output is correct
5	Correct	32 ms	22140 KB	Output is correct
6	Correct	26 ms	22140 KB	Output is correct
7	Correct	36 ms	22140 KB	Output is correct
8	Correct	26 ms	22140 KB	Output is correct
9	Correct	21 ms	22140 KB	Output is correct
10	Correct	33 ms	22140 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	275 ms	36612 KB	Output is correct
2	Correct	235 ms	36612 KB	Output is correct
3	Correct	250 ms	36612 KB	Output is correct
4	Correct	267 ms	36612 KB	Output is correct
5	Correct	152 ms	36612 KB	Output is correct
6	Correct	128 ms	36612 KB	Output is correct
7	Correct	237 ms	36612 KB	Output is correct
8	Correct	47 ms	36612 KB	Output is correct
9	Correct	78 ms	36612 KB	Output is correct
10	Correct	148 ms	36612 KB	Output is correct

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	805 ms	60760 KB	Output is correct
2	Correct	672 ms	60760 KB	Output is correct
3	Execution timed out	1081 ms	69296 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

답안 #46175

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