Submission #648815

#	Time	Username	Problem	Language	Result	Execution time	Memory
648815		MrBrionix	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	135 ms	131072 KiB

palindromic

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

constexpr int MAXN = 1 << 20, LOGN = 21;
int table[LOGN][MAXN];
void build(int N, int* V) {
  copy(V, V + 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) {
  if(l>r)swap(l,r);
  int k = 31 - __builtin_clz(r - l); // [l, r)
  return min(table[k][l], table[k][r-(1 << k)]);
}

int sa[MAXN], rnk[2*MAXN], lcp[MAXN], tmp[MAXN], invsa[MAXN];
void suffix_array(int N, const string& S) {
  memset(rnk,0,sizeof(rnk));
  for (int i = 0; i < N; i++) {
    sa[i] = i, rnk[i] = S[i];
  }
  for (int k = 1; k < N; k *= 2) {
    sort(sa, sa + N, [&](int a, int b) {
      return tie(rnk[a],rnk[a+k]) < tie(rnk[b],rnk[b+k]);
    });
    tmp[sa[0]] = 1;
    for (int i = 1; i < N; i++) {
      tmp[sa[i]] = tmp[sa[i-1]] + (rnk[sa[i]] !=
        rnk[sa[i-1]] || rnk[sa[i]+k] != rnk[sa[i-1]+k]);
    }
    copy(tmp, tmp + N, rnk);
    if (rnk[sa[N - 1]] == N) break;
  }
}
void lcp_array(int N, const string& S) {
  for (int i = 0, k = 0; i < N; i++) {
    int j = sa[rnk[i]];
    while (i+k < N && j+k < N && S[i+k] == S[j+k]) k++;
    lcp[rnk[i] - 1] = k;
    k = max(k - 1, 0);
  }
}

const int N = MAXN;

void induced_sort(const vector<int> &vec, int val_range, vector<int> &SA, const vector<bool> &sl, const vector<int> &lms_idx) {
  vector<int> l(val_range, 0), r(val_range, 0);
  for (int c : vec) {
    if (c + 1 < val_range) ++l[c + 1];
    ++r[c];
  }
  partial_sum(l.begin(), l.end(), l.begin());
  partial_sum(r.begin(), r.end(), r.begin());
  fill(SA.begin(), SA.end(), -1);
  for (int i = lms_idx.size() - 1; i >= 0; --i)
    SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
  for (int i : SA)
    if (i >= 1 && sl[i - 1]) {
      SA[l[vec[i - 1]]++] = i - 1;
    }
  fill(r.begin(), r.end(), 0);
  for (int c : vec)
    ++r[c];
  partial_sum(r.begin(), r.end(), r.begin());
  for (int k = SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
    if (i >= 1 && !sl[i - 1]) {
      SA[--r[vec[i - 1]]] = i - 1;
    }
}

vector<int> SA_IS(const vector<int> &vec, int val_range) {
  const int n = vec.size();
  vector<int> SA(n), lms_idx;
  vector<bool> sl(n);
  sl[n - 1] = false;
  for (int i = n - 2; i >= 0; --i) {
    sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
    if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
  }
  reverse(lms_idx.begin(), lms_idx.end());
  induced_sort(vec, val_range, SA, sl, lms_idx);
  vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
  for (int i = 0, k = 0; i < n; ++i)
    if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
      new_lms_idx[k++] = SA[i];
    }
  int cur = 0;
  SA[n - 1] = cur;
  for (size_t k = 1; k < new_lms_idx.size(); ++k) {
    int i = new_lms_idx[k - 1], j = new_lms_idx[k];
    if (vec[i] != vec[j]) {
      SA[j] = ++cur;
      continue;
    }
    bool flag = false;
    for (int a = i + 1, b = j + 1;; ++a, ++b) {
      if (vec[a] != vec[b]) {
        flag = true;
        break;
      }
      if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
        flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
        break;
      }
    }
    SA[j] = (flag ? ++cur : cur);
  }
  for (size_t i = 0; i < lms_idx.size(); ++i)
    lms_vec[i] = SA[lms_idx[i]];
  if (cur + 1 < (int)lms_idx.size()) {
    auto lms_SA = SA_IS(lms_vec, cur + 1);
    for (size_t i = 0; i < lms_idx.size(); ++i) {
      new_lms_idx[i] = lms_idx[lms_SA[i]];
    }
  }
  induced_sort(vec, val_range, SA, sl, new_lms_idx);
  return SA;
}
vector<int> suffix_array(const string &s, const int LIM = 128) {
  vector<int> vec(s.size() + 1);
  copy(begin(s), end(s), begin(vec));
  vec.back() = '$';
  auto ret = SA_IS(vec, LIM);
  ret.erase(ret.begin());
  return ret;
}
struct SuffixArray {
  int n;
  string s;
  vector<int> sa, rank, lcp;
  static const int LG = 21;
  vector<vector<int>> t;
  vector<int> lg;
  SuffixArray() {}
  SuffixArray(string _s) {
    n = _s.size();
    s = _s;
    sa = suffix_array(s);
    rank.resize(n);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    costruct_lcp();
    prec();
    build();
  }
  void costruct_lcp() {
    int k = 0;
    lcp.resize(n - 1, 0);
    for (int i = 0; i < n; i++) {
      if (rank[i] == n - 1) {
        k = 0;
        continue;
      }
      int j = sa[rank[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k])  k++;
      lcp[rank[i]] = k;
      if (k)  k--;
    }
  }
  void prec() {
    lg.resize(n, 0);
    for (int i = 2; i < n; i++) lg[i] = lg[i / 2] + 1;
  }
  void build() {
    int sz = n - 1;
    t.resize(sz);
    for (int i = 0; i < sz; i++) {
      t[i].resize(LG);
      t[i][0] = lcp[i];
    }
    for (int k = 1; k < LG; ++k) {
      for (int i = 0; i + (1 << k) - 1 < sz; ++i) {
        t[i][k] = min(t[i][k - 1], t[i + (1 << (k - 1))][k - 1]);
      }
    }
  }
  int query(int l, int r) { // minimum of lcp[l], ..., lcp[r]
    int k = lg[r - l + 1];
    return min(t[l][k], t[r - (1 << k) + 1][k]);
  }
  int get_lcp(int i, int j) { // lcp of suffix starting from i and j
    if (i == j) return n - i;
    int l = rank[i], r = rank[j];
    if (l > r) swap(l, r);
    return query(l, r - 1);
  }
  int lower_bound(string &t) {
    int l = 0, r = n - 1, k = t.size(), ans = n;
    while (l <= r) {
      int mid = l + r >> 1;
      if (s.substr(sa[mid], min(n - sa[mid], k)) >= t) ans = mid, r = mid - 1;
      else l = mid + 1;
    }
    return ans;
  }
  int upper_bound(string &t) {
    int l = 0, r = n - 1, k = t.size(), ans = n;
    while (l <= r) {
      int mid = l + r >> 1;
      if (s.substr(sa[mid], min(n - sa[mid], k)) > t) ans = mid, r = mid - 1;
      else l = mid + 1;
    }
    return ans;
  }
  // occurrences of s[p, ..., p + len - 1]
  pair<int, int> find_occurrence(int p, int len) {
    p = rank[p];
    pair<int, int> ans = {p, p};
    int l = 0, r = p - 1;
    while (l <= r) {
      int mid = l + r >> 1;
      if (query(mid, p - 1) >= len) ans.first = mid, r = mid - 1;
      else l = mid + 1;
    }
    l = p + 1, r = n - 1;
    while (l <= r) {
      int mid = l + r >> 1;
      if (query(p, mid - 1) >= len) ans.second = mid, l = mid + 1;
      else r = mid - 1;
    }
    return ans;
  }

};

void solve(){
	string s;
	int n;
	cin>>s;
	n=s.size();
	SuffixArray tmp(s);
	//suffix_array(n,s);
	for(int i=0;i<n;i++)rnk[i]=tmp.rank[i]+1;
	for(int i=0;i<n;i++)sa[i]=tmp.sa[i];
	lcp_array(n,s);
	build(n-1,lcp);
	for(int i=0;i<n;i++)invsa[sa[i]]=i;
	
	int last=0,ans=0;
	for(int i=0;i<s.size()/2;i++){
		if(s[last]==s[s.size()-1-i] && query(invsa[last],invsa[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 member function 'int SuffixArray::lower_bound(std::string&)':
palindromic.cpp:194:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  194 |       int mid = l + r >> 1;
      |                 ~~^~~
palindromic.cpp: In member function 'int SuffixArray::upper_bound(std::string&)':
palindromic.cpp:203:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  203 |       int mid = l + r >> 1;
      |                 ~~^~~
palindromic.cpp: In member function 'std::pair<int, int> SuffixArray::find_occurrence(int, int)':
palindromic.cpp:215:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  215 |       int mid = l + r >> 1;
      |                 ~~^~~
palindromic.cpp:221:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  221 |       int mid = l + r >> 1;
      |                 ~~^~~
palindromic.cpp: In function 'void solve()':
palindromic.cpp:244:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  244 |  for(int i=0;i<s.size()/2;i++){
      |              ~^~~~~~~~~~~
palindromic.cpp:251:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |  if(last!=s.size()/2 || s.size()%2==1)ans++;
      |     ~~~~^~~~~~~~~~~~

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