Submission #602033

#	Time	Username	Problem	Language	Result	Execution time	Memory
602033		ace5	Palindromes (APIO14_palindrome)	C++17	73 / 100	302 ms	131072 KiB

palindrome

#include <bits/stdc++.h>
#include <random>
#include <ext/rope>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

const int alf = 26;
const int maxn = 300005;

struct sf
{
    sf(){len = 0;link = 0;l = 0;c = 0;};
    int go[alf];
    int len,link;
    int l;
    int c;
};


vector<sf> sa(2*maxn);

void init()
{
    sa[0].link = -1;
    sa[0].len = 0;
    sa[0].c = 0;
    sa[0].l = -1;
    for(int i = 0;i < sa.size();++i)
    {
        for(int j = 0;j < alf;++j)
            sa[i].go[j] = -1;
    }
    return ;

}

int last = 0,sz = 1;


void add(char c)
{
    int x = c-'a';
    int cur = sz++;
    sa[cur].len = sa[last].len+1;
    sa[cur].l = 0;
    sa[cur].c = 1;
    int p = last;
    while(p != -1 && sa[p].go[x] == -1)
    {
        sa[p].go[x] = cur;
        p = sa[p].link;
    }
   // cout << p << ' ';
    if(p == -1)
    {
        sa[cur].link = 0;
    }
    else
    {
        int q = sa[p].go[x];
        if(sa[p].len == sa[q].len-1)
        {
            sa[cur].link = q;
        }
        else
        {
            int clone = sz++;
            sa[clone].len = sa[p].len + 1;
            sa[clone].link = sa[q].link;
            for(int i = 0;i < alf;++i)
                sa[clone].go[i] = sa[q].go[i];
            sa[clone].c = 0;
            sa[clone].l = sa[q].l + sa[q].len - sa[p].len - 1;
            sa[q].link = sa[cur].link = clone;
            int cp = p;
            while(sa[cp].go[x] == q)
            {
                sa[cp].go[x] = clone;
                cp = sa[cp].link;
            }
        }
    }
    last = cur;
    return ;
}
vector<int64_t> phash(maxn),shash(maxn),st(maxn);
const int64_t mod = int64_t(1e9)+7,p = 101;

bool qp(int64_t l,int64_t r)
{
   // cout << shash[l] << ' ' << ((shash[r+1]*(st[r-l+1]))%mod) << "\n";
    if((phash[r+1]-((phash[l]*(st[r-l+1]))%mod)+mod)%mod == (shash[l]-((shash[r+1]*(st[r-l+1]))%mod)+mod)%mod)
        return true;
    else
        return false;
}

struct ev
{
    ev(){t =0;c = 0;oc = 0;l = 0;};
    ev(int64_t  _t,bool _c,int64_t _oc,int64_t _l){t =_t;c = _c;oc = _oc;l = _l;};
    int64_t t;
    bool c;
    int64_t oc;
    int64_t l;
    bool operator <(const ev& other)const
    {
        if(t != other.t)
            return t < other.t;
        if(c == other.c)
            return oc < other.oc;
        else
        {
            if(c == 0)
            {
                if(oc == 0)
                    return 1;
                else
                    return 0;
            }
            else
            {
                if(other.oc == 0)
                    return 0;
                else
                    return 1;
            }
        }
    }
};




int main()
{
    st[0] = 1;
    for(int i =1;i < maxn;++i)
    {
        st[i] = (p*st[i-1])%mod;
    }
    string s;
    cin >> s;
    int n = s.size();
    init();
    for(int i = 0;i < s.size();++i)
    {
       // cout << 1;
        add(s[i]);
    }
    vector<pair<int,int>> tr;
    for(int i = 1;i < sz;++i)
    {
        tr.push_back({sa[i].len,i});
    }
    sort(tr.rbegin(),tr.rend());
    for(int i = 0;i < sz-1;++i)
    {
        sa[sa[tr[i].second].link].c += sa[tr[i].second].c;
    }
   // cout << 1;
    int64_t thash = 0;
    phash[0] = thash;
    for(int i = 0;i < s.size();++i)
    {
        thash *= p;
        thash += s[i];
        thash = thash%mod;
        phash[i+1] = thash;
    }
    thash = 0;
    shash[n] = thash;
    for(int i = int(s.size())-1;i >= 0;--i)
    {
        thash *= p;
        thash += s[i];
        thash = thash%mod;
        shash[i] = thash;
    }
    vector<ev> lg;

    for(int i = 1;i < sz;++i)
    {
       // cout << sa[i].link << ' ' << sa[i].l << ' ' << sa[i].len << ' ' << sa[i].c << "\n";
        lg.push_back(ev(sa[i].l + sa[i].len - 1,1,sa[i].c,sa[i].l));
    }
    for(int i = 0;i < n;++i)
    {
        int l = max(0,i-(n-i)+1),r = i;
        while(l < r)
        {
            int m = (l+r)/2;
            if(qp(m,2*i-m))
                r = m;
            else
                l = m+1;
        }
        //cout << l << ' ' << i << "\n";
        lg.push_back(ev(i,0,0,2*i));
        lg.push_back(ev(2*i-l,0,1,2*i));
    }
    for(int i = 1;i < n;++i)
    {
        int l = max(1,i-(n-i)+1),r = i+1;
        while(l < r)
        {
            int m = (l+r)/2;
            if(qp(m-1,2*i-m))
                r = m;
            else
                l = m+1;
        }
        //cout << l << ' ' << i << "\n";
        if(l <= i)
        {
            lg.push_back(ev(i,0,0,2*i-1));
            lg.push_back(ev(2*i-l,0,1,2*i-1));

        }
    }
    sort(lg.begin(),lg.end());
    int64_t ans = 0;
    set<int> ss;
    for(int i = 0;i < lg.size();++i)
    {
        ev x = lg[i];
        if(x.c == 0)
        {
            if(x.oc == 0)
            {
                ss.insert(x.l);
            }
            else
                ss.erase(x.l);
        }
        else
        {
            auto it = ss.lower_bound((x.l+x.t));
            int64_t xx = (*it);
         //   cout << xx << ' ' << x.l << ' ' << x.t << "\n";
            if(xx%2 == 0)
                ans = max(ans,((x.t-(xx/2))*2+1)*(x.oc));
            else
                ans = max(ans,((x.t-(xx/2))*2)*(x.oc));
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void init()':
palindrome.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sf>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0;i < sa.size();++i)
      |                   ~~^~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:151:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i = 0;i < s.size();++i)
      |                   ~~^~~~~~~~~~
palindrome.cpp:169:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     for(int i = 0;i < s.size();++i)
      |                   ~~^~~~~~~~~~
palindrome.cpp:229:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ev>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     for(int i = 0;i < lg.size();++i)
      |                   ~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27