oj.uz

Submission #47193

# Submission time Handle Problem Language Result Execution time Memory
47193 2018-04-28T19:22:10 Z evenharder Palindromes (APIO14_palindrome) C++11
73 / 100
 1000 ms 69072 KB 
#include <iostream>
#include <ios>
#include <algorithm>
#include <string>
#include <vector>
#include <array>
#include <stack>

const int MAX_N = 600006;
std::vector<int> make_sa(const std::string& s)
{
    int n = s.length();
    std::vector<int> sa(n), g(n+1), ng(n+1);

    for(int i=0;i<n;i++)
    {
        sa[i] = i;
        g[i] = s[i];
    }
    g[n] = 0;

    int lim = std::max(128, n+1);
    for(int t=1;t<s.length();t<<=1)
    {
        auto cmp = [&] (int a, int b) {
            return g[a] != g[b] ? g[a] < g[b] : g[a+t] < g[b+t];
        };

        std::vector<int> cnt(lim), ind(lim+1);

        for(int i=0;i<n;i++) cnt[g[std::min(i+t, n)]]++;
        for(int i=1;i<lim;i++) cnt[i] += cnt[i-1];
        for(int i=n-1;i>=0;i--) ind[--cnt[g[std::min(i+t, n)]]] = i;

        for(int i=0;i<lim;i++) cnt[i] = 0;

        for(int i=0;i<n;i++) cnt[g[i]]++; // same as cnt[g[ind[i]]]++
        for(int i=1;i<lim;i++) cnt[i] += cnt[i-1];
        for(int i=n-1;i>=0;i--) sa[--cnt[g[ind[i]]]] = ind[i];

        ng[sa[0]] = 1;

        for(int i=1;i<n;i++)
        {
            ng[sa[i]] = ng[sa[i-1]];
            if(cmp(sa[i-1], sa[i])) ng[sa[i]]++;
        }
        g = ng;
    }
    return sa;
}

std::vector<int> make_lcp(const std::string& s, const std::vector<int>& sa)
{
    int n = s.length();
    std::vector<int> lcp(n+1);
    std::vector<int> rank(n);
    for(int i=0;i<n;i++)
        rank[sa[i]] = i;

    int len = 0;
    for(int i=0;i<n;i++)
    {
        if(rank[i])
        {
            int j = sa[rank[i]-1];
            int len_cap = n - std::max(i,j);
            while(len < len_cap && s[i+len] == s[j+len]) len++;
            lcp[rank[i]-1] = len;
        }
        if(len) len--;
    }
    return lcp;
}
long long int get_max_area(const std::vector<int>& v)
{
    std::stack<int> sh, sx;
    int n = v.size();
    long long int ans = 0;
    for(int i=0;i<=n;i++)
    {
        int val = i < n ? v[i] : 0;
        int last_x = i;
        while(!sh.empty() && sh.top() >= val)
        {
            ans = std::max(ans, 1LL * sh.top() * (i-sx.top()+1));
            last_x = sx.top();
            sh.pop();
            sx.pop();
        }
        sh.push(val);
        sx.push(last_x);
    }
    return ans;
}
std::string make_appended_str(const std::string& s)
{
    std::vector<char> v;
    for(int i=0;i<=s.length();i++)
    {
        v.push_back('_');
        if(i != s.length()) v.push_back(s[i]);
    }
    return std::string(v.begin(), v.end());
}
std::vector<int> manacher(const std::string& s)
{
    std::vector<int> ret(s.length());
    int r = -1;
    int p = -1;
    for(int i=0;i<s.length();i++)
    {
        if(i <= r) ret[i] = std::min(r-i, ret[2*p-i]);
        while(ret[i]+1 <= i && i+ret[i]+1 < s.length() &&
            s[i-ret[i]-1] == s[i+ret[i]+1])
                ret[i]++;
        if(i + ret[i] > r)
            r = i + ret[i], p = i;
    }
    return ret;
}

int spl[MAX_N+1];
int sp[20][MAX_N];
void set_sp(std::vector<int>& lcp)
{
    int n = lcp.size();
    for(int j=0;j<n;j++)
        sp[0][j] = lcp[j];
    for(int i=1;i<20;i++)
    {
        for(int j=1;j<=(1<<i);j++)
        {
            if((1<<i)+j <= MAX_N) spl[(1<<i)+j] = i;
        }
    }
    for(int i=0;i<19;i++)
    {
        for(int j=0;j<n;j++)
        {
            sp[i+1][j] = std::min(sp[i][j], sp[i][std::min(j+(1<<i), n-1)]);
        }
    }
}

long long int solve(std::string& s)
{
    std::string s_ = make_appended_str(s);
    std::vector<int> sa = make_sa(s_);
    std::vector<int> rank(sa.size());
    for(int i=0;i<sa.size();i++)
        rank[sa[i]] = i;
    std::vector<int> lcp = make_lcp(s_, sa);
    std::vector<int> ma = manacher(s_);

    set_sp(lcp);
    auto lcp_val = [&] (int x, int y)
    {
        x = rank[x];
        y = rank[y];
        if(x>y) std::swap(x,y);
        int len = y-x;
        int res = std::min(sp[spl[len]][x], sp[spl[len]][y-(1<<spl[len])]);
        return res;
    };
    auto cmp = [&] (int x, int y)
    {
        int len = y-x+ 1;
        int clen = std::min({lcp_val(x,y), ma[x]+1, ma[y]+1});
        char chx = clen != ma[x]+1 && x+clen < s_.length() ? s_[x+clen] : 0;
        char chy = clen != ma[y]+1 && y+clen < s_.length() ? s_[y+clen] : 0;
        return (chx != chy ? chx < chy : x<y);
    };
    std::vector<int> ord(s_.length());
    for(int i=0;i<s_.length();i++)
        ord[i] = i;

    std::sort(ord.begin(), ord.end(), cmp);

    std::vector<int> lcp_palin;
    for(int i=1;i<ord.size();i++)
    {
        int v = std::min({
            ma[ord[i-1]],
            ma[ord[i]],
            lcp_val(ord[i-1], ord[i])-1});
        lcp_palin.push_back(std::max(v,0));
    }

    return std::max(get_max_area(lcp_palin), (long long int)*std::max_element(ma.begin(), ma.end()));
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::string s;
    std::cin >> s;
    std::cout << solve(s);
}

Compilation message

palindrome.cpp: In function 'std::vector<int> make_sa(const string&)':
palindrome.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int t=1;t<s.length();t<<=1)
                 ~^~~~~~~~~~~
palindrome.cpp: In function 'std::__cxx11::string make_appended_str(const string&)':
palindrome.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<=s.length();i++)
                 ~^~~~~~~~~~~~
palindrome.cpp:102:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i != s.length()) v.push_back(s[i]);
            ~~^~~~~~~~~~~~~
palindrome.cpp: In function 'std::vector<int> manacher(const string&)':
palindrome.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.length();i++)
                 ~^~~~~~~~~~~
palindrome.cpp:114:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ret[i]+1 <= i && i+ret[i]+1 < s.length() &&
                                ~~~~~~~~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'long long int solve(std::__cxx11::string&)':
palindrome.cpp:151:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<sa.size();i++)
                 ~^~~~~~~~~~
palindrome.cpp: In lambda function:
palindrome.cpp:170:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         char chx = clen != ma[x]+1 && x+clen < s_.length() ? s_[x+clen] : 0;
                                       ~~~~~~~^~~~~~~~~~~~~
palindrome.cpp:171:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         char chy = clen != ma[y]+1 && y+clen < s_.length() ? s_[y+clen] : 0;
                                       ~~~~~~~^~~~~~~~~~~~~
palindrome.cpp:168:13: warning: unused variable 'len' [-Wunused-variable]
         int len = y-x+ 1;
             ^~~
palindrome.cpp: In function 'long long int solve(std::__cxx11::string&)':
palindrome.cpp:175:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s_.length();i++)
                 ~^~~~~~~~~~~~
palindrome.cpp:181:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<ord.size();i++)
                 ~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5304 KB Output is correct
2 Correct 22 ms 5304 KB Output is correct
3 Correct 22 ms 5304 KB Output is correct
4 Correct 18 ms 5304 KB Output is correct
5 Correct 20 ms 5304 KB Output is correct
6 Correct 21 ms 5432 KB Output is correct
7 Correct 18 ms 5432 KB Output is correct
8 Correct 23 ms 5432 KB Output is correct
9 Correct 23 ms 5432 KB Output is correct
10 Correct 22 ms 5432 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 24820 KB Output is correct
2 Correct 189 ms 24880 KB Output is correct
3 Correct 151 ms 24880 KB Output is correct
4 Correct 201 ms 24880 KB Output is correct
5 Correct 318 ms 24880 KB Output is correct
6 Correct 311 ms 24892 KB Output is correct
7 Correct 238 ms 24952 KB Output is correct
8 Correct 427 ms 24952 KB Output is correct
9 Correct 320 ms 24952 KB Output is correct
10 Correct 327 ms 24956 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 68996 KB Output is correct
2 Correct 596 ms 69072 KB Output is correct
3 Correct 513 ms 69072 KB Output is correct
4 Correct 615 ms 69072 KB Output is correct
5 Execution timed out 1082 ms 69072 KB Time limit exceeded
6 Halted 0 ms 0 KB -