oj.uz

Submission #468535

# Submission time Handle Problem Language Result Execution time Memory
468535 2021-08-28T16:40:04 Z idk321 Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 11 ms 4220 KB 
#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];
int 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];

    int hash1 = 0;
    int 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));
        }
    }

    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

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:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int i = 0; i < s.size() / 2 + 1; i++) res[i] = 0;
      |                         ~~^~~~~~~~~~~~~~~~~~
palindromic.cpp:58:13: warning: unused variable 'cres' [-Wunused-variable]
   58 |         int cres = 0;
      |             ^~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4208 KB Output is correct
2 Incorrect 11 ms 4220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4208 KB Output is correct
2 Incorrect 11 ms 4220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4208 KB Output is correct
2 Incorrect 11 ms 4220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4208 KB Output is correct
2 Incorrect 11 ms 4220 KB Output isn't correct
3 Halted 0 ms 0 KB -