Submission #675696

#TimeUsernameProblemLanguageResultExecution timeMemory
675696MrBrionixPalindromic Partitions (CEOI17_palindromic)C++17
100 / 100
5548 ms98876 KiB
#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)]); } template<class T> using V = vector<T>; using vi = V<int>; #define sz(x) int((x).size()) #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) struct SuffixArray { 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; genSa(); genLcp(); } //tested with $t\leq 10,n \leq 10^6$ (5.41 sec) 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 //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) //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:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<s.size()/2;i++){
      |                 ~^~~~~~~~~~~
palindromic.cpp:86:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     if(last!=s.size()/2 || s.size()%2==1)ans++;
      |        ~~~~^~~~~~~~~~~~
palindromic.cpp:71:9: warning: variable 'n' set but not used [-Wunused-but-set-variable]
   71 |     int n;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...