oj.uz

Submission #885183

# Submission time Handle Problem Language Result Execution time Memory
885183 2023-12-09T07:43:46 Z 12345678 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 85 ms 26916 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-1)/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';
    }
}

/*
10
cars
cac
cactuscac
bob
bbobb
bacocab
bababababababa
bacbacbacbacbacbacbacbacbacbacbac
sasa
sddsa

1
sasa
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9564 KB Output is correct
2 Correct 7 ms 9564 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 7 ms 9564 KB Output is correct
5 Correct 6 ms 9564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9564 KB Output is correct
2 Correct 7 ms 9564 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 7 ms 9564 KB Output is correct
5 Correct 6 ms 9564 KB Output is correct
6 Correct 6 ms 9564 KB Output is correct
7 Correct 6 ms 9564 KB Output is correct
8 Correct 6 ms 9564 KB Output is correct
9 Correct 8 ms 9564 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9564 KB Output is correct
2 Correct 7 ms 9564 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 7 ms 9564 KB Output is correct
5 Correct 6 ms 9564 KB Output is correct
6 Correct 6 ms 9564 KB Output is correct
7 Correct 6 ms 9564 KB Output is correct
8 Correct 6 ms 9564 KB Output is correct
9 Correct 8 ms 9564 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 7 ms 9792 KB Output is correct
12 Correct 8 ms 9972 KB Output is correct
13 Correct 8 ms 9948 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9564 KB Output is correct
2 Correct 7 ms 9564 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 7 ms 9564 KB Output is correct
5 Correct 6 ms 9564 KB Output is correct
6 Correct 6 ms 9564 KB Output is correct
7 Correct 6 ms 9564 KB Output is correct
8 Correct 6 ms 9564 KB Output is correct
9 Correct 8 ms 9564 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 7 ms 9792 KB Output is correct
12 Correct 8 ms 9972 KB Output is correct
13 Correct 8 ms 9948 KB Output is correct
14 Correct 85 ms 26916 KB Output is correct
15 Correct 48 ms 22252 KB Output is correct
16 Correct 79 ms 26392 KB Output is correct
17 Correct 48 ms 19788 KB Output is correct