Submission #47206

#	Time	Username	Problem	Language	Result	Execution time	Memory
47206		evenharder	Palindromes (APIO14_palindrome)	C++11	73 / 100	1094 ms	69232 KiB

palindrome

#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 clen = std::min({lcp_val(x,y), ma[x]+1, ma[y]+1});
        char chx = clen <= ma[x] /*&& x+clen < s_.length()*/ ? s_[x+clen] : 0;
        char chy = clen <= ma[y] /*&& 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;

    s_.push_back('\0');
    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 (stderr)

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:174: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 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27