Submission #1157446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157446		CodeLakVN	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	98 ms	19572 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;

#define task "PALINDROMIC"
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define ll long long

const int N = (int)1e6 + 5;
const int base = 311;
const int MOD = (int)1e9 + 7;

int n;
string s;

ll hsh[N], poww[N];

void prepare() {
    hsh[0] = 0;
    n = s.size();
    s = " " + s;
    FOR(i, 1, n) hsh[i] = (hsh[i - 1] * base + s[i] - 'a' + 1) % MOD;
}

ll get(int l, int r) {
    return (hsh[r] - hsh[l - 1] * poww[r - l + 1] + 1LL * MOD * MOD) % MOD;
}

void solve() {
    int l = 1, r = n;
    int ans = 0;
    bool f = false;
    FOR(i, 1, n / 2) {
        if (r - (i - l + 1) + 1 < l) {
            ans++;
            f = true;
            break;
        }
        if (get(l, i) == get(r - (i - l + 1) + 1, r)) {
            ans += 2;
            r = r - (i - l + 1);
            l = i + 1;
        }
    }

    if (!f && r >= l) ans++;

    cout << ans << "\n";
}

int main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    poww[0] = 1;
    FOR(i, 1, 1000000) poww[i] = poww[i - 1] * base % MOD;

    int t;
    cin >> t;
    while (t--) {
        cin >> s;
        prepare();
        solve();
    }

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40