Submission #519339

#	Time	Username	Problem	Language	Result	Execution time	Memory
519339		hoanghq2004	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	176 ms	20752 KiB

palindromic

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e6 + 10;
const int base = 31;
const int mod = 1e9 + 7;

int h[N], power[N];

int get(int L, int R) {
    return (0LL + h[R] - 1LL * h[L - 1] * power[R - L + 1] + 1LL * mod * mod) % mod;
}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 1; i <= n; ++i) h[i] = (1LL * h[i - 1] * base + s[i - 1] - 'a' + 1) % mod;
    power[0] = 1;
    for (int i = 1; i <= n; ++i) power[i] = 1LL * power[i - 1] * base % mod;
    int i = 1, ans = 0;
    while (1) {
        int j = n - i + 1;
        for (int len = 0; len <= n; ++len) {
            if (get(i, i + len) == get(j - len, j)) {
                ans += (i + len != j ? 2 : 1);
                i += len;
                j -= len;
                break;
            }
        }
        ++i, --j;
        if (i > j) break;
    }
    cout << ans << '\n';
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
}

Compilation message (stderr)

palindromic.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
palindromic.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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