oj.uz

Submission #267035

# Submission time Handle Problem Language Result Execution time Memory
267035 2020-08-15T17:32:29 Z uacoder123 Palindromes (APIO14_palindrome) C++14
73 / 100
 1000 ms 76288 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
string s;
lli n,co=0;
vi sa(300001),t1(300001),t2(300001),cnt(300001),c(300001);
lli r[300001],lcp[300001],lo[300001],sp[300001][20],d1[300001],d2[300001],le=0,ri=-1,ans=0;
lli cot(lli l,lli ri)
{
  lli left=r[l],rig=n-1,ans=l,ans1=0;
  while(left<=rig)
  {
    lli m1=(left+rig)/2,m;
    m=m1-1;
    lli ch=(m1==r[l])?(ri-l+1):(min(sp[r[l]][lo[m-r[l]+1]],sp[m-(1<<lo[m-r[l]+1])+1][lo[m-r[l]+1]]));
    if(ch>=(ri-l+1))
    {
      left=m1+1;
      ans=m1;
    }
    else
      rig=m1-1;
  }
  ans1+=ans-r[l]+1;
  left=0;
  rig=r[l];
  ans=r[l];
  while(left<=rig)
  {
    lli m1=(left+rig)/2,m;
    m=m1;
    lli ch=(m==r[l])?ri-l+1:min(sp[m][lo[r[l]-1-m+1]],sp[r[l]-1-(1<<lo[r[l]-1-m+1])+1][lo[r[l]-1-m+1]]);
    if(ch>=(ri-l+1))
    {
      rig=m1-1;
      ans=m1;
    }
    else
      left=m1+1;
  }
  ans1+=r[l]-ans;
  return ans1;
}
void cal()
{
  pair<char,lli> s1[n];
  for(lli i=0;i<n;++i)
    s1[i]=mp(s[i],i);
  sort(s1,s1+n);
  c[0]=0;
  co++;
  sa[0]=s1[0].S;
  for(lli i=1;i<n;++i)
  {
    if(s1[i].F!=s1[i-1].F)
      co++;
    c[s1[i].S]=co-1;
    sa[i]=s1[i].S;
  }
  for(lli k=1;(1<<(k-1))<n;++k)
  {
    for(lli i=0;i<n;++i)
    {
      cnt[i]=0;
      t1[i]=(sa[i]-(1<<(k-1))+n)%n;
    }
    for(lli i=0;i<n;++i)
      cnt[c[t1[i]]]++;
    for(lli i=1;i<co;++i)
      cnt[i]+=cnt[i-1];
    for(lli i=n-1;i>=0;--i)
      sa[--cnt[c[t1[i]]]]=t1[i];
    t2[sa[0]]=0;
    co=1;
    for(lli i=1;i<n;++i)
    {
      ii cur=mp(c[sa[i]],c[(sa[i]+(1<<k-1))]);
      ii prev=mp(c[sa[i-1]],c[(sa[i-1]+(1<<k-1))%n]);
      if(cur!=prev)
        co++;
      t2[sa[i]]=co-1;
    }
    swap(t2,c);
  }
  sa.erase(sa.begin());
  n--;
  for(lli i=0;i<n;++i)
    r[sa[i]]=i;
}
void cal1()
{
  lli k=0;
  for(lli i=0;i<n;++i)
  {
    if(r[i]==n-1)
    {
      k=0;
      continue;
    }
    lli j=sa[r[i]+1];
    while(i+k<n&&j+k<n&&s[i+k]==s[j+k])
      k++;
    lcp[r[i]]=k;
    if(k)
      k--;
  }
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>s;
  n=s.size();
  if(n==1)
  {
    cout<<1<<endl;
    exit(0);
  }
  s+="#";
  n++;
  cal();
  cal1();
  for(lli i=2;i<=n;++i)
    lo[i]=lo[i/2]+1;
  for(lli i=0;i<20;++i)
  {
    for(lli j=0;j<n;++j)
    {
      if(i==0)
      {
        sp[j][i]=lcp[j];
      }
      else if(j+(1LL<<i)<=n)
      {
        sp[j][i]=min(sp[j][i-1],sp[j+(1<<(i-1))][i-1]);
      }
    }
  }
  for(lli i=0;i<n;++i)
  {
    lli k=(i>ri)?1:min(ri-i+1,d1[le+ri-i]);
    ans=max(ans,cot(i,i));
    while(i+k<n&&i-k>=0&&s[i+k]==s[i-k])
    {
      ans=max(cot(i-k,i+k)*(2*k+1),ans);
      k++;
    }
    d1[i]=k;
    if(d1[i]+i-1>ri)
    {
      ri=d1[i]+i-1;
      le=i-d1[i]+1;
    }
  }
  le=0;
  ri=-1;
  for(lli i=0;i<n;++i)
  {
    lli k=(i>ri)?0:min(ri-i+1,d1[le+ri-i]);
    while(i+k<n&&i-k-1>=0&&s[i+k]==s[i-k-1])
    {
      ans=max(cot(i-k-1,i+k)*(2*k+2),ans);
      k++;
    }
    d2[i]=k;
    if(d2[i]+i-1>ri)
    {
      ri=d2[i]+i-1;
      le=i-d2[i];
    }
  }
  cout<<ans<<endl;
  return(0);
}

Compilation message

palindrome.cpp: In function 'void cal()':
palindrome.cpp:90:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   90 |       ii cur=mp(c[sa[i]],c[(sa[i]+(1<<k-1))]);
      |                                       ~^~
palindrome.cpp:9:29: note: in definition of macro 'mp'
    9 | #define mp(i,a) make_pair(i,a)
      |                             ^
palindrome.cpp:91:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   91 |       ii prev=mp(c[sa[i-1]],c[(sa[i-1]+(1<<k-1))%n]);
      |                                            ~^~
palindrome.cpp:9:29: note: in definition of macro 'mp'
    9 | #define mp(i,a) make_pair(i,a)
      |                             ^

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14208 KB Output is correct
2 Correct 17 ms 14336 KB Output is correct
3 Correct 18 ms 14208 KB Output is correct
4 Correct 17 ms 14208 KB Output is correct
5 Correct 19 ms 14208 KB Output is correct
6 Correct 20 ms 14208 KB Output is correct
7 Correct 17 ms 14208 KB Output is correct
8 Correct 19 ms 14208 KB Output is correct
9 Correct 19 ms 14336 KB Output is correct
10 Correct 35 ms 14208 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 33528 KB Output is correct
2 Correct 147 ms 33528 KB Output is correct
3 Correct 139 ms 33744 KB Output is correct
4 Correct 153 ms 33528 KB Output is correct
5 Correct 350 ms 33528 KB Output is correct
6 Correct 284 ms 33784 KB Output is correct
7 Correct 197 ms 33528 KB Output is correct
8 Correct 270 ms 33528 KB Output is correct
9 Correct 242 ms 33656 KB Output is correct
10 Correct 882 ms 33748 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 76032 KB Output is correct
2 Correct 530 ms 76288 KB Output is correct
3 Correct 448 ms 76160 KB Output is correct
4 Correct 503 ms 76160 KB Output is correct
5 Execution timed out 1064 ms 72960 KB Time limit exceeded
6 Halted 0 ms 0 KB -