oj.uz

Submission #939111

# Submission time Handle Problem Language Result Execution time Memory
939111 2024-03-06T05:48:23 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 261 ms 35260 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Hash{
    vector <int> p, pw;
    const int P = 31;
    // 0 - indexed
    string s;
    int n, Mod;
    Hash(int Mod) : Mod(Mod) {}
    void ins(string _s){
        s = _s;
        n = (int)s.size();
        p.resize(n + 1); pw.pb(1);
        while ( (int)pw.size() <= n ){
            pw.pb(pw.back() * P % Mod);
        }
        for ( int i = 0; i < n; i++ ){
            int f = s[i] - 'a' + 1; // *appropriate subtraction
            p[i + 1] = (p[i] * P + f) % Mod;
        }
    }
    int get(int l, int r){
        int ans = (p[r + 1] - p[l] * pw[r - l + 1]) % Mod;
        if ( ans < 0 ) ans += Mod;
        return ans;
    }
};

void solve(){
    string s; cin >> s;
    Hash h(998244353);
    h.ins(s);
    int l = 0, r = (int)s.size() - 1, ans = 0;
    while ( l <= r ){
        if ( l == r ){
            ans++;
            break;
        }
        int a = l, b = r;
        while ( a < b && h.get(l, a) != h.get(b, r) ){
            a++, b--;
        }
        if ( a >= b ){
            ans++;
            break;
        }
        ans += 2;
        l = a + 1, r = b - 1;
    }
    cout << ans << ln;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    while ( t-- ){
        solve();
    }

    cout << '\n';
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 780 KB Output is correct
11 Correct 2 ms 712 KB Output is correct
12 Correct 3 ms 740 KB Output is correct
13 Correct 2 ms 728 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 780 KB Output is correct
11 Correct 2 ms 712 KB Output is correct
12 Correct 3 ms 740 KB Output is correct
13 Correct 2 ms 728 KB Output is correct
14 Correct 251 ms 32748 KB Output is correct
15 Correct 138 ms 31784 KB Output is correct
16 Correct 261 ms 35260 KB Output is correct
17 Correct 140 ms 25408 KB Output is correct