oj.uz

Submission #24779

# Submission time Handle Problem Language Result Execution time Memory
24779 2017-06-13T20:30:24 Z Extazy Palindromes (APIO14_palindrome) C++14
47 / 100
 1000 ms 60868 KB 
/*
example test starts
1

aaaacacaa
example test ends
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 300007;
const unsigned long long B1 = 137, B2 = 139, MOD = (1e9) + 7;

struct rolling_hash {
    unsigned long long h1,h2;
    void initialize() {
        h1=0;
        h2=0;
    }
    void append(char a) {
        h1*=B1;
        h1+=a-'a'+1;
        h1%=MOD;
        h2*=B2;
        h2+=a-'a'+1;
        h2%=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) ? h1<a.h1 : h2<a.h2);
    }
};

struct cmp {
    bool operator () (const pair < int, int > &a, const pair < int, int > &b) const {
        return ((a.second-a.first==b.second-b.first) ? a.first<b.first : a.second-a.first>b.second-b.first);
    }
};

unsigned long long pw1[N],pw2[N];
rolling_hash ph[N],sh[N];
char a[N];
map < rolling_hash, pair < int, int > > code;
map < pair < int, int >, int > value;
int n;
set < pair < int, int >, cmp > s;
long long ans;

rolling_hash get_hash(int l, int r) {
    rolling_hash hl=ph[l-1],hr=ph[r];
    
    hl.h1*=pw1[r-l+1];
    hl.h1%=MOD;
    hl.h2*=pw2[r-l+1];
    hl.h2%=MOD;
    
    hr.h1-=hl.h1;
    hr.h1+=MOD;
    hr.h1%=MOD;
    hr.h2-=hl.h2;
    hr.h2+=MOD;
    hr.h2%=MOD;

    return hr;
}

rolling_hash get_reversed_hash(int l, int r) {
    rolling_hash hl=sh[r+1],hr=sh[l];
    
    hl.h1*=pw1[r-l+1];
    hl.h1%=MOD;
    hl.h2*=pw2[r-l+1];
    hl.h2%=MOD;
    
    hr.h1-=hl.h1;
    hr.h1+=MOD;
    hr.h1%=MOD;
    hr.h2-=hl.h2;
    hr.h2+=MOD;
    hr.h2%=MOD;

    return hr;
}

bool is_palindrome(int l, int r) {
    return get_hash(l,r)==get_reversed_hash(l,r);
}

int main() {
    int tests,current_case;
    int i,j,left,right,middle;
    pair < int, int > curr;
    rolling_hash h;

    pw1[0]=pw2[0]=1;
    for(i=1;i<N;i++) pw1[i]=pw1[i-1]*B1%MOD,pw2[i]=pw2[i-1]*B2%MOD;

    tests=1;
    //scanf("%d", &tests);
    for(current_case=1;current_case<=tests;current_case++) {
        scanf("%s", a+1);
        n=strlen(a+1);

        //Compute prefix hash
        h.initialize();
        ph[0]=h;
        for(i=1;i<=n;i++) {
            h.append(a[i]);
            ph[i]=h;
        }

        //Compute suffix hash
        h.initialize();
        sh[n+1]=h;
        for(i=n;i>=1;i--) {
            h.append(a[i]);
            sh[i]=h;
        }

        code.clear();
        s.clear();
        value.clear();
        for(i=1;i<=n;i++) {
            left=0;
            right=min(i-1,n-i)+1;
            while(right-left>1) {
                middle=(left+right)>>1;
                if(is_palindrome(i-middle,i+middle)) left=middle;
                else right=middle;
            }
            for(j=left;j+j+1>0;j--) {
                if(code.find(get_hash(i-j,i+j))==code.end()) {
                    code[get_hash(i-j,i+j)]=make_pair(i-j,i+j);
                }
                else {
                    break;
                }
            }
            ++value[code[get_hash(i-left,i+left)]];
            if(s.find(code[get_hash(i-left,i+left)])==s.end()) s.insert(code[get_hash(i-left,i+left)]);
        }

        for(i=1;i<n;i++) if(a[i]==a[i+1]) {
            left=0;
            right=min(i-1,n-i-1)+1;
            while(right-left>1) {
                middle=(left+right)>>1;
                if(is_palindrome(i-middle,i+1+middle)) left=middle;
                else right=middle;
            }
            for(j=left;j+j+2>0;j--) {
                if(code.find(get_hash(i-j,i+1+j))==code.end()) {
                    code[get_hash(i-j,i+1+j)]=make_pair(i-j,i+1+j);
                }
                else {
                    break;
                }
            }
            ++value[code[get_hash(i-left,i+1+left)]];
            if(s.find(code[get_hash(i-left,i+1+left)])==s.end()) s.insert(code[get_hash(i-left,i+1+left)]);
        }

        ans=0;
        while(!s.empty()) {
            curr=*s.begin();
            s.erase(s.begin());
            ans=max(ans,(curr.second-curr.first+1)*1ll*value[curr]);
            if(curr.first+1<=curr.second-1) if(s.find(code[get_hash(curr.first+1,curr.second-1)])==s.end()) {
                value[code[get_hash(curr.first+1,curr.second-1)]]+=value[code[get_hash(curr.first,curr.second)]];
                s.insert(code[get_hash(curr.first+1,curr.second-1)]);
            }
            else {
                value[code[get_hash(curr.first+1,curr.second-1)]]+=value[code[get_hash(curr.first,curr.second)]];
            }
        }

        printf("%lld\n", ans);
    }

    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:171:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
             if(curr.first+1<=curr.second-1) if(s.find(code[get_hash(curr.first+1,curr.second-1)])==s.end()) {
               ^
palindrome.cpp:104:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", a+1);
                         ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16384 KB Output is correct
2 Correct 0 ms 16384 KB Output is correct
3 Correct 0 ms 16384 KB Output is correct
4 Correct 0 ms 16384 KB Output is correct
5 Correct 3 ms 16384 KB Output is correct
6 Correct 0 ms 16384 KB Output is correct
7 Correct 0 ms 16384 KB Output is correct
8 Correct 3 ms 16384 KB Output is correct
9 Correct 3 ms 16384 KB Output is correct
10 Correct 0 ms 16384 KB Output is correct
11 Correct 0 ms 16384 KB Output is correct
12 Correct 0 ms 16384 KB Output is correct
13 Correct 3 ms 16384 KB Output is correct
14 Correct 3 ms 16384 KB Output is correct
15 Correct 0 ms 16384 KB Output is correct
16 Correct 0 ms 16384 KB Output is correct
17 Correct 3 ms 16384 KB Output is correct
18 Correct 3 ms 16384 KB Output is correct
19 Correct 0 ms 16384 KB Output is correct
20 Correct 3 ms 16384 KB Output is correct
21 Correct 0 ms 16384 KB Output is correct
22 Correct 3 ms 16384 KB Output is correct
23 Correct 3 ms 16384 KB Output is correct
24 Correct 0 ms 16384 KB Output is correct
25 Correct 0 ms 16384 KB Output is correct
26 Correct 0 ms 16384 KB Output is correct
27 Correct 0 ms 16384 KB Output is correct
28 Correct 0 ms 16384 KB Output is correct
29 Correct 0 ms 16384 KB Output is correct
30 Correct 3 ms 16384 KB Output is correct
31 Correct 3 ms 16384 KB Output is correct
32 Correct 3 ms 16384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16516 KB Output is correct
2 Correct 0 ms 16516 KB Output is correct
3 Correct 3 ms 16516 KB Output is correct
4 Correct 6 ms 16516 KB Output is correct
5 Correct 6 ms 16516 KB Output is correct
6 Correct 0 ms 16516 KB Output is correct
7 Correct 0 ms 16516 KB Output is correct
8 Correct 6 ms 16516 KB Output is correct
9 Correct 3 ms 16516 KB Output is correct
10 Correct 0 ms 16384 KB Output is correct
11 Correct 0 ms 16384 KB Output is correct
12 Correct 0 ms 16516 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18100 KB Output is correct
2 Correct 29 ms 17968 KB Output is correct
3 Correct 43 ms 18100 KB Output is correct
4 Correct 39 ms 18100 KB Output is correct
5 Correct 16 ms 17704 KB Output is correct
6 Correct 33 ms 17704 KB Output is correct
7 Correct 39 ms 18100 KB Output is correct
8 Correct 6 ms 16516 KB Output is correct
9 Correct 6 ms 16516 KB Output is correct
10 Correct 16 ms 17308 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 33544 KB Output is correct
2 Correct 546 ms 32620 KB Output is correct
3 Correct 693 ms 33544 KB Output is correct
4 Incorrect 676 ms 33544 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 60868 KB Execution timed out
2 Halted 0 ms 0 KB -