oj.uz

Submission #917779

# Submission time Handle Problem Language Result Execution time Memory
917779 2024-01-28T19:04:29 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 579 ms 17116 KB 
#pragma GCC optimize("03")
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define ln '\n'
#define F first 
#define S second
#define pb push_back
#define ins insert
#define all(v) v.begin(), v.end()
#define whole(a, n) a + 1, a + n + 1
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int sz = 1e6 + 5;
const int inf = 1e9 + 7;
string s;
int n, sh[sz];
void get_hash(){
    int h = 0, pw = 1, p = 47;
    for(int i = 1; i <= n; i++){
        h = (h + 1LL * (s[i] - 'a' + 1) * pw % inf) % inf;
        pw = 1ll * pw * p % inf;
        sh[i] = h;
    }
}
int bin_pow(int x, int y){
    int res = 1;
    while(y){
        if(y & 1){
            res = 1LL * res * x % inf;
        }
        x = 1LL * x * x % inf;
        y >>= 1;
    }
    return res;
}
bool check(int l, int r){
    l--;
    int h1 = (sh[r] - sh[l] + inf) % inf;
    int h2 = (sh[n-l] - sh[n-r] + inf) % inf;
    /// cout << h1 << " " << h2 << " ";
    if(1LL * h1 * bin_pow(47, (n - r - l)) % inf == h2) return true;
    return false;
}
void solve(){
    cin >> s;
    n = s.length();
    s = '.' + s;
    get_hash();
    int ans = 0;
    int m = n / 2 + n % 2;
    for(int i = 1; i <= m; i++){
        bool t = false;
        for(int j = i; j <= m; j++){
            if(check(i, j)){
                ans += 2;
                i = j;
                t = true;
                if(i == j and i == m and n % 2) ans--;
                break;
            }
        }
        if(!t){
            ans++;
            break;
        }
    }
    cout << ans << ln;
   /*
    for(int i = 1; i <= n; i++) cout << sh[i] << " ";
    cout << ln;
    cout << check(2, 2) << ln;
    cout << bin_pow(47, 4);
    */
}
signed main(){
    fastio
    int T = 1;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 579 ms 16184 KB Output is correct
15 Correct 320 ms 11464 KB Output is correct
16 Correct 538 ms 17116 KB Output is correct
17 Correct 313 ms 8808 KB Output is correct