oj.uz

Submission #680653

# Submission time Handle Problem Language Result Execution time Memory
680653 2023-01-11T12:31:55 Z sysia Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 841 ms 75372 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;

struct Hash{
    vector<int>h = {0}, p = {1}, inv = {1};
    int base, mod;

    int mul(int a, int b){
        return (a*b)%mod;
    }

    void add(int &a, int b){
        a += b;
        if (a >= mod) a -= mod;
    }

    int sub2(int a, int b){
        a -= b;
        if (a < 0) a += mod;
        return a;
    }

    int power(int a, int b){
        if (!b) return 1LL;
        int k = power(a, b/2);
        k = mul(k, k);
        if (b&1) k = mul(k, a);
        return k;
    }

    int add2(int a, int b){
        add(a, b);
        return a;
    }

    Hash(string s, int _b, int _m){
        base = _b, mod = _m;
        int n = (int)s.size();
        s = "$"+s;
        int I = power(base, mod-2);
        for (int i = 1; i<=n; i++){
            p.emplace_back(mul(p.back(), base));
            inv.emplace_back(mul(inv.back(), I));
            h.emplace_back(add2(h.back(), mul(s[i], p[i])));
        }
    }

    int ask(int a, int b){
        return mul(sub2(h[b], h[a-1]), inv[a-1]);
    }  
};

void solve(){
    string s; cin >> s;
   
    Hash H1(s, 2137, 1e9+7);
    Hash H2(s, 2137, 1e9+9);
    int n = (int)s.size(); 
    s = "$"+s;
    int L = 1, R = n;
    int ans = 0;
    while (R >= L){
        int a = L, b = R;
        while (a <= R && b >= L){
            if (H1.ask(L, a) == H1.ask(b, R) && H2.ask(L, a) == H2.ask(b, R)){
                if (a != R) {
                    ans += 2;
                    L = a+1;
                    R = b-1;
                } else {
                    ans++;
                    cout << ans << "\n";
                    return;
                }
                break;
            }
            a++;b--;
        }
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 10 ms 1216 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 8 ms 1240 KB Output is correct
13 Correct 9 ms 1168 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 10 ms 1216 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 8 ms 1240 KB Output is correct
13 Correct 9 ms 1168 KB Output is correct
14 Correct 841 ms 67488 KB Output is correct
15 Correct 443 ms 62388 KB Output is correct
16 Correct 779 ms 75372 KB Output is correct
17 Correct 536 ms 48152 KB Output is correct