oj.uz

Submission #592981

# Submission time Handle Problem Language Result Execution time Memory
592981 2022-07-10T03:21:45 Z Hanksburger Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 68 ms 19028 KB 
#include <bits/stdc++.h>
using namespace std;
const long long mod1=1e15+1, mod2=1e15+3;
long long power1[1000005], power2[1000005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    power1[0]=power2[0]=1;
    for (long long i=1; i<=1e6; i++)
        power1[i]=power1[i-1]*26%mod1;
    for (long long i=1; i<=1e6; i++)
        power2[i]=power2[i-1]*26%mod2;
    long long t;
    cin >> t;
    while (t--)
    {
        string str;
        cin >> str;
        long long len=str.length(), x1=0, x2=0, y1=0, y2=0, cnt=0, ans=0;
        for (long long i=0; i<len/2; i++)
        {
            x1=(x1*26+str[i]-'a')%mod1;
            x2=(x2*26+str[i]-'a')%mod2;
            y1=(y1+(str[len-i-1]-'a')*power1[cnt])%mod1;
            y2=(y2+(str[len-i-1]-'a')*power2[cnt])%mod2;
            cnt++;
            if (x1==y1 && x2==y2)
            {
                ans+=2;
                x1=x2=y1=y2=cnt=0;
            }
        }
        cout << ans+(cnt || len&1) << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15864 KB Output is correct
2 Correct 23 ms 15952 KB Output is correct
3 Correct 22 ms 15920 KB Output is correct
4 Correct 21 ms 15888 KB Output is correct
5 Correct 21 ms 15964 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15864 KB Output is correct
2 Correct 23 ms 15952 KB Output is correct
3 Correct 22 ms 15920 KB Output is correct
4 Correct 21 ms 15888 KB Output is correct
5 Correct 21 ms 15964 KB Output is correct
6 Correct 21 ms 15924 KB Output is correct
7 Correct 21 ms 15980 KB Output is correct
8 Correct 21 ms 15916 KB Output is correct
9 Correct 24 ms 15948 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15864 KB Output is correct
2 Correct 23 ms 15952 KB Output is correct
3 Correct 22 ms 15920 KB Output is correct
4 Correct 21 ms 15888 KB Output is correct
5 Correct 21 ms 15964 KB Output is correct
6 Correct 21 ms 15924 KB Output is correct
7 Correct 21 ms 15980 KB Output is correct
8 Correct 21 ms 15916 KB Output is correct
9 Correct 24 ms 15948 KB Output is correct
10 Correct 24 ms 16048 KB Output is correct
11 Correct 23 ms 15956 KB Output is correct
12 Correct 22 ms 16080 KB Output is correct
13 Correct 38 ms 16000 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15864 KB Output is correct
2 Correct 23 ms 15952 KB Output is correct
3 Correct 22 ms 15920 KB Output is correct
4 Correct 21 ms 15888 KB Output is correct
5 Correct 21 ms 15964 KB Output is correct
6 Correct 21 ms 15924 KB Output is correct
7 Correct 21 ms 15980 KB Output is correct
8 Correct 21 ms 15916 KB Output is correct
9 Correct 24 ms 15948 KB Output is correct
10 Correct 24 ms 16048 KB Output is correct
11 Correct 23 ms 15956 KB Output is correct
12 Correct 22 ms 16080 KB Output is correct
13 Correct 38 ms 16000 KB Output is correct
14 Correct 68 ms 18992 KB Output is correct
15 Correct 50 ms 18924 KB Output is correct
16 Correct 66 ms 19028 KB Output is correct
17 Correct 48 ms 17748 KB Output is correct