Submission #839224

#	Time	Username	Problem	Language	Result	Execution time	Memory
839224		MrBrionix	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	596 ms	101972 KiB

palindromic

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

constexpr int MAXN = 1 << 20, LOGN = 21;
int table[LOGN][MAXN];
void build(int N, vector<int> &V) {
  copy(V.begin(), V.begin()+N, table[0]);
  for (int j = 1; j < LOGN; j++) {
    for (int i = 0; i + (1 << j) <= N; i++) {
      table[j][i]=min(table[j-1][i],
        table[j-1][i+(1<<j)/2]);
    }
  }
}
int query(int l, int r) {
  int k = 31 - __builtin_clz(r - l); // [l, r)
  return min(table[k][l], table[k][r-(1 << k)]);
}

using ll = long long;
#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vpi = V<pair<int,int>>;
#define sz(x) int((x).size())
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define each(a,x) for (auto& a: x)
#define all(x) begin(x), end(x)
template<class T> bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0; } // set $a = \min(a,b)$

vi sa_is(const vi& s, int upper) { //Suffix array $\mathcal{O}(n)$
  int n=sz(s);if(!n)return {}; vi sa(n);vector<bool> ls(n);
  for(int i=n-1;i--;)ls[i]=s[i]==s[i+1]?ls[i+1]:s[i]<s[i+1];
  vi sum_l(upper), sum_s(upper);
  F0R(i,n) (ls[i] ? sum_l[s[i]+1] : sum_s[s[i]])++;
  F0R(i,upper) { 
    if (i) sum_l[i] += sum_s[i-1];
    sum_s[i] += sum_l[i];
  }
  auto induce = [&](const vi& lms) {
    fill(all(sa),-1); vi buf = sum_s;
    for (int d: lms) if (d != n) sa[buf[s[d]]++] = d;
    buf = sum_l; sa[buf[s[n-1]]++] = n-1;
    F0R(i,n){//do l-type in increasing order,suf[v]>suf[v+1]
      int v = sa[i]-1;
      if (v >= 0 && !ls[v]) sa[buf[s[v]]++] = v;
    }
    buf = sum_l;
    for(int i=n-1; i>=0; --i){
      int v=sa[i]-1;//s-type in decr. order,suf[v]<suf[v+1]
      if (v >= 0 && ls[v]) sa[--buf[s[v]+1]] = v;
    }
  };
  vi lms_map(n+1,-1), lms; int m = 0;
  FOR(i,1,n)if(!ls[i-1] && ls[i])lms_map[i]=m++,lms.pb(i);
  induce(lms);vi sorted_lms;// sorts LMS prefixes
  each(v,sa)if(lms_map[v]!=-1)sorted_lms.pb(v);
  vi rec_s(m); int rec_upper = 0; // smaller subproblem
  FOR(i,1,m){ //compare two lms substrings in sorted order
    int l=sorted_lms[i-1], r=sorted_lms[i]; bool same = 0;
    int end_l = lms_map[l]+1 < m ? lms[lms_map[l]+1] : n;
    int end_r = lms_map[r]+1 < m ? lms[lms_map[r]+1] : n;
    if(end_l-l == end_r-r){
      for (;l < end_l && s[l] == s[r]; ++l,++r);
      if (l != n && s[l] == s[r]) same = 1;
    }
    rec_s[lms_map[sorted_lms[i]]] = (rec_upper += !same);
  }
  vi rec_sa = sa_is(rec_s,rec_upper+1);
  F0R(i,m) sorted_lms[i] = lms[rec_sa[i]];
  induce(sorted_lms); return sa;
}

struct SuffixArray { //tested with $n \leq 5\cdot 10^5$ (226 ms)
  string S; int N; vi sa, isa, lcp; //N=sz(S)+1=n+1
  void init(string _S) { //$\mathcal{O}(n\log n)$
    N=sz(S=_S)+1;vi s(N);FOR(i,0,N-1)s[i]=S[i]-'a';
    sa=sa_is(s,27);isa=vi(N);FOR(i,0,N)isa[sa[i]]=i;genLcp();}
  void genSa() { // sa has size sz(S)+1, sa[0]=sz(S)
    sa = isa = vi(N); sa[0] = N-1; iota(1+all(sa),0);
    sort(1+all(sa),[&](int a,int b){return S[a]<S[b];});
    FOR(i,1,N) { int a = sa[i-1], b = sa[i];
      isa[b] = i > 1 && S[a] == S[b] ? isa[a] : i; }
    for (int len = 1; len < N; len *= 2) { // currently
      // sorted by first len chars
      vi s(sa), is(isa), pos(N); iota(all(pos),0);
      each(t,s){
        int T=t-len;if(T>=0)sa[pos[isa[T]]++]=T;
      }
      FOR(i,1,N) {
        int a = sa[i-1], b = sa[i];
        // verify that nothing goes out of bounds
        isa[b] = is[a]==is[b]&&
        is[a+len]==is[b+len]?isa[a]:i;
      }
    }//sa[i]= indice (0-based) d'inizio i-esimo...
  }  //... prefisso più piccolo
  // isa[i] = x t.c. sa[x]=i
  //lcp[i]=lcp tra sa[i] e sa[i+1] ($0\leq i \leq n-1$)
  void genLcp(){
    lcp=vi(N-1); int h=0; //lcp[0]=lcp(sz(S),sa[1])=0
    F0R(b,N-1) { int a = sa[isa[b]-1];
      while (a+h < sz(S) && S[a+h] == S[b+h]) ++h;
      lcp[isa[b]-1] = h; if (h) h--; }
    build(N-1,lcp); // serve rmq (del booklet)
    //ma va modificato con vector<int>& anzichè int*
    //e V.begin() anzichè V
    //if we cut off first chars of two strings with...
  } //...lcp h then remaining portions still have lcp h-1
  //lcp of suffixes starting at a,b
  int getLCP(int a, int b){
    if (a == b) return sz(S)-a; // a,b sono 0-based
    int l = isa[a], r = isa[b]; if (l > r) swap(l,r);
    return query(l,r); // serve rmq (del booklet)
  }
};

void solve(){
  string s;
  int n;
  cin>>s;
  n=s.size();
  SuffixArray tmp;
  tmp.init(s);
  assert(tmp.lcp[0]==0);
  
  int last=0,ans=0;
  for(int i=0;i<s.size()/2;i++){
    if(s[last]==s[s.size()-1-i] && tmp.getLCP(last,s.size()-1-last-(i-last))>=(i-last+1)){
      last=i+1;
      ans+=2;
    }
  }
  
  if(last!=s.size()/2 || s.size()%2==1)ans++;
  cout<<ans<<"\n";
}

int main(){
  
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int t;
  cin>>t;
  
  while(t--)solve();
  
  return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:132:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for(int i=0;i<s.size()/2;i++){
      |               ~^~~~~~~~~~~
palindromic.cpp:139:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   if(last!=s.size()/2 || s.size()%2==1)ans++;
      |      ~~~~^~~~~~~~~~~~
palindromic.cpp:124:7: warning: variable 'n' set but not used [-Wunused-but-set-variable]
  124 |   int n;
      |       ^

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40