oj.uz

Submission #983123

# Submission time Handle Problem Language Result Execution time Memory
983123 2024-05-15T08:29:26 Z kh0i Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 471 ms 45248 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

struct Hash{
    ll base, mod;

    int n;
    string s;
    vector<ll> p, hash;

    void precalc(int _n){
        hash.resize(_n + 2, 0);
        p.resize(_n + 2, 0);
        p[0] = 1;
        for(int i = 1; i <= _n; ++i)
            p[i] = (p[i - 1] * base) % mod;
    }

    void init(string x, ll _base, ll _mod){
        n = x.size();
        base = _base, mod = _mod;

        precalc(n);

        s = ' ' + x;
        for(int i = 1; i <= n; ++i)
            hash[i] = (hash[i - 1] * base + (s[i] - 'a' + 1)) % mod;
    }

    ll get_hash(int l, int r){
        return (hash[r] - hash[l - 1] * p[r - l + 1] + mod * mod) % mod;
    }

    ll get_single_hash(string x){
        ll res = 0;
        for(int i = 0; i < sz(x); ++i)
            res = (res * base + (x[i] - 'a' + 1)) % mod;
        return res;
    }
};

void solve(){
    string s;
    cin >> s;
    Hash h1, h2;
    h1.init(s, 137, 1e9 + 7);
    h2.init(s, 137, 1e9 + 9);

    int l = 1, r = sz(s);
    int res = 0;

    while(l <= r){
        bool found = 0;
        for(int len = 1; l + len - 1 < r - len + 1; ++len){
            bool ok = 1;
            ok &= (h1.get_hash(l, l + len - 1) == h1.get_hash(r - len + 1, r));
            ok &= (h2.get_hash(l, l + len - 1) == h2.get_hash(r - len + 1, r));
            if(ok){
                res += 2;
                l = l + len, r = r - len;
                found = 1;
                break;
            }
        }

        if(!found){
            ++res;
            break;
        }
    }

    cout << res << '\n';
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message

palindromic.cpp: In function 'int32_t main()':
palindromic.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 1 ms 344 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 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 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 1 ms 344 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 5 ms 904 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 5 ms 904 KB Output is correct
13 Correct 5 ms 816 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 1 ms 344 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 5 ms 904 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 5 ms 904 KB Output is correct
13 Correct 5 ms 816 KB Output is correct
14 Correct 471 ms 45248 KB Output is correct
15 Correct 240 ms 40660 KB Output is correct
16 Correct 409 ms 44664 KB Output is correct
17 Correct 253 ms 24536 KB Output is correct