oj.uz

Submission #868408

# Submission time Handle Problem Language Result Execution time Memory
868408 2023-10-31T12:20:49 Z themm1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 53 ms 19136 KB 
#include <bits/stdc++.h>
using namespace std;
// ordered set whith s.order_of_key(x) method, which returns rank of element x in set s
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

// pair printing
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;}
// set printing
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// map printing
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// unordered_set printing
template <class T>
ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// unordered_map printing
template <class T, class U>
ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// vector printing
template<class T>
ostream& operator<<(ostream& out, const vector<T> &cont){ out << "[";  for (const auto &x:cont) out << x << ", ";  out << "]"; return out;}

#define print(x) cout << (x) << endl;
#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "
#define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl

#define int long long
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;
const int SZ = 26;

int N;
string s;
vector<int> pows;

pii cut(int l, int r) {
        int front_hsh = 0, back_hsh = 0;
        for (int i = l, j = r; i < j; i++, j--) {
                front_hsh = (front_hsh + (s[i] * pows[i - l]) % MOD) % MOD;
                int back_i = N - (r - j);
                back_hsh = (back_hsh + (s[j] * pows[back_i]) % MOD) % MOD;
                
                int shifted_fhsh = (front_hsh * pows[back_i]) % MOD;
                if (shifted_fhsh == back_hsh) {
                        return { i + 1, j - 1 };
                }
        }
        return { -INT_MAX, -INT_MAX };
}

void solve() {
        cin >> s;
        N = sz(s);
        int l = 0, r = N - 1, ans = 0;
        while (l < r) {
                pii p = cut(l, r);
                l = p.ff;
                r = p.ss;
                if (l == -INT_MAX) break;
                ans += 2;
        }
        if (l == r) ans++;
        cout << ans << endl;
}

int32_t main() {
        pows.assign(1e6 + 10, 1);
        for (int i = 1; i < 1e6 + 10; i++) pows[i] = (pows[i - 1] * SZ) % MOD;

        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8284 KB Output is correct
2 Correct 9 ms 8272 KB Output is correct
3 Correct 9 ms 8284 KB Output is correct
4 Correct 9 ms 8272 KB Output is correct
5 Correct 9 ms 8284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8284 KB Output is correct
2 Correct 9 ms 8272 KB Output is correct
3 Correct 9 ms 8284 KB Output is correct
4 Correct 9 ms 8272 KB Output is correct
5 Correct 9 ms 8284 KB Output is correct
6 Correct 10 ms 8264 KB Output is correct
7 Correct 9 ms 8284 KB Output is correct
8 Correct 9 ms 8284 KB Output is correct
9 Correct 9 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8284 KB Output is correct
2 Correct 9 ms 8272 KB Output is correct
3 Correct 9 ms 8284 KB Output is correct
4 Correct 9 ms 8272 KB Output is correct
5 Correct 9 ms 8284 KB Output is correct
6 Correct 10 ms 8264 KB Output is correct
7 Correct 9 ms 8284 KB Output is correct
8 Correct 9 ms 8284 KB Output is correct
9 Correct 9 ms 8284 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 9 ms 8268 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 9 ms 8284 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8284 KB Output is correct
2 Correct 9 ms 8272 KB Output is correct
3 Correct 9 ms 8284 KB Output is correct
4 Correct 9 ms 8272 KB Output is correct
5 Correct 9 ms 8284 KB Output is correct
6 Correct 10 ms 8264 KB Output is correct
7 Correct 9 ms 8284 KB Output is correct
8 Correct 9 ms 8284 KB Output is correct
9 Correct 9 ms 8284 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 9 ms 8268 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 9 ms 8284 KB Output is correct
14 Correct 53 ms 19136 KB Output is correct
15 Correct 31 ms 14520 KB Output is correct
16 Correct 46 ms 18444 KB Output is correct
17 Correct 32 ms 14036 KB Output is correct