답안 #46165 :: oj.uz

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

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<=P ? 2 : 20000;

    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<P) 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	23 ms	20312 KB	Output is correct
2	Correct	17 ms	20328 KB	Output is correct
3	Correct	17 ms	20404 KB	Output is correct
4	Correct	18 ms	20476 KB	Output is correct
5	Correct	17 ms	20476 KB	Output is correct
6	Correct	19 ms	20504 KB	Output is correct
7	Correct	18 ms	20584 KB	Output is correct
8	Correct	34 ms	20584 KB	Output is correct
9	Correct	18 ms	20584 KB	Output is correct
10	Correct	17 ms	20648 KB	Output is correct
11	Correct	18 ms	20648 KB	Output is correct
12	Correct	17 ms	20648 KB	Output is correct
13	Correct	19 ms	20648 KB	Output is correct
14	Correct	18 ms	20648 KB	Output is correct
15	Correct	17 ms	20648 KB	Output is correct
16	Correct	17 ms	20648 KB	Output is correct
17	Correct	17 ms	20648 KB	Output is correct
18	Correct	18 ms	20648 KB	Output is correct
19	Correct	18 ms	20648 KB	Output is correct
20	Correct	18 ms	20648 KB	Output is correct
21	Correct	18 ms	20648 KB	Output is correct
22	Correct	18 ms	20648 KB	Output is correct
23	Correct	17 ms	20648 KB	Output is correct
24	Correct	17 ms	20812 KB	Output is correct
25	Correct	17 ms	20812 KB	Output is correct
26	Correct	18 ms	20812 KB	Output is correct
27	Correct	21 ms	20812 KB	Output is correct
28	Correct	17 ms	20812 KB	Output is correct
29	Correct	18 ms	20812 KB	Output is correct
30	Correct	17 ms	20812 KB	Output is correct
31	Correct	18 ms	20812 KB	Output is correct
32	Correct	18 ms	20812 KB	Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 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	34 ms	22140 KB	Output is correct
5	Correct	26 ms	22140 KB	Output is correct
6	Correct	35 ms	22140 KB	Output is correct
7	Correct	28 ms	22140 KB	Output is correct
8	Correct	20 ms	22140 KB	Output is correct
9	Correct	19 ms	22140 KB	Output is correct
10	Correct	28 ms	22140 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	245 ms	36460 KB	Output is correct
2	Correct	227 ms	36460 KB	Output is correct
3	Correct	285 ms	36480 KB	Output is correct
4	Correct	295 ms	36600 KB	Output is correct
5	Correct	158 ms	36600 KB	Output is correct
6	Correct	167 ms	36600 KB	Output is correct
7	Correct	208 ms	36600 KB	Output is correct
8	Correct	51 ms	36600 KB	Output is correct
9	Correct	88 ms	36600 KB	Output is correct
10	Correct	147 ms	36600 KB	Output is correct

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	831 ms	61260 KB	Output is correct
2	Correct	713 ms	62672 KB	Output is correct
3	Execution timed out	1022 ms	70164 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

답안 #46165

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