Submission #468650

#	Time	Username	Problem	Language	Result	Execution time	Memory
468650		idk321	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	119 ms	44404 KiB

palindromic

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

string s;
const int N = 1000001;
const int MINF = -1000000000;
const int MOD = 1000000007;
const int P = 29;
int res[N];
int vis[N];
ll power[N];

int calc(int n) {
    if (n == s.size() / 2) {
        if (s.size() % 2 == 1) return 1;
        return 0;
    }
    if (res[n]) return res[n];

    ll hash1 = 0;
    ll hash2 = 0;
    int j = 0;
    int cres = 1;
    for (int i = n; i < s.size() / 2; i++, j++) {
        hash2 *= P;
        hash2 %= MOD;
        hash1 += (s[i] - 'a') * power[j];
        hash1 %= MOD;
        hash2 += s[s.size() - 1 - i] - 'a';
        hash2 %= MOD;
        //cout << i << " " << hash1 << " " << hash2 << " " << s.size()<< endl;
        if (hash1 == hash2) {
            cres = max(cres, 2 + calc(i + 1));
            break;
        }
    }

    res[n] = cres;
    return res[n];
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    power[0] = 1;
    for (int i = 1; i <N; i++) {
        power[i] = power[i - 1] * P;
        power[i] %= MOD;
    }

    int t;
    cin >> t;
    for (int t1 = 0; t1 < t; t1++) {
        cin >> s;
        int cres = 0;

        for (int i = 0; i < s.size() / 2 + 1; i++) res[i] = 0;
        cout << calc(0) << "\n";
    }
}

/*
4
bonobo
deleted
racecar
racecars
*/

Compilation message (stderr)

palindromic.cpp: In function 'int calc(int)':
palindromic.cpp:16:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     if (n == s.size() / 2) {
      |         ~~^~~~~~~~~~~~~~~
palindromic.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = n; i < s.size() / 2; i++, j++) {
      |                     ~~^~~~~~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i = 0; i < s.size() / 2 + 1; i++) res[i] = 0;
      |                         ~~^~~~~~~~~~~~~~~~~~
palindromic.cpp:59:13: warning: unused variable 'cres' [-Wunused-variable]
   59 |         int cres = 0;
      |             ^~~~

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