Submission #516288

#	Time	Username	Problem	Language	Result	Execution time	Memory
516288		fcmalkcin	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	325 ms	44180 KiB

palindromic

/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>
using namespace std;

#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define F(i,a,b) for (ll i=a;i<=b;i++)

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e6+40;
const ll mod=1000003 ;
const ll base=317;

/// you will be the best but now you just are trash
/// goal 2/7
ll a[maxn];
struct tk
{
    ll mod;
    ll n;
    string s;
    ll f[maxn];
    ll mu[maxn];
    tk()
    {
        memset(mu,0,sizeof(mu));
        ll h=5e8;
        while (1)
        {
            ll nw=((abs)((ll)rnd()))%h +h ;
            bool chk=true;
            for (ll i=2;i*i<=nw;i++)
            {
                if (nw%i==0)
                {
                    chk=false;
                    break;
                }
            }
            if (chk)
            {
                mod=nw;
                break;
            }
        }
        mu[0]=1;
        for (int i=1;i<maxn;i++)
        {
            mu[i]=(mu[i-1]*base)%mod;
        }
    }
    void init(string s)
    {
        ll n=s.length();
        f[0]=0;
        for (int i=1;i<=n;i++)
        {
            f[i]=(f[i-1]*base+s[i-1]-'a'+1)%mod;
        }
    }
    ll get(ll l,ll r)
    {
        return ((f[r]-f[l-1]*mu[r-l+1])%mod+mod)%mod;
    }
}man,man1;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll t;
    cin>> t;
    while (t--)
    {
        string s;
        cin>> s;
        ll n=s.length();
        man.init(s);
        man1.init(s);
        ll ans=n%2;
        for (int i=1;i<=n/2;i++)
        {
            ll j=i;
            while (j<=(n/2)&&make_pair(man.get(i,j),man1.get(i,j))!=make_pair(man.get(n-j+1,n-i+1),man1.get(n-j+1,n-i+1)))
            {
                j++;
            }
            if (j>(n/2))
            {
            ans+=(1-n%2);
               break;
            }
            else
            {
                ans+=2;
               // cout <<i<<" "<<j<<endl;
                i=j;
            }
        }
        cout <<ans<<endl;
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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