fork(1) download
copy 
  1. #pragma comment(linker, "/stack:200000000")
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #pragma GCC optimize("unroll-loops")
  5.  
  6. #include<bits/stdc++.h>
  7. #include<ext/pb_ds/assoc_container.hpp>
  8. #include<ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10. using namespace std;
  11.  
  12. #define ll long long
  13. #define ull unsigned long long
  14. #define ld long double
  15. #define pii pair<int,int>
  16. #define pll pair<ll,ll>
  17. #define vi vector<int>
  18. #define vll vector<ll>
  19. #define vc vector<char>
  20. #define vs vector<string>
  21. #define vpll vector<pll>
  22. #define vpii vector<pii>
  23. #define umap unordered_map
  24. #define uset unordered_set
  25. #define PQ priority_queue
  26.  
  27. #define printa(a,L,R) for(int i=L;i<R;i++) cout<<a[i]<<(i==R-1?'\n':' ')
  28. #define printv(a) printa(a,0,a.size())
  29. #define print2d(a,r,c) for(int i=0;i<r;i++) for(int j=0;j<c;j++) cout<<a[i][j]<<(j==c-1?'\n':' ')
  30. #define pb push_back
  31. #define eb emplace_back
  32. #define mt make_tuple
  33. #define fbo find_by_order
  34. #define ook order_of_key
  35. #define MP make_pair
  36. #define UB upper_bound
  37. #define LB lower_bound
  38. #define SQ(x) ((x)*(x))
  39. #define issq(x) (((ll)(sqrt((x))))*((ll)(sqrt((x))))==(x))
  40. #define F first
  41. #define S second
  42. #define mem(a,x) memset(a,x,sizeof(a))
  43. #define inf 1e18
  44. #define E 2.71828182845904523536
  45. #define gamma 0.5772156649
  46. #define nl "\n"
  47. #define lg(r,n) (int)(log2(n)/log2(r))
  48. #define pf printf
  49. #define sf scanf
  50. #define sf1(a)                scanf("%d",&a)
  51. #define sf2(a,b)              scanf("%d %d",&a,&b)
  52. #define sf3(a,b,c)            scanf("%d %d %d",&a,&b,&c)
  53. #define pf1(a)                printf("%d\n",a);
  54. #define pf2(a,b)              printf("%d %d\n",a,b)
  55. #define pf3(a,b,c)            printf("%d %d %d\n",a,b,c)
  56. #define sf1ll(a)              scanf("%lld",&a)
  57. #define sf2ll(a,b)            scanf("%I64d %I64d",&a,&b)
  58. #define sf3ll(a,b,c)          scanf("%I64d %I64d %I64d",&a,&b,&c)
  59. #define pf1ll(a)              printf("%lld\n",a);
  60. #define pf2ll(a,b)            printf("%I64d %I64d\n",a,b)
  61. #define pf3ll(a,b,c)          printf("%I64d %I64d %I64d\n",a,b,c)
  62. #define _ccase printf("Case %lld: ",++cs)
  63. #define _case cout<<"Case "<<++cs<<": "
  64. #define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
  65.  
  66. #define asche cerr<<"Ekhane asche\n";
  67. #define rev(v) reverse(v.begin(),v.end())
  68. #define srt(v) sort(v.begin(),v.end())
  69. #define grtsrt(v) sort(v.begin(),v.end(),greater<ll>())
  70. #define all(v) v.begin(),v.end()
  71. #define mnv(v) *min_element(v.begin(),v.end())
  72. #define mxv(v) *max_element(v.begin(),v.end())
  73. #define toint(a) atoi(a.c_str())
  74. #define BeatMeScanf ios_base::sync_with_stdio(false)
  75. #define valid(tx,ty) (tx>=0&&tx<n&&ty>=0&&ty<m)
  76. #define one(x) __builtin_popcount(x)
  77. #define Unique(v) v.erase(unique(all(v)),v.end())
  78. #define stree l=(n<<1),r=l+1,mid=b+(e-b)/2
  79. #define fout(x) fixed<<setprecision(x)
  80. string tostr(int n) {stringstream rr;rr<<n;return rr.str();}
  81. inline void yes(){cout<<"YES\n";exit(0);}
  82. inline void no(){cout<<"NO\n";exit(0);}
  83. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  84. //ll dx[]={1,0,-1,0,1,-1,-1,1};
  85. //ll dy[]={0,1,0,-1,1,1,-1,-1};
  86. //random_device rd;
  87. //mt19937 random(rd());
  88. #define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); deb(_it, args); }
  89. void deb(istream_iterator<string> it) {}
  90. template<typename T, typename... Args>
  91. void deb(istream_iterator<string> it, T a, Args... args) {
  92.     cerr << *it << " = " << a << endl;
  93.     deb(++it, args...);
  94. }
  95.  
  96. const int mod=1e9+7;
  97. const int N=3e5+9;
  98. const ld eps=1e-9;
  99. const ld PI=acos(-1.0);
  100. //ll gcd(ll a,ll b){while(b){ll x=a%b;a=b;b=x;}return a;}
  101. //ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
  102. //ll qpow(ll n,ll k) {ll ans=1;assert(k>=0);n%=mod;while(k>0){if(k&1) ans=(ans*n)%mod;n=(n*n)%mod;k>>=1;}return ans%mod;}
  103.  
  104.  
  105. ///There can be at most n unique palindromes for a string of size n
  106. struct node             ///a node is a palindromic substring of the string
  107. {
  108.     int nxt[26];        ///link to the palindrome which is formed by adding
  109.                         ///next[i] in both side of this palindrome
  110.     int len;            ///length of the palindrome
  111.     int st,en;          ///starting and ending index of the node
  112.     int suflink;        ///link to the maximum proper suffix palindrome of the node
  113.     int cnt;            ///stores the length of the suffix link chain from it (including this node)
  114.                         ///i.e. the number of palindromic suffix of this node
  115.     int oc;             ///stores the number of occurrence of the node
  116.     int diff;           ///difference diff[v] = len[v]−len[suflink[v]]
  117.     int serieslink;     ///longest suffix-palindrome of v having the difference unequal to diff[v].
  118. };
  119. string s;
  120. node t[N];
  121. int n;                  ///size of string
  122. int sz;                 ///indicates size of the tree
  123. int suf;                ///index of maximum suffix palindrome
  124. void init()
  125. {
  126.     t[1].diff=t[2].diff=0;
  127.     sz=2,suf=2;
  128.     t[1].len=-1,t[1].suflink=t[1].serieslink=1;  ///node 1- root with length -1
  129.     t[2].len=0,t[2].suflink=1;t[2].serieslink=2;  ///node 2- root with length 0 i.e null palindrome
  130. }
  131. /// return if creates a new palindrome
  132. int add_letter(int pos)
  133. {
  134.     ///find the maximum suffix of the prefix+s[pos]
  135.     int cur=suf,curlen=0;
  136.     int ch=s[pos]-'a';
  137.     while(1){
  138.         curlen=t[cur].len;
  139.         if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos]) break;
  140.         cur=t[cur].suflink;
  141.     }
  142.     ///if the node is not created yet then create the new node
  143.     if(t[cur].nxt[ch]){
  144.         suf=t[cur].nxt[ch];
  145.         t[suf].oc++;
  146.         return 0;
  147.     }
  148.     sz++;
  149.     suf=sz;
  150.     t[sz].oc=1;
  151.     t[sz].len=t[cur].len+2;
  152.     t[cur].nxt[ch]=sz;
  153.     t[sz].en=pos;
  154.     t[sz].st=pos-t[sz].len+1;
  155.     if(t[sz].len==1){
  156.         t[sz].diff=1;
  157.         t[sz].serieslink=2;
  158.         t[sz].suflink=2;
  159.         t[sz].cnt=1;
  160.         return 1;
  161.     }
  162.     while(1){
  163.         cur=t[cur].suflink;
  164.         curlen=t[cur].len;
  165.         if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos]){
  166.                 t[sz].suflink=t[cur].nxt[ch];
  167.                 break;
  168.         }
  169.     }
  170.     t[sz].cnt=1+t[t[sz].suflink].cnt;
  171.     t[sz].diff=t[sz].len-t[t[sz].suflink].len;
  172.     if(t[sz].diff==t[t[sz].suflink].diff) t[sz].serieslink=t[t[sz].suflink].serieslink;
  173.     else t[sz].serieslink=t[sz].suflink;
  174.     return 1;
  175. }
  176.  
  177. int ans[N][2],dp[N][2],kfact[N];
  178.  
  179. int getmin(int pos,int v,int k)
  180. {
  181.     dp[v][k]=ans[pos-t[v].len][k];
  182.     if (t[v].diff == t[t[v].suflink].diff){
  183.         dp[v][k] = min(dp[v][k], dp[t[v].suflink][k]);
  184.         dp[v][k] =min(dp[v][k], ans[pos - t[t[v].serieslink].len- t[v].diff][k]);
  185.     }
  186.     return dp[v][k] + 1;
  187. }
  188.  
  189. void calc(int pos,int cur)
  190. {
  191.     pos++;
  192.     ans[pos][0]=1e9;
  193.     ans[pos][1]=1e9;
  194.     for(int v=cur;t[v].len>0;v=t[v].serieslink){
  195.         ans[pos][0]=min(ans[pos][0],getmin(pos,v,1));
  196.         ans[pos][1]=min(ans[pos][1],getmin(pos,v,0));
  197.     }
  198. }
  199.  
  200. ///ans[i][0]=minimal even k (or −2 if it doesn’t exist) such that
  201. ///we can split string s[1.. i] into k palindromes.
  202.  
  203. ///ans[i][1]=minimal odd k (or −1 if it doesn’t exist) such that
  204. ///we can split string s[1.. i] into k palindromes.
  205.  
  206. ///k-palindrome factorization=splitting  the string into k non-empty non-intersecting palindromes
  207.  
  208. ///minimum palindrome factorization=minimum k such that k-palindrome factorization exist
  209.  
  210. int main()
  211. {
  212.     BeatMeScanf;
  213.     int i,j,k,n,m;
  214.     cin>>s;
  215.     n=s.size();
  216.     init();
  217.     ans[0][1]=1e9;
  218.     dp[2][1]=1e9;
  219.     for(i=0;i<n;i++){
  220.         add_letter(i);
  221.         calc(i,suf);
  222.     }
  223.     for(i=1;i<=n;i++) cout<<(ans[i][1]==1e9?-1:ans[i][1])<<' '<<(ans[i][0]==1e9?-2:ans[i][0])<<nl;
  224.  
  225.     ///minimum palindrome factorization
  226.     int res=min(ans[n][0],ans[n][1]);
  227.     cout<<res<<nl;
  228.  
  229.     ///if k-palindrome factorization is possible or not
  230.     for(i=ans[n][1];i<=n;i+=2) kfact[i]=1;
  231.     for(i=ans[n][0];i<=n;i+=2) kfact[i]=1;
  232.     for(i=1;i<=n;i++) cout<<(kfact[i]?"YES\n":"NO\n");
  233.     return 0;
  234. }
  235.  
Success #stdin #stdout 0s 60952KB
comments (?)
stdin
copy 
aabaa
stdout
copy 
1 -2
1 2
3 2
3 2
1 4
1
YES
NO
YES
YES
YES
https://ideone.com/u3cXip
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!