oj.uz

Submission #885180

# Submission time Handle Problem Language Result Execution time Memory
885180 2023-12-09T07:35:31 Z 12345678 Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 6 ms 9564 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int nx=1e6+5, mod=1e9+7;
ll n, t, p[nx], st, ed, vl, qs[nx], sz, cnt;
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    p[0]=1;
    for (int i=1; i<nx; i++) p[i]=(p[i-1]*26)%mod;
    cin>>t;
    while (t--)
    {
        cin>>s;
        cnt=st=0;
        n=s.size();
        qs[0]=s[0]-'a';
        for (int i=1; i<n; i++) qs[i]=(qs[i-1]+(s[i]-'a')*p[i])%mod;
        while (st<=n/2)
        {
            vl=0;
            bool can=0;
            for (int i=st; i<=(n/2); i++)
            {
                vl=(vl+(s[i]-'a')*p[i-st])%mod;
                ed=n-1-st;
                sz=i-st+1;
                if (st+sz-1>=ed-sz+1) break;
                //cout<<st<<' '<<sz<<' '<<ed<<' '<<qs[ed]-qs[ed-sz]<<' '<<vl<<' '<<vl*p[ed-sz+1]<<'\n';
                if (((qs[ed]-qs[ed-sz])%mod+mod)%mod==(vl*p[ed-sz+1])%mod)
                {
                    cnt+=2;
                    st=i+1;
                    can=1;
                    break;
                }
            }
            if (!can) {cnt++; break;}
        }
        cout<<cnt<<'\n';
    }
}

/*
1
deleted
*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9564 KB Output isn't correct
2 Halted 0 ms 0 KB -