oj.uz

Submission #934266

# Submission time Handle Problem Language Result Execution time Memory
934266 2024-02-27T04:34:08 Z UmairAhmadMirza Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 267 ms 34876 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e6+5;
int const mod=1e9+7;
int const base=727;
int dp[N];
int Hash[N];
int pw[N];
void pre(){
  pw[0]=1;
  for(int i=1;i<N;i++)
    pw[i]=(pw[i-1]*base)%mod;
}
int make_hash(int l,int r){
  l--;
  int h=((Hash[r]-((Hash[l]*pw[r-l])%mod))+mod)%mod;
  return h;
}
void solve(){
  string s;
  cin>>s;
  int n=s.length();
  int hsh=0;
  for(int i=0;i<n;i++){
    hsh*=base;
    hsh%=mod;
    hsh+=s[i];
    hsh%=mod;
    Hash[i+1]=hsh;
  }
  for(int i=0;i<=n;i++)
    dp[i]=0;
  int ans=0;
  int j=0;
  for(int i=1;i<=(n/2);i++){
    if(make_hash(j+1,i)==make_hash(n-(i-1),n-j)){
      j=i;
      ans+=2;
    }
  }
  if(j*2<n)
    ans++;
  cout<<max(1LL,ans)<<endl;
}
signed main(){
  pre();
  int t;
  cin>>t;
  while(t--)
    solve();
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10840 KB Output is correct
2 Correct 6 ms 10844 KB Output is correct
3 Correct 6 ms 10844 KB Output is correct
4 Correct 6 ms 10844 KB Output is correct
5 Correct 6 ms 11100 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10840 KB Output is correct
2 Correct 6 ms 10844 KB Output is correct
3 Correct 6 ms 10844 KB Output is correct
4 Correct 6 ms 10844 KB Output is correct
5 Correct 6 ms 11100 KB Output is correct
6 Correct 6 ms 10844 KB Output is correct
7 Correct 6 ms 10844 KB Output is correct
8 Correct 6 ms 10844 KB Output is correct
9 Correct 6 ms 10844 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10840 KB Output is correct
2 Correct 6 ms 10844 KB Output is correct
3 Correct 6 ms 10844 KB Output is correct
4 Correct 6 ms 10844 KB Output is correct
5 Correct 6 ms 11100 KB Output is correct
6 Correct 6 ms 10844 KB Output is correct
7 Correct 6 ms 10844 KB Output is correct
8 Correct 6 ms 10844 KB Output is correct
9 Correct 6 ms 10844 KB Output is correct
10 Correct 9 ms 10844 KB Output is correct
11 Correct 7 ms 10668 KB Output is correct
12 Correct 8 ms 10840 KB Output is correct
13 Correct 8 ms 10844 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10840 KB Output is correct
2 Correct 6 ms 10844 KB Output is correct
3 Correct 6 ms 10844 KB Output is correct
4 Correct 6 ms 10844 KB Output is correct
5 Correct 6 ms 11100 KB Output is correct
6 Correct 6 ms 10844 KB Output is correct
7 Correct 6 ms 10844 KB Output is correct
8 Correct 6 ms 10844 KB Output is correct
9 Correct 6 ms 10844 KB Output is correct
10 Correct 9 ms 10844 KB Output is correct
11 Correct 7 ms 10668 KB Output is correct
12 Correct 8 ms 10840 KB Output is correct
13 Correct 8 ms 10844 KB Output is correct
14 Correct 267 ms 34516 KB Output is correct
15 Correct 138 ms 30860 KB Output is correct
16 Correct 242 ms 34876 KB Output is correct
17 Correct 134 ms 25600 KB Output is correct