oj.uz

Submission #961184

# Submission time Handle Problem Language Result Execution time Memory
961184 2024-04-11T16:16:36 Z LucaIlie Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 524 ms 26620 KB 
#include <bits/stdc++.h>

using namespace std;

struct hasher {
    int mod, b;
    vector<int> hashh, put;

    hasher( string s, int _mod, int _b ) {
        mod = _mod;
        b = _b;

        hashh.resize( s.size() + 1 );
        put.resize( s.size() + 1 );

        put[0] = 1;
        hashh[0] = 0;
        for ( int i = 1; i <= s.size(); i++ ) {
            put[i] = (long long)put[i - 1] * b % mod;
            hashh[i] = ((long long)hashh[i - 1] * b + s[i - 1] - 'a') % mod;
        }
    }

    int getHash( int l, int r ) {
        return (hashh[r + 1] - (long long)hashh[l] * put[r - l + 1] % mod + mod) % mod;
    }
};

const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int b1 = 37;
const int b2 = 31;

int main() {
    int t;

    cin >> t;
    while ( t-- ) {
        string s;

        cin >> s;
        hasher hash1( s, mod1, b1 );
        hasher hash2( s, mod2, b2 );

        int l = 0, r = s.size() - 1, cuv = 0;
        while ( l <= r ) {
            int i = 1;
            while ( i <= (r - l + 1) / 2 ) {
                if ( hash1.getHash( l, l + i - 1 ) == hash1.getHash( r - i + 1, r ) && hash2.getHash( l, l + i - 1 ) == hash2.getHash( r - i + 1, r ) )
                    break;
                i++;
            }
            if ( i <= (r - l + 1) / 2 ) {
                l += i;
                r -= i;
                cuv += 2;
            } else {
                cuv++;
                break;
            }
        }

        cout << cuv << "\n";
    }

    return 0;
}

Compilation message

palindromic.cpp: In constructor 'hasher::hasher(std::string, int, int)':
palindromic.cpp:18:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for ( int i = 1; i <= s.size(); i++ ) {
      |                          ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 5 ms 620 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 576 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 5 ms 620 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 576 KB Output is correct
14 Correct 524 ms 26620 KB Output is correct
15 Correct 264 ms 23024 KB Output is correct
16 Correct 468 ms 26232 KB Output is correct
17 Correct 295 ms 15112 KB Output is correct