Submission #648806

#	Time	Username	Problem	Language	Result	Execution time	Memory
648806		MrBrionix	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	10011 ms	101624 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(sa,0,sizeof(sa));
  memset(rnk,0,sizeof(rnk));
  memset(tmp,0,sizeof(tmp));
  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);
  }
}

vector<int> lcp_construction(string const& s, vector<int> const& p) {
    int n = s.size();
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++)
        rank[p[i]] = i;

    int k = 0;
    vector<int> lcp(n-1, 0);
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k])
            k++;
        lcp[rank[i]] = k;
        if (k)
            k--;
    }
    return lcp;
}

void solve(){
	string s;
	int n;
	cin>>s;
	n=s.size();
	suffix_array(n,s);
	lcp_array(n,s);
	//vector<int> p(n);
	//for(int i=0;i<n;i++)p[i]=sa[i];
	//auto x = lcp_construction(s,p);
	//for(int i=0;i<n-1;i++)lcp[i]=x[i];
	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 function 'void solve()':
palindromic.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i=0;i<s.size()/2;i++){
      |              ~^~~~~~~~~~~
palindromic.cpp:96:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  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