oj.uz

Submission #944321

# Submission time Handle Problem Language Result Execution time Memory
944321 2024-03-12T14:46:18 Z fzyzzz_z Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 750 ms 52124 KB 
#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

const ll inf = 1e18 + 50;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct hashBasic {
    const long long M = 1e9 + 7; 
    const long long B = uniform_int_distribution<long long>(0, M - 1)(rng);
    vector<long long> mpow, hash; 
    long long mul(long long a, long long b) {
        __int128 x = (__int128)a * b; return x % M; 
        return (a * b) % M; 
    }

    hashBasic(string s) {
        hash = vector<long long> (s.size() + 1); 
        mpow.push_back(1); hash[0] = 0; 
        while (mpow.size() < s.size()) {
            mpow.push_back(mul(mpow.back(), B)); }
        for (int i = 0; i < s.size(); ++i) {
            hash[i+1] = (mul(hash[i], B) + s[i]) % M; }
    } 
    
    long long get(int l, int r) { //on [l, r]
        r++; 
        long long ret = hash[r] - mul(hash[l], mpow[r - l]); 
        return (ret + M) % M; 
    }
}; 

void solve() {
    string s; 
    cin >> s; 
    int n = (int) s.size(); 
    hashBasic h1(s), h2(s); 

    int ans = 0; 
    int l = 0, r = n - 1, l0 = -1, r0 = n; 
    while (l < r) {
        if (h1.get(l0 + 1, l) == h1.get(r, r0 - 1) && h2.get(l0 + 1, l) == h2.get(r, r0 - 1)) {
            ans += 2; 
            l0 = l; 
            r0 = r; 
        }
        l++; 
        r--; 
    }
    if (l0 + 1 < r0) ans++; 

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; 
    cin >> t; 
    while (t--) {
        solve(); 
    }

    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 8 ms 1048 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 7 ms 1024 KB Output is correct
13 Correct 6 ms 868 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 8 ms 1048 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 7 ms 1024 KB Output is correct
13 Correct 6 ms 868 KB Output is correct
14 Correct 750 ms 52124 KB Output is correct
15 Correct 381 ms 46220 KB Output is correct
16 Correct 669 ms 50820 KB Output is correct
17 Correct 407 ms 27224 KB Output is correct