Submission #162252

#	Time	Username	Problem	Language	Result	Execution time	Memory
162252		karma	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	174 ms	28796 KiB

palindromic

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(1e6) + 7;
const int mod = int(1e9) + 9;
const ll sqrMod = 1ll * mod * mod;
const ll Base = 33;
typedef pair<int, int> pii;

ll Hash[N], p[N];
string s;
int n;

int GetHash(int l, int r) {return (Hash[r] - Hash[l - 1] * p[r - l + 1] + sqrMod) % mod;}

void Solve() {
    cin >> s; s = ' ' + s;
    n = int(s.size()) - 1;
    for(int i = 1; i <= n; ++i) Hash[i] = (Hash[i - 1] * Base + s[i] - 'a') % mod;
    int i = 1, j = n, len = 1, res = 0;
    while(i <= j) {
        if(GetHash(i, i + len - 1) == GetHash(j - len + 1, j)) {
           if(i + len - 1 < j - len + 1) res += 2;
           else ++res;
           //cout << i << ' ' << j << ' ' << len << '\n';
           i = i + len; j = j - len; len = 1;
        } else ++len;
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    p[0] = 1;
    for(int i = 1; i < N; ++i) p[i] = p[i - 1] * Base % mod;
    int nTest; cin >> nTest;
    while(nTest --) Solve();
}

Compilation message (stderr)

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

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