oj.uz

Submission #915827

# Submission time Handle Problem Language Result Execution time Memory
915827 2024-01-24T18:42:02 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 52 ms 28580 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define ss(a) set<a>
#define pp(a, b) pair<a, b>
#define mm(a, b) map<a, b>
#define qq(a) queue<a>
#define pq(a) priority_queue<a>
#define ump(a, b) unordered_map<a, b>
#define ANDROID                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define elif else if
#define endl "\n"
#define pb push_back
#define ins insert
#define logi __lg
#define sqrt sqrtl
#define mpr make_pair
using namespace std;
using namespace __cxx11;
using namespace __gnu_pbds;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll p = 37;
void solve()
{
    str s;
    cin >> s;
    ll n = s.size();
    s = ' ' + s;
    ll pref[n + 1], pw[n + 1];
    pw[0] = 1;
    pref[0] = 0;
    for (ll i = 1; i <= n; i++)
        s[i] -= 'a' - 1, pw[i] = pw[i - 1] * p, pref[i] = pref[i - 1] + s[i] * pw[i];
    auto sum = [&](ll l, ll r)
    {
        return pref[r] - pref[l - 1];
    };
    ll l = 1, r = n, ans = 0;
    while (l <= r)
    {
        ll curl = l, curr = r;
        while (sum(l, curl) * pw[curr - l] != sum(curr, r))
            curl++, curr--;
        ans += curl == r ? 1 : 2;
        l = curl + 1;
        r = curr - 1;
    }
    cout << ans << endl;
}
/*
 
*/
int main()
{
    ANDROID
    // precomp();
    ll t = 1;
    cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case #" << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 608 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 608 KB Output is correct
14 Correct 52 ms 28580 KB Output is correct
15 Correct 31 ms 23500 KB Output is correct
16 Correct 50 ms 27488 KB Output is correct
17 Correct 28 ms 15264 KB Output is correct