oj.uz

Submission #1008515

# Submission time Handle Problem Language Result Execution time Memory
1008515 2024-06-26T13:57:11 Z Alihan_8 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 224 ms 33700 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;
}

const int Mod = 1e9 + 7, P = 31;

struct _hash{
    vector <int> pw, p;

    int n;

    _hash() : pw(1, 1) {}

    void modify(string s){
        int n = s.size();

        while ( pw.size() <= n ){
            pw.pb(pw.back() * P % Mod);
        }

        p.resize(n + 1);

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

    int get(int l, int r){
        return (p[r + 1] - p[l] * pw[r - l + 1] % Mod + Mod) % Mod;
    }
};

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

    int t; cin >> t;

    while ( t-- ){
        string s; cin >> s;

        _hash h;

        h.modify(s);

        int l = 0, r = (int)s.size() - 1, ans = 0;

        while ( l <= r ){
            if ( l == r ){
                ans++;

                break;
            }

            int p = l, q = r;

            while ( p < q && h.get(l, p) != h.get(q, r) ){
                p++, q--;
            }

            if ( p < q ){
                ans += 2;
            } else{
                ans++;

                break;
            }

            l = p + 1, r = q - 1;
        }

        cout << ans << ln;
    }

    cout << '\n';
}

Compilation message

palindromic.cpp: In member function 'void _hash::modify(std::string)':
palindromic.cpp:43:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |         while ( pw.size() <= 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 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 1 ms 708 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 2 ms 756 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 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 1 ms 708 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 224 ms 33700 KB Output is correct
15 Correct 120 ms 22368 KB Output is correct
16 Correct 189 ms 29616 KB Output is correct
17 Correct 139 ms 19088 KB Output is correct