oj.uz

Submission #839224

# Submission time Handle Problem Language Result Execution time Memory
839224 2023-08-29T08:49:27 Z MrBrionix Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 596 ms 101972 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 5 ms 1132 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct
12 Correct 4 ms 1088 KB Output is correct
13 Correct 5 ms 980 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 5 ms 1132 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct
12 Correct 4 ms 1088 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 596 ms 101972 KB Output is correct
15 Correct 405 ms 97520 KB Output is correct
16 Correct 504 ms 94272 KB Output is correct
17 Correct 491 ms 51092 KB Output is correct