Submission #1034912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034912		MarwenElarbi	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	159 ms	28648 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);
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 ans=0;
        int lst=1;
        bool test=false;
        for (int i = 1; i <= n/2; ++i)
        {
            if(get_hash(lst,i)==get_hash(n-i,n-lst)){
                ans+=2;
                if(i==n/2&&n%2==0&&i==lst) ans--;
                lst=i+1;
            }else if(i==n/2) ans++;
        }
        cout <<ans<<endl;
    }
}

Compilation message (stderr)

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

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