oj.uz

Submission #256284

# Submission time Handle Problem Language Result Execution time Memory
256284 2020-08-02T13:40:27 Z giorgikob Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 245 ms 26492 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6 + 5;
const int p = 31, mod = 1e9 + 9;

inline void test_case(){

        string s;
        cin >> s;
        s = '#' + s;
        int n = s.size();
        vector<ll>hash_val(n+1,0), P(n+5,0);

        int answer = 0;

        P[0] = 1;
        for(int i = 1; i <= n; i++){
                P[i] = P[i-1] * p;
                P[i] %= mod;
        }

        for(int i = 1; i < n; i++){
                hash_val[i] = hash_val[i-1] + (s[i] - 'a' + 1) * P[i-1];
                hash_val[i] %= mod;
        }

        //hash_val[n] = hash_val[n-1];

        int l = 1, r = 1;
        int sl = n-1, sr = n-1;

        while(r < sl){
                if( ( (hash_val[r] - hash_val[l-1] + mod) * P[sl-l] ) % mod  == (hash_val[sr] - hash_val[sl-1] + mod) % mod ){
                        //cout << r << endl;
                        r++;
                        l = r;
                        sl--;
                        sr = sl;
                        answer += 2;
                } else {
                        r++;
                        sl--;
                }
        }

        if(l <= n/2) answer ++;

        cout << answer << endl;
}

int main(){

        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

        int T;
        cin >> T;
        while(T--){
                test_case();
        }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 360 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 1 ms 608 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 616 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 1 ms 608 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 616 KB Output is correct
14 Correct 245 ms 26492 KB Output is correct
15 Correct 128 ms 21952 KB Output is correct
16 Correct 219 ms 25200 KB Output is correct
17 Correct 128 ms 14228 KB Output is correct