oj.uz

Submission #716975

# Submission time Handle Problem Language Result Execution time Memory
716975 2023-03-31T14:58:26 Z onepunchac168 Palindromes (APIO14_palindrome) C++17
100 / 100
 698 ms 54768 KB 
// 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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 472 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 476 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 464 KB Output is correct
30 Correct 1 ms 464 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2356 KB Output is correct
2 Correct 10 ms 2260 KB Output is correct
3 Correct 10 ms 2260 KB Output is correct
4 Correct 10 ms 2352 KB Output is correct
5 Correct 12 ms 2252 KB Output is correct
6 Correct 11 ms 2260 KB Output is correct
7 Correct 11 ms 2260 KB Output is correct
8 Correct 9 ms 2344 KB Output is correct
9 Correct 8 ms 2332 KB Output is correct
10 Correct 10 ms 2260 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 17204 KB Output is correct
2 Correct 111 ms 17192 KB Output is correct
3 Correct 109 ms 17236 KB Output is correct
4 Correct 120 ms 17212 KB Output is correct
5 Correct 133 ms 17188 KB Output is correct
6 Correct 123 ms 17288 KB Output is correct
7 Correct 117 ms 17204 KB Output is correct
8 Correct 119 ms 17208 KB Output is correct
9 Correct 153 ms 17328 KB Output is correct
10 Correct 148 ms 17200 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 54632 KB Output is correct
2 Correct 384 ms 54656 KB Output is correct
3 Correct 360 ms 54644 KB Output is correct
4 Correct 359 ms 54648 KB Output is correct
5 Correct 519 ms 54656 KB Output is correct
6 Correct 409 ms 54768 KB Output is correct
7 Correct 402 ms 54648 KB Output is correct
8 Correct 403 ms 54652 KB Output is correct
9 Correct 467 ms 54636 KB Output is correct
10 Correct 556 ms 54740 KB Output is correct
11 Correct 354 ms 54760 KB Output is correct
12 Correct 698 ms 54636 KB Output is correct