Submission #1312881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312881		mikasa	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	2440 ms	106084 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x) x.begin(),x.end()

#define io(nam) if (!(nam).empty()) { \
    freopen(((nam)+".in").c_str(),"r",stdin); \
    freopen(((nam)+".out").c_str(),"w",stdout); \
}
  #define pb push_back 
const int N=2e6+5;
const int mod=1e9+9;
const int inf=9e18;

int a[N];

string s;

struct Segtree {


  struct Node {
    int ha;
    int len;
  };

  int p=149;
  vector<int> ppow;
  

  Node merge(Node a , Node b) {
    return {(b.ha+(ppow[b.len]*a.ha%mod))%mod,a.len+b.len};
  }

  vector<Node> tr;
  vector<int> lz;

  void init(int n) {
    tr.assign(4*n,{0,0});
    lz.assign(4*n,0);
    ppow.resize(n+1);
    ppow[0]=1;
    for (int i=1;i<=n;++i) {
      ppow[i]=ppow[i-1]*p%mod;
    }
  }

  void build(int u,int l,int r) {
    if (l==r) {
      tr[u]={s[l],1};
      return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    tr[u]=merge(tr[u<<1],tr[u<<1|1]);
  }

  // void push(int u,int l,int r) {
  //   if (!lz[u]) return;
  //   int k=lz[u];
  //   if (l!=r) {
  //     lz[u<<1]=lz[u<<1|1]=lz[u];
  //     int mid=l+r>>1;
  //     int le=mid-l+1,ri=r-mid;
  //     tr[u<<1]={k*su[le]%mod,le};
  //     tr[u<<1|1]={k*su[ri]%mod,ri};
  //   }
  //   lz[u]=0;
  // }s

  // void upd(int u,int l,int r,int x,int y,int k) {
  //   if (l>y||r<x) return;
  //   if (l>=x&&r<=y) {
  //     lz[u]=k;
  //     tr[u]={k*su[r-l+1]%mod,r-l+1};
  //     return;
  //   }
  //   push(u,l,r);
  //   int mid=l+r>>1;
  //   upd(u<<1,l,mid,x,y,k);
  //   upd(u<<1|1,mid+1,r,x,y,k);
  //   tr[u]=merge(tr[u<<1],tr[u<<1|1]);
  // }
  Node query(int u,int l,int r,int x,int y) {
    if (l>y||r<x) return {0,0} ;
    if (l>=x&&r<=y) {
      return tr[u];
    }
    //push(u,l,r);
    int mid=l+r>>1;
    Node le=query(u<<1,l,mid,x,y);
    Node ri=query(u<<1|1,mid+1,r,x,y);
    return merge(le,ri);
  }
};


void levi() {
  cin>>s;
  int n=s.size();
  s='!'+s;
int len=1,res=0;
  Segtree h;
  h.init(n);
  h.build(1,1,n);
  for (int i=1;i<=n/2;) {
    while (h.query(1,1,n,i,i+len-1).ha!=h.query(1,1,n,n-i+1-len+1,n-i+1).ha) {
      ++len;
      if (i+len-1>n/2) break;
    }
    int j=i+len-1;
    // debug(i,' ');
    // debug(j,'\n');
    if (j>n/2) {
      cout<<++res<<'\n';
      return;
    }
    res+=2;
    i+=len;
    len=1;
  }
  if (n&1) ++res;
  cout<<res<<'\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);int tt=1;cin>>tt;
  while (tt--) levi();
}

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