oj.uz

Submission #224100

# Submission time Handle Problem Language Result Execution time Memory
224100 2020-04-17T08:02:05 Z SorahISA Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 535 ms 20780 KB 
#pragma GCC optimize ("Ofast", "unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;
 
#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0)
 
const int mod = 1E9 + 9;
const int p = 1000;
 
void solve() {
    int n;
    string s;
    cin >> s, n = s.size();
    
    if (n == 1) {cout << 1 << "\n"; return;}
    
    int Hash[n];
    for (int i = 0; i < n; ++i) Hash[i] = ((i ? Hash[i-1] : 0) * p + s[i]) % mod;
    
    auto fastpow = [](int base, int pow, int ans = 1) {
        while (pow) {
            if (pow & 1) ans = ans * base % mod;
            base = base * base % mod, pow >>= 1;
        }
        return ans;
    };
    
    auto getHash = [&](int L, int len) {
        return (Hash[L+len-1] - (L ? Hash[L-1] * fastpow(p, len) % mod : 0) + mod) % mod;
    };
    
    // for (int i = 0; i < n; ++i) cerr << getHash(i, 1) << " \n"[i == n-1];
    
    int tok = 0, ans = 0;
    for (int i = 0; i < n/2; ++i) {
        if (getHash(tok, i-tok+1) == getHash(n-i-1, i-tok+1)) {
            ans += 2;
            tok = i + 1;
            if (n%2 and i == n/2-1) ++ans;
        }
        else if (i == n/2-1) ++ans;
    }
    
    cout << ans << "\n";
}
 
int32_t main() {
    fastIO();
    
    int t;
    cin >> t;
    while (t--) solve();
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 7 ms 560 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 7 ms 560 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 353 ms 20780 KB Output is correct
15 Correct 275 ms 15636 KB Output is correct
16 Correct 535 ms 19708 KB Output is correct
17 Correct 103 ms 11080 KB Output is correct