Submission #1225771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225771		takoshanava	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	152 ms	18972 KiB

palindromic

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
#define ull unsigned long long
using namespace std;

const ull BASE = 911;
const int N = 1e6 + 5;
ull p[N], h[N], rh[N];

void bld(string s) {
    int n = s.size();
    h[0] = s[0];
    for (int i = 1; i < n; i++) {
        h[i] = h[i - 1] * BASE + s[i];
    }
}
//void bldrev(string s) {
//    int n = s.size();
//    rh[n - 1] = s[n - 1];
//    for (int i = n - 2; i >= 0; i--) {
//        rh[i] = rh[i + 1] * BASE + s[i];
//    }
//}

ull get1(int l, int r) {
    if (l == 0) return h[r];
    return h[r] - h[l - 1] * p[r - l + 1];
}

//ull get2(int l, int r) {
//    if (r == h[0]) return rh[l];
//    return rh[l] - rh[r + 1] * p[r - l + 1];
//}

signed main() {
    p[0] = 1;
    for (int i = 1; i <= N; i++) {
        p[i] = p[i - 1] * BASE;
    }
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();
        int l = 0, r = n - 1;
        int res = 0;
        bld(s);
        //bldrev(s);

        while (l < r) {
            bool good = false;
            for (int len = 1; l + len - 1 < r - len + 1; len++) {
                int l1 = l, r1 = l + len - 1;
                int l2 = r - len + 1, r2 = r;
                if (get1(l1, r1) == get1(l2, r2)) {
                    res += 2;
                    l += len;
                    r -= len;
                    good = true;
                    break;
                }
            }
            if (!good) break;
        }

        if (l <= r) res++;
        cout << res << endl;
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:41:14: warning: iteration 1000004 invokes undefined behavior [-Waggressive-loop-optimizations]
   41 |         p[i] = p[i - 1] * BASE;
      |         ~~~~~^~~~~~~~~~~~~~~~~
palindromic.cpp:40:23: note: within this loop
   40 |     for (int i = 1; i <= N; i++) {
      |                     ~~^~~~

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