Submission #703679

#	Time	Username	Problem	Language	Result	Execution time	Memory
703679		mychecksedad	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	231 ms	34556 KiB

palindromic

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e6+100, M = 1e5+10, K = 20;

int n;
string s;
ll h[N], p[N], rp[N];
ll po(ll a, ll b){ll res = 1; while(b){if(b&1) (res*=a)%=MOD; b>>=1; (a*=a)%=MOD;} return res;}

ll mod(ll x){
  x %= MOD;
  x = (x+MOD)%MOD;
  return x;
}

void solve(){
  cin >> s;
  n = s.length();
  h[0] = 0;
  for(int i = 1; i <= n; ++i){
    h[i] = (h[i - 1] + p[i] * (s[i - 1] - 'a' + 1)) % MOD;
  }
  int ans = 1, last = 1;
  for(int i = 1; i <= n/2; ++i){
    if(mod((h[n - last + 1] - h[n - i]) * rp[n - i]) == mod((h[i] - h[last - 1]) * rp[last - 1])){
      ans += 2;
      last = i + 1;
    }
  }
  if(n % 2 == 0 && last == n/2 + 1) ans--;
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int T = 1, aa;
  cin >> T;aa=T;
  p[0] = 1;
  for(int i = 1; i < N; ++i) p[i] = (p[i - 1] * 37) % MOD;
  for(int i = 0; i < N; ++i) rp[i] = po(p[i], MOD-2);
  while(T--){
    // cout << "Case #" << aa-T << ": ";
    solve();
    cout << '\n';
  }
  return 0;
 
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:44:14: warning: variable 'aa' set but not used [-Wunused-but-set-variable]
   44 |   int T = 1, aa;
      |              ^~

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