Submission #1122302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122302		stakoz	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	461 ms	41736 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << ' ' << (x) << '\n';
typedef array<int, 2> F;
F base = {2137, 2143};
F mod = {(int)1e9 + 7, (int)1e9 + 9}; 

void add(int &a, int b, int j){
    a += b;
    if(a > mod[j]) a -= mod[j];
}

void sub(int &a, int b, int j){
    a -= b;
    if(0 > a) a += mod[j];
}

int mul(int a, int b, int j){
    return (a * b) % mod[j];
}

void solve(){
    //wczytywanie
    string s;
    cin >> s;
    int n = s.size();
    s = "$" + s;

    //potegi
    vector<F> p(n + 2, {1, 1});
    for(int i = 1; i <= n + 1; i++){
        for(int j = 0; j < 2; j++){
            p[i][j] = mul(p[i - 1][j], base[j], j);
        }
    }

    //hash???
    vector<F> hash(n + 1); 
    for(int i = 1; i <= n; i++){
        hash[i] = hash[i - 1];
        for(int j = 0; j < 2; j++){
            add(hash[i][j], mul(s[i], p[i][j], j), j);
        }
    }
    int l = 0, lx = 0, r = n, rx = n;
    int seg_num = 0; 
    bool finished = 0; 
    while(!finished){
        rx--; 
        lx++;
        F curr_l = hash[lx], curr_r = hash[r];
        for(int j = 0; j < 2; j++){
            sub(curr_l[j], hash[l][j] , j);
            sub(curr_r[j], hash[rx][j] , j);
        }
        for(int j = 0; j < 2; j++){
            curr_l[j] = mul(curr_l[j], p[r - lx][j], j);
        }
        if(rx < lx){
            seg_num++;
            finished = true; 
            break;
        }
        if(curr_l == curr_r){
            seg_num += 2;
            l = lx;
            r = rx;
            if(l == r)
                finished = true;
        }
        
    }
    cout << seg_num << '\n';
}




int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin >> q;
    while(q--){
        solve();
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40