oj.uz

Submission #939234

# Submission time Handle Problem Language Result Execution time Memory
939234 2024-03-06T07:15:17 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 240 ms 18888 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,mod=1e9+7,tt=13;
int pw[N];
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    pw[0]=1;
    for(int i=1;i<N;i++){
        pw[i]=pw[i-1]*tt;
        pw[i]%=mod;
    }
    while(t--){
        string s;
        cin>>s;
        s=" "+s;
        vector <int> h(s.size());
        for(int i=1;i<s.size();i++){
            h[i]=h[i-1]*tt+(s[i]-'a'+1);
            h[i]%=mod;
        }
        int st1=1,end2=s.size()-1;
        int end1=1,st2=s.size()-1;
        int h1=0,h2=0;
        int ans=0;
        while(end1<st2){
            h1=(h[end1]-h[st1-1]*pw[end1-st1+1])%mod;
            while(h1<0)h1+=mod;
            h2=(h[end2]-h[st2-1]*pw[end2-st2+1])%mod;
            while(h2<0)h2+=mod;
            //cout<<h1<<" "<<h2<<"\n";
            //cout<<st1<<" "<<end1<<" "<<st2<<' '<<end2<<"\n";
            if(h1==h2){
                end1++;
                st1=end1;
                st2--;
                end2=st2;
                ans+=2;
            }
            else{
                st2--;
                end1++;
            }
        }
        if(st1<=end2)ans++;
        cout<<ans<<"\n";
    }
    
}
/*

*/

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:25:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i=1;i<s.size();i++){
      |                     ~^~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8028 KB Output is correct
2 Correct 6 ms 8028 KB Output is correct
3 Correct 6 ms 8028 KB Output is correct
4 Correct 6 ms 8028 KB Output is correct
5 Correct 6 ms 8028 KB Output is correct
6 Correct 6 ms 8048 KB Output is correct
7 Correct 6 ms 8028 KB Output is correct
8 Correct 6 ms 8248 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 8028 KB Output is correct
2 Correct 6 ms 8028 KB Output is correct
3 Correct 6 ms 8028 KB Output is correct
4 Correct 6 ms 8028 KB Output is correct
5 Correct 6 ms 8028 KB Output is correct
6 Correct 6 ms 8048 KB Output is correct
7 Correct 6 ms 8028 KB Output is correct
8 Correct 6 ms 8248 KB Output is correct
9 Correct 6 ms 8028 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 8 ms 8332 KB Output is correct
12 Correct 9 ms 8368 KB Output is correct
13 Correct 8 ms 8284 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8028 KB Output is correct
2 Correct 6 ms 8028 KB Output is correct
3 Correct 6 ms 8028 KB Output is correct
4 Correct 6 ms 8028 KB Output is correct
5 Correct 6 ms 8028 KB Output is correct
6 Correct 6 ms 8048 KB Output is correct
7 Correct 6 ms 8028 KB Output is correct
8 Correct 6 ms 8248 KB Output is correct
9 Correct 6 ms 8028 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 8 ms 8332 KB Output is correct
12 Correct 9 ms 8368 KB Output is correct
13 Correct 8 ms 8284 KB Output is correct
14 Correct 240 ms 17232 KB Output is correct
15 Correct 126 ms 18876 KB Output is correct
16 Correct 217 ms 18888 KB Output is correct
17 Correct 129 ms 12860 KB Output is correct