Submission #983123

#	Time	Username	Problem	Language	Result	Execution time	Memory
983123		kh0i	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	471 ms	45248 KiB

palindromic

#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 (stderr)

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 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40