oj.uz

Submission #479416

# Submission time Handle Problem Language Result Execution time Memory
479416 2021-10-11T16:50:52 Z tranxuanbach Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 223 ms 15956 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

#define hash __hash__

mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());
int randt(int l, int r){
    return rando() % (r - l + 1) + l;
}

const int N = 1e6 + 5, base = 31;
int mod;

inline void sadd(int& x, int y){
    if ((x += y) >= mod) x -= mod;
    return;
}

inline int add(int x, int y){
    if ((x += y) >= mod) x -= mod;
    return x;
}

inline void ssub(int& x, int y){
    if ((x -= y) < 0) x += mod;
    return;
}

inline int sub(int x, int y){
    if ((x -= y) < 0) x += mod;
    return x;
}

inline int mul(int x, int y){
    return 1ll * x * y % mod;
}

inline int binpow(int x, int y){
    int ans = 1;
    while (y){
        if (y & 1) ans = mul(ans, x);
        x = mul(x, x);
        y >>= 1;
    }
    return ans;
}

inline int inv(int x){
    return binpow(x, mod - 2);
}

#define div __div__
inline int div(int x, int y){
    return mul(x, binpow(y, mod - 2));
}

int fac[N], invfac[N];

void calfac(){
    fac[0] = invfac[0] = 1;
    For(i, 1, N){
        fac[i] = mul(fac[i - 1], i);
    }
    invfac[N - 1] = binpow(fac[N - 1], mod - 2);
    FordE(i, N - 2, 1){
        invfac[i] = mul(invfac[i + 1], i + 1);
    }
}

inline int C(int n, int k){
    if (n < 0 or k < 0 or k > n){
        return 0;
    }
    return mul(fac[n], mul(invfac[k], invfac[n - k]));
}

inline int P(int n, int k){
    if (n < 0 or k < 0 or k > n){
        return 0;
    }
    return mul(fac[n], invfac[n - k]);
}

bool isprime(int x){
    if (x <= 1){
        return 0;
    }
    if (x <= 3){
        return 1;
    }
    if (x % 2 == 0 or x % 3 == 0){
        return 0;
    }
    for (int i = 5; i * i <= x; i += 6){
        if (x % i == 0 or x % (i + 2) == 0){
            return 0;
        }
    }
    return 1;
}

int n;
string s;

int pwbase[N];
int hash[N];

int calhash(int l, int r){
    return sub(hash[r], mul(hash[l - 1], pwbase[r - l + 1]));
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
{
    mod = randt(500000000, 1000000000);
    while (!isprime(mod)){
        mod++;
    }
}
pwbase[0] = 1;
For(i, 1, N){
    pwbase[i] = mul(pwbase[i - 1], base);
}
int tests; cin >> tests; while (tests--){
    cin >> s; n = isz(s); s = ' ' + s;
    ForE(i, 1, n){
        hash[i] = add(mul(hash[i - 1], base), s[i] - 'a' + 1);
    }
    int l = 1, r = n, ll = 1, rr = n, ans = 0;
    while (ll < rr){
        if (calhash(l, ll) == calhash(rr, r)){
            ans += 2;
            l = ll + 1; r = rr - 1;
        }
        ll++; rr--;
    }
    if (l <= r){
        ans++;
    }
    cout << ans << endl;
}
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4172 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4172 KB Output is correct
5 Correct 9 ms 4172 KB Output is correct
6 Correct 8 ms 4172 KB Output is correct
7 Correct 8 ms 4172 KB Output is correct
8 Correct 8 ms 4132 KB Output is correct
9 Correct 8 ms 4172 KB Output is correct
10 Correct 10 ms 4300 KB Output is correct
11 Correct 9 ms 4300 KB Output is correct
12 Correct 10 ms 4300 KB Output is correct
13 Correct 10 ms 4304 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4172 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4172 KB Output is correct
5 Correct 9 ms 4172 KB Output is correct
6 Correct 8 ms 4172 KB Output is correct
7 Correct 8 ms 4172 KB Output is correct
8 Correct 8 ms 4132 KB Output is correct
9 Correct 8 ms 4172 KB Output is correct
10 Correct 10 ms 4300 KB Output is correct
11 Correct 9 ms 4300 KB Output is correct
12 Correct 10 ms 4300 KB Output is correct
13 Correct 10 ms 4304 KB Output is correct
14 Correct 207 ms 10088 KB Output is correct
15 Correct 120 ms 14424 KB Output is correct
16 Correct 223 ms 15956 KB Output is correct
17 Correct 107 ms 11716 KB Output is correct