oj.uz

Submission #936283

# Submission time Handle Problem Language Result Execution time Memory
936283 2024-03-01T14:08:36 Z Aiperiii Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 188 ms 19896 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e6+5,tt=31,mod=1e9+7;
int pw[N];
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    pw[0]=1;
    for(int i=1;i<N;i++)pw[i]=pw[i-1]*tt%mod;
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int l=0,r=s.size()-1;
        int sz=0,x=0,y=0,res=0;
        while(l<r){
            sz++;
            x+=pw[sz]*(s[l]-'a'+1);
            x%=mod;
            y*=tt;
            y%=mod;
            y+=(s[r]-'a'+1)*tt;
            y%=mod;
            if(x==y){
                res+=2;
                x=0;y=0;sz=0;
            }
            l++;r--;
        }
        if(l==r)sz++;
        if(sz)res++;
        cout<<res<<"\n";
    }
}
/*
4
bonobo
deleted
racecar
racecars
 */

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8024 KB Output is correct
2 Correct 6 ms 8028 KB Output is correct
3 Correct 6 ms 8264 KB Output is correct
4 Correct 6 ms 8028 KB Output is correct
5 Correct 6 ms 8044 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8024 KB Output is correct
2 Correct 6 ms 8028 KB Output is correct
3 Correct 6 ms 8264 KB Output is correct
4 Correct 6 ms 8028 KB Output is correct
5 Correct 6 ms 8044 KB Output is correct
6 Correct 6 ms 8028 KB Output is correct
7 Correct 6 ms 8164 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 6 ms 8028 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8024 KB Output is correct
2 Correct 6 ms 8028 KB Output is correct
3 Correct 6 ms 8264 KB Output is correct
4 Correct 6 ms 8028 KB Output is correct
5 Correct 6 ms 8044 KB Output is correct
6 Correct 6 ms 8028 KB Output is correct
7 Correct 6 ms 8164 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 6 ms 8028 KB Output is correct
10 Correct 8 ms 8284 KB Output is correct
11 Correct 7 ms 8296 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 7 ms 8384 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8024 KB Output is correct
2 Correct 6 ms 8028 KB Output is correct
3 Correct 6 ms 8264 KB Output is correct
4 Correct 6 ms 8028 KB Output is correct
5 Correct 6 ms 8044 KB Output is correct
6 Correct 6 ms 8028 KB Output is correct
7 Correct 6 ms 8164 KB Output is correct
8 Correct 6 ms 8024 KB Output is correct
9 Correct 6 ms 8028 KB Output is correct
10 Correct 8 ms 8284 KB Output is correct
11 Correct 7 ms 8296 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 7 ms 8384 KB Output is correct
14 Correct 177 ms 19896 KB Output is correct
15 Correct 95 ms 15120 KB Output is correct
16 Correct 188 ms 19368 KB Output is correct
17 Correct 98 ms 14884 KB Output is correct