oj.uz

Submission #516288

# Submission time Handle Problem Language Result Execution time Memory
516288 2022-01-21T03:06:34 Z fcmalkcin Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 325 ms 44180 KB 
/*#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 18 ms 15976 KB Output is correct
3 Correct 18 ms 15952 KB Output is correct
4 Correct 18 ms 15952 KB Output is correct
5 Correct 18 ms 15972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 18 ms 15976 KB Output is correct
3 Correct 18 ms 15952 KB Output is correct
4 Correct 18 ms 15952 KB Output is correct
5 Correct 18 ms 15972 KB Output is correct
6 Correct 18 ms 15956 KB Output is correct
7 Correct 18 ms 15968 KB Output is correct
8 Correct 20 ms 15968 KB Output is correct
9 Correct 18 ms 15920 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 18 ms 15976 KB Output is correct
3 Correct 18 ms 15952 KB Output is correct
4 Correct 18 ms 15952 KB Output is correct
5 Correct 18 ms 15972 KB Output is correct
6 Correct 18 ms 15956 KB Output is correct
7 Correct 18 ms 15968 KB Output is correct
8 Correct 20 ms 15968 KB Output is correct
9 Correct 18 ms 15920 KB Output is correct
10 Correct 22 ms 16268 KB Output is correct
11 Correct 20 ms 16228 KB Output is correct
12 Correct 21 ms 16216 KB Output is correct
13 Correct 22 ms 16140 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 18 ms 15976 KB Output is correct
3 Correct 18 ms 15952 KB Output is correct
4 Correct 18 ms 15952 KB Output is correct
5 Correct 18 ms 15972 KB Output is correct
6 Correct 18 ms 15956 KB Output is correct
7 Correct 18 ms 15968 KB Output is correct
8 Correct 20 ms 15968 KB Output is correct
9 Correct 18 ms 15920 KB Output is correct
10 Correct 22 ms 16268 KB Output is correct
11 Correct 20 ms 16228 KB Output is correct
12 Correct 21 ms 16216 KB Output is correct
13 Correct 22 ms 16140 KB Output is correct
14 Correct 325 ms 44180 KB Output is correct
15 Correct 174 ms 39000 KB Output is correct
16 Correct 286 ms 43404 KB Output is correct
17 Correct 190 ms 30776 KB Output is correct