oj.uz

Submission #318024

# Submission time Handle Problem Language Result Execution time Memory
318024 2020-10-31T09:03:24 Z parsabahrami Palindromic Partitions (CEOI17_palindromic) C++17
15 / 100
 2 ms 1152 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=1e5+10,LN=30,SQ=550,M=1e9+10;
const ll INF=1e16;
const int MOD=1000000007 /*998244353*/;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pair<pll,ll>, null_type,less<pair<pll,ll>>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll t,b=737,m=1000696969,p[N];
int main(){
    fast_io;
    p[0]=1;
    for(ll i=1; i<N; i++) p[i]=p[i-1]*b%m;
    cin >> t;
    while(t--){
        string s;
        ll n;
        cin >> s;
        n=s.size();
        ll l=0,r=n-1,ans=1,x=0,h1=0,h2=0;
        while(r-l>1){
            h1=(h1*b+s[l]-'a'+1)%m;
            h2+=p[x]*(s[r]-'a'+1);
            h2%=m;
            x++;
            if(h1==h2) ans+=2,h1=0,h2=0,x=0;
            l++;
            r--;
        }
        if(r>l){
            h1=(h1*b+s[l]-'a'+1)%m;
            h2+=p[x]*(s[r]-'a'+1);
            if(h1==h2) ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Incorrect 2 ms 1132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Incorrect 2 ms 1132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Incorrect 2 ms 1132 KB Output isn't correct
7 Halted 0 ms 0 KB -