oj.uz

Submission #250653

# Submission time Handle Problem Language Result Execution time Memory
250653 2020-07-18T15:10:03 Z Sorting Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 254 ms 26388 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int k_N = 1e6 + 3;
const int cnt_Mod = 1;
const array<ll, cnt_Mod> k_Mod{(int)1e9 + 7}, k_Base{293};

int dp[k_N];
string s;
int n;

array<ll, cnt_Mod> h[k_N], b_pow[k_N];

ll get_hash(int l, int r, int idx){
    if(l == 0) return h[r][idx];
    ll ans = (h[r][idx] - h[l - 1][idx] * b_pow[r - l + 1][idx]) % k_Mod[idx];
    return (ans < 0) ? (ans + k_Mod[idx]) : ans;
}

bool equal(int l1, int r1, int l2, int r2){
    for(int i = 0; i < cnt_Mod; ++i)
        if(get_hash(l1, r1, i) != get_hash(l2, r2, i))
            return false;
    return true;
}

void init_hashing(){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < cnt_Mod; ++j){
            if(i == 0)
                h[i][j] = s[i];
            else
                h[i][j] = (h[i - 1][j] * k_Base[j] + s[i]) % k_Mod[j];
        }
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < cnt_Mod; ++j){
            if(i == 0)
                b_pow[i][j] = 1;
            else
                b_pow[i][j] = b_pow[i - 1][j] * k_Base[j] % k_Mod[j];
        }
    }
}

void solve(){
    cin >> s;
    n = (int)s.size();

    if(n == 1){
        cout << "1\n";
        return;
    }


    init_hashing();

    int mid = (n - 1) / 2, mid2 = (n - 2) / 2;
    int ans = 0, i = 0;
    while(true){
        if(i > mid)
            break;

        bool changed = false;
        for(int j = i; j <= mid2; ++j){
            //if(j >= n - j - 1) break;

            if(equal(i, j, n - j - 1, n - i - 1)){
                ans += 2;
                i = j + 1;
                changed = true;
                break;
            }
        }
        if(!changed){
            ans++;
            break;
        }
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--)
        solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 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 0 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 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 0 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 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 0 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 254 ms 20884 KB Output is correct
15 Correct 134 ms 22292 KB Output is correct
16 Correct 238 ms 26388 KB Output is correct
17 Correct 135 ms 14480 KB Output is correct