Submission #1034368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034368		MarwenElarbi	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	3 ms	8280 KiB

palindromic

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e6+5;
const int MOD=1e9+9;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int segtree[nax*4];
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos]=(l==0 ? 0 : -1e9);
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
    return;
}
void update(int pos,int l,int r,int idx,int value){
    if(l==r){
        segtree[pos]=value;
        return;
    }
    int mid=(r+l)/2;
    if(idx<=mid) update(pos*2+1,l,mid,idx,value);
    else update(pos*2+2,mid+1,r,idx,value);
    segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
    return;
}
int query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return -1e9;
    if(l>=left&&r<=right) return segtree[pos];
    int mid=(r+l)/2;
    return max(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
vector<ll> pw={1};
vector<ll> p_hash(nax);
long long B=9973;
void compute_hash(string s){
    while(pw.size()<s.size()){
        pw.pb((pw.back()*B)%MOD);
    }
    p_hash[0]=0;
    for (int i = 0; i < s.size(); ++i)
    {
        p_hash[i+1]=((p_hash[i]*B)%MOD+s[i])%MOD;
    }   
    return;
}
int get_hash(int l,int r){
    long long ans=(p_hash[r+1]-(p_hash[l]*pw[r-l+1]));
    return (ans%MOD + MOD)%MOD;
}
int main()
{
    optimise;
    int test_cases;
    cin>>test_cases;
    while(test_cases--){
        string t;
        cin>>t;
        int n=t.size()+1;
        reverse(t.begin(),t.end());
        t.pb(' ');
        reverse(t.begin(),t.end());
        compute_hash(t);
        int dp[n];
        build(0,0,n-1);
        for (int i = 0; i < n; ++i)
        {
            dp[i]=-1e9;
        }
        dp[0]=0;
        int ans=1;
        for (int i = 1; i <= n/2; ++i)
        {
            int l=-1;
            int r=i+1;
            while(r-l>1){
                int mid=(r+l)/2;
                if(get_hash(mid,i)==get_hash(n-i,n-mid)){
                    r=mid;
                }else l=mid;
            }
            if(r==i+1) continue;
            dp[i]=query(0,0,n-1,r-1,i)+1;
            update(0,0,n-1,i,dp[i]);
            ans=max(ans,(dp[i]*2-((i==n/2&&(n%2==0||t[i]!=t[n-i]) ? 1 : 0))+(i==n/2 ? 0 : 1)));
        }cout <<ans<<endl;

    }
}

        

Compilation message (stderr)

palindromic.cpp: In function 'void compute_hash(std::string)':
palindromic.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < s.size(); ++i)
      |                     ~~^~~~~~~~~~

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