Submission #716975

#	Time	Username	Problem	Language	Result	Execution time	Memory
716975		onepunchac168	Palindromes (APIO14_palindrome)	C++17	100 / 100	698 ms	54768 KiB

palindrome

// created by Dinh Manh Hung
// onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM
// Grandmaster go go

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("sse4,avx2,fma")
#define task "palindrome"
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert

typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
const long long mod=978846151;
const long long base=29;
const long long mod1=1e9+9;
const long long base1=31;
const int maxn=1e6+5;
//const int mod=1e9+7;
const char nl = '\n';
inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = xo * 10 + co - '0';
    return xo;
}

void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}
/* END OF TEMPLATE*/

// ================= Solution =================//

ll q;
string ss;
ll n;
long long T[600005];
long long F[600005];
ll Tb[600005];
ll Fb[600005];
ll id[600005];
ii lcp[600005];
ll res;
struct SuffixArray {
  static const int maxn = 6e5 + 5;
  static const char sep = '$';

  int n;
  char s[maxn];
  int sa[maxn], ra[2][maxn];
  int lcp[maxn];

  void build(string t) {
    n=t.size();
    for (int i=0;i<n;i++)
    {
        s[i]=t[i];
    }
    for (int i = 0; i < n; i++) {
      sa[i] = i, ra[0][i] = 0, ra[1][i] = s[i] + 1;
    }
    for (int d = 1; radixsort(); d <<= 1) {
      for (int i = 0; i < n; i++) {
        if (i + d < n) {
          ra[1][i] = ra[0][i + d] + 1;
        } else {
          ra[1][i] = 0;
        }
      }
    }
    buildlcp();
  }

  int radixsort() {
    static int p[maxn];
    static int tmpsa[maxn];
    static int tmpra[maxn];
    int mx = max(1024, n) + 1;
    for (int step = 1; step >= 0; step--) {
      fill_n(p, mx, 0);
      for (int i = 0; i < n; i++) {
        p[ra[step][i] + 1]++;
        tmpsa[i] = sa[i];
      }
      partial_sum(p, p + mx, p);
      for (int i = 0; i < n; i++) {
        sa[p[ra[step][tmpsa[i]]]++] = tmpsa[i];
      }
    }
    int ptr = 0;
    tmpra[sa[0]] = ptr;
    for (int i = 1; i < n; i++) {
      int u = sa[i - 1];
      int v = sa[i];
      if (ra[0][u] < ra[0][v] || ra[1][u] < ra[1][v]) {
        ptr++;
      }
      tmpra[v] = ptr;
    }
    for (int i = 0; i < n; i++)
      ra[0][i] = tmpra[i];
    return ptr < n - 1;
  }

  void buildlcp() {
    for (int i = 0, k = 0; i < n; i++) {
      if (!ra[0][i])
        lcp[ra[0][i]] = 0;
      else {
        for (int j = sa[ra[0][i] - 1]; s[i + k] == s[j + k] && s[i + k] != sep;
             k++)
          ;
        lcp[ra[0][i]] = k;
        k = max(k - 1, 0);
      }
    }
  }
} sta;
ii HASH(int u,int v)
{
    return {(T[v]-T[u-1]*F[v-u+1]+mod*mod)%mod,(Tb[v]-Tb[u-1]*Fb[v-u+1]+mod1*mod1)%mod1};
}
ll LCP(int u,int v)
{
    if (u>v)
    {
        swap(u,v);
    }
    ll kq=0;
    int lefta=1;int righta=n-v+1;
    while (lefta<=righta)
    {
        int mid=(lefta+righta)/2;
        if (HASH(u,u+mid-1)==HASH(v,v+mid-1))
        {
            kq=mid;
            lefta=mid+1;
        }
        else righta=mid-1;
    }
    return kq;
}
bool cmp(int u,int v)
{
    int cnt=LCP(u,v);
    return ss[u+cnt]<ss[v+cnt];
}
struct DSU{
    ll lab[600005];
    ll sz[600005];
    void makeset(int u)
    {
        lab[u]=-1;
        sz[u]=1;
    }
    ll findset(int u)
    {
        if (lab[u]<0){return u;}
        return lab[u]=findset(lab[u]);
    }
    void Union(int r,int s)
    {
        if (lab[r]>lab[s])
        {
            swap(r,s);
        }
        lab[r]+=lab[s];
        lab[s]=r;
        sz[r]+=sz[s];
    }
};
DSU dsu;
vector<int> manacher_odd(string sa) {
    int na = sa.size();
    sa = "$" + sa + "^";
    vector<int> p(na + 2);
    int l = 1, r = 1;
    for(int i = 1; i <= na; i++) {
        p[i] = max(0, min(r - i, p[l + (r - i)]));
        while(sa[i - p[i]] == sa[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<ll> manacher(string sa) {
    string t;
    for(auto c: sa) {
        t.pb('#');
        t.pb(c);
    }
    auto res = manacher_odd(t + "#");
    return vector<ll>(begin(res) + 1, end(res) - 1);
}
ll ip[600005];
ll Ta[600005*4];
void update(int node,int l,int r ,int u,ll val)
{
    if (u>r||u<l)
    {
        return;
    }
    if (l==r)
    {
        Ta[node]=val;
        return;
    }
    update(node*2,l,(l+r)/2,u,val);
    update(node*2+1,(l+r)/2+1,r,u,val);
    Ta[node]=min(Ta[node*2],Ta[node*2+1]);
}
vector <ll> T1;
ll query(int node,int l,int r,int u,int v,ll val)
{
    if (l>v||r<u)
    {
        return -1;
    }
    if (Ta[node]>=val)
    {
        return -1;
    }
    if (l==r)
    {
        return l;
    }
    int mid=(l+r)/2;
    int res=-1;
    if (Ta[node*2+1]<val)
    {
        res=query(node*2+1,mid+1,r,u,v,val);
    }
    if (res==-1)
    {
        res=query(node*2,l,mid,u,v,val);
    }
    return res;
}
ll coderneverdie(int id,int limit)
{
    ll aa=query(1,1,T1.size(),id,limit,id);
    return aa-id+1;
}
void optmushnpr()
{
    cin>>ss;
    sta.build(ss);
    ll ss_sum=0;
    n=ss.size();
    T1=manacher(ss);
    ll dem=0;
    for (int i=0;i<T1.size();i+=2)
    {
        dem++;
        ip[dem]=i+1;
    }
    for (int i=0;i<T1.size();i++)
    {
        update(1,1,T1.size(),i+1,i+1-T1[i]);
    }
    ss=' '+ss;
    T[0]=0;
    F[0]=1;
    Tb[0]=0;
    Fb[0]=1;
    res=1e9+5;
    for (int i=1;i<=n;i++)
    {
        T[i]=(T[i-1]*base+ss[i]-'a'+1)%mod;
        F[i]=(F[i-1]*base)%mod;
        Tb[i]=(Tb[i-1]*base1+ss[i]-'a'+1)%mod1;
        Fb[i]=(Fb[i-1]*base1)%mod1;
        dsu.makeset(i);
        ll a1=ip[i];
        ll a2=ip[n];
        a2=a1+((a2-a1)/2);
        ss_sum=max(ss_sum,coderneverdie(a1,a2));
    }
    //sort (id+1,id+n+1,cmp);
    for (int i = 0; i < sta.n; i++)
    {
        id[sta.ra[0][i]+1]=i+1;
    }
    for (int i=1;i<=n-1;i++)
    {
        //assert(id[i]!=0||id[i+1]!=0);
        //assert(cmp(id[i],id[i+1])==true);
        lcp[i].fi=LCP(id[i],id[i+1]);
        lcp[i].se=i;
    }
    sort (lcp+1,lcp+n);

    for (int i=n-1;i>=1;i--)
    {
        ii aa=lcp[i];
        if (aa.fi==0)
        {
            break;
        }
        int r=dsu.findset(id[aa.se]);
        int s=dsu.findset(id[aa.se+1]);
        if (r!=s)
        {
            dsu.Union(r,s);
        }
        //cout<<aa.fi<<" "<<res<<" "<<id[aa.se]<<" "<<id[aa.se+1]<<'\n';
        ll opt=dsu.findset(id[aa.se]);
        ll a1=ip[id[aa.se]];
        ll a2=ip[id[aa.se]+aa.fi-1];
        a2=a1+((a2-a1)/2);
        ll ansa=coderneverdie(a1,a2);
        ll po=dsu.sz[opt];
        ss_sum=max(ss_sum,ansa*po);
    }
    cout<<ss_sum;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(task".inp","r")){
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);}
    int t;
    t=1;
    while (t--){optmushnpr();}
}

// goodbye see ya

Compilation message (stderr)

palindrome.cpp: In function 'void optmushnpr()':
palindrome.cpp:285:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  285 |     for (int i=0;i<T1.size();i+=2)
      |                  ~^~~~~~~~~~
palindrome.cpp:290:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  290 |     for (int i=0;i<T1.size();i++)
      |                  ~^~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:356:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  356 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:357:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  357 |     freopen(task".out","w",stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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