제출 #648815

#제출 시각아이디문제언어결과실행 시간메모리
648815MrBrionixPalindromic Partitions (CEOI17_palindromic)C++17
60 / 100
135 ms131072 KiB
#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; }

컴파일 시 표준 에러 (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++;
      |     ~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...