oj.uz

Submission #46701

# Submission time Handle Problem Language Result Execution time Memory
46701 2018-04-22T15:16:37 Z minkank Palindromes (APIO14_palindrome) C++17
100 / 100
 776 ms 37548 KB 
#include <bits/stdc++.h>
#pragma GCC optimization("O3")
#define ll long long
using namespace std;
const ll mod = (ll) 1e9+9;
const ll base = 29;
int lg2[300005];
void prepLg2(int bound){
    for(int i=2;i<=bound;i++)
        lg2[i] = lg2[i>>1] + 1;
}
struct suffixArray{
    int sa[300005], saRank[300005], tmp[300005];
    int lcp[300005][19];
    int strLen, gap;
 
    bool saCmp(int x,int y){
        if (saRank[x] != saRank[y])
            return saRank[x] < saRank[y];
        return x+gap < strLen && y+gap < strLen ? saRank[x+gap] < saRank[y+gap] : x > y;
    }
 
    void build_lcp(string &s){
        int k = 0;
        for(int i = 0; i < strLen; i ++){
            if (saRank[i] != strLen - 1){
                for (int j = sa[saRank[i] + 1]; max(i+k, j+k) < strLen && s[i + k] == s[j + k];)  ++k;
                lcp[saRank[i]][0] = k;
                if (k) k--;
            }
        }
        for(int k = 1; k < 19; k ++){
            for(int i = 0; i < strLen; i ++)
                if (i + (1<<k) < strLen)
                    lcp[i][k] = min(lcp[i][k-1], lcp[i+(1<<(k-1))][k-1]);
                else break;
        }
    }
 
    int getLcp(int l,int r){
        if (l > r)  swap(l, r);
        if (l == r) return strLen - sa[l];
        int k = lg2[r - l];
        return min(lcp[l][k], lcp[r-(1<<k)][k]);
    }
 
    void build(string &s, int isIndexFromOne = 0){
        strLen = s.size();
        //for(int i = 0; i < strLen; i ++)
        //    lcp[i].assign(20, 0);
 
        for(int i = 0; i < strLen; i ++)
            sa[i] = i, saRank[i] = s[i];
 
        for(gap = 1;;gap *= 2){
            sort(sa, sa + strLen, [&](int a, int b) {return this->saCmp(a, b);});
            //sort(sa.begin(), sa.begin() + strLen, saCmp);
            for(int i = 0; i < strLen; i ++) tmp[i+1] = tmp[i] + saCmp(sa[i], sa[i+1]);
            for(int i = 0; i < strLen; i ++) saRank[sa[i]] = tmp[i];
            if (tmp[strLen-1] == strLen-1) break;
        }
        build_lcp(s);
    }
};
int n;
string s[2];
suffixArray suff;
ll hashCode[2][300000], pBase[300000];
void prepHash(){
    pBase[0] = 1;
    for(int i=1;i<300000;i++)
        pBase[i] = pBase[i-1] * base % mod;
 
    hashCode[0][0] = s[0][0] - 'a' + 1;
    hashCode[1][0] = s[1][0] - 'a' + 1;
    for(int i=1;i<n;i++)
        hashCode[0][i] = (hashCode[0][i-1] + pBase[i] * (s[0][i] - 'a' + 1)) % mod,
        hashCode[1][i] = (hashCode[1][i-1] + pBase[i] * (s[1][i] - 'a' + 1)) % mod;
}
bool checkPalindrome(int l1,int r1){
    int l2 = n-1-r1;
    int r2 = n-1-l1;
    ll val1 = (hashCode[0][r1] - (l1 == 0 ? 0 : hashCode[0][l1-1]) + mod) % mod;
    ll val2 = (hashCode[1][r2] - (l2 == 0 ? 0 : hashCode[1][l2-1]) + mod) % mod;
    val1 = val1 * pBase[max(0, r2 - r1)] % mod;
    val2 = val2 * pBase[max(0, r1 - r2)] % mod;
    return val1 == val2;
}
 
long long ans;
 
long long solve(int p, int sz) {
    int id = suff.saRank[p];
    int l = id;
    if(n <= ans / sz) return 0;
    for(int i = 18; i >= 0; --i) {
        int cur = l - (1 << i);
        if(cur < 0) continue;
        if(suff.lcp[cur][i] < sz) {
            if((n - cur) <= ans / sz) return 0;
        }
        else l = cur;
    }
    int r = id;
    for(int i = 18; i >= 0; --i) {
        if(suff.lcp[r][i] < sz) {
            int cur = min(n - 1, r + (1 << i));
            if((cur - l + 1) <= ans / sz) return 0;
        }
        else r = min(n - 1, r + (1 << i));
    }
    return 1LL * sz * (r - l + 1);
}
 
int main(){
    prepLg2(300000);
    iostream::sync_with_stdio(0);
    cin >> s[0];
    n = s[0].size();
    s[1] = s[0];
    reverse(s[1].begin(), s[1].end());
    suff.build(s[0]);
    prepHash();
    int sz0, sz1;
    sz0 = 0, sz1 = 1;
    ans = 0;
    //return 0;
    for(int i = n - 1; i >= 0; --i) {
        int p0 = i + 2 * sz0 - 1; 
        int p1 = i + 2 * sz1 - 2;
        if(p0 >= p1) ans = max(ans, solve(i, p0 - i + 1));
        else ans = max(ans, solve(i, p1 - i + 1));
        if(i == 0) continue;
        sz0++, sz1++;
        while(sz0) {
            p0 = i - 1 + 2 * sz0 - 1;
            if(!checkPalindrome(i - 1, p0)) sz0--;
            else break;
        }
        while(sz1) {
            p1 = i - 1 + 2 * sz1 - 2;
            if(!checkPalindrome(i - 1, p1)) sz1--;
            else break;
        }
    }
    cout << ans;
    //cout << setprecision(6) << fixed << clock() * 1000 / CLOCKS_PER_SEC << endl;
}

Compilation message

palindrome.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5244 KB Output is correct
2 Correct 15 ms 5244 KB Output is correct
3 Correct 15 ms 5244 KB Output is correct
4 Correct 14 ms 5244 KB Output is correct
5 Correct 19 ms 5372 KB Output is correct
6 Correct 16 ms 5372 KB Output is correct
7 Correct 14 ms 5372 KB Output is correct
8 Correct 12 ms 5372 KB Output is correct
9 Correct 12 ms 5372 KB Output is correct
10 Correct 26 ms 5372 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 14508 KB Output is correct
2 Correct 119 ms 14588 KB Output is correct
3 Correct 128 ms 14588 KB Output is correct
4 Correct 120 ms 14664 KB Output is correct
5 Correct 181 ms 14664 KB Output is correct
6 Correct 151 ms 14664 KB Output is correct
7 Correct 122 ms 14664 KB Output is correct
8 Correct 96 ms 14664 KB Output is correct
9 Correct 113 ms 14688 KB Output is correct
10 Correct 177 ms 14688 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 35332 KB Output is correct
2 Correct 403 ms 35460 KB Output is correct
3 Correct 458 ms 35460 KB Output is correct
4 Correct 390 ms 35460 KB Output is correct
5 Correct 776 ms 35460 KB Output is correct
6 Correct 454 ms 35844 KB Output is correct
7 Correct 443 ms 36032 KB Output is correct
8 Correct 394 ms 36356 KB Output is correct
9 Correct 408 ms 36652 KB Output is correct
10 Correct 774 ms 36964 KB Output is correct
11 Correct 613 ms 37264 KB Output is correct
12 Correct 423 ms 37548 KB Output is correct