oj.uz

Submission #1096282

# Submission time Handle Problem Language Result Execution time Memory
1096282 2024-10-04T08:14:48 Z Zero_OP Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 137 ms 28720 KB 
#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(v) "[" #v " = " << (v) << "]"
#define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define repd(i, r, l) for(int i = (r) - 1; i >= (l); --i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using ld = long double;

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }  return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

template<int dimension, typename T>
struct tensor : public vector<tensor<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {}
};

template<typename T>
struct tensor<1, T> : public vector<T> {
    tensor(int n = 0, T val = T()) : vector<T>(n, val) {}
};

const int MAX = 1e6 + 5;
const int MOD[2] = {(int)1e9 + 9, (int)1e9 + 7};
const int BASE[2] = {31, 37};

int add(int a, int b, const int& mod){
    return a + b < mod ? a + b : a + b - mod;
}

int subtract(int a, int b, const int& mod){
    return a < b ? a - b + mod : a - b;
}

int multiply(int a, int b, const int& mod){
    return 1LL * a * b % mod;
}

int n, pw[2][MAX], h[2][MAX];
string s;

int code(char c){
    return c - 'a' + 1;
}

void init(){
    for(int i = 1; i <= n; ++i){
        for(int j : {0, 1}){
            h[j][i] = add(multiply(h[j][i - 1], BASE[j], MOD[j]), code(s[i]), MOD[j]);
        }
    }
}

int getHash(int type, int l, int r){
    return subtract(h[type][r], multiply(h[type][l - 1], pw[type][r - l + 1], MOD[type]), MOD[type]);
}

bool same(int l1, int r1, int l2, int r2){
    return getHash(0, l1, r1) == getHash(0, l2, r2) && getHash(1, l1, r1) == getHash(1, l2, r2);
}

int solve(int l, int r){
    if(l > r) return 0;
    if(l == r) return 1;

    int k = r - l + 1;
    for(int i = 1; i < k; ++i){
        if(same(l, l + i - 1, r - i + 1, r)){
            return solve(l + i, r - i) + 2;
        }
    }

    return 1;
}

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

    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }

    pw[0][0] = 1;
    pw[1][0] = 1;
    FOR(i, 1, 1000000){
        pw[0][i] = multiply(pw[0][i - 1], BASE[0], MOD[0]);
        pw[1][i] = multiply(pw[1][i - 1], BASE[1], MOD[1]);
    }

    int t;
    cin >> t;
    while(t--){
        cin >> s;
        n = sz(s);
        s = '?' + s;
        init();
        cout << solve(1, n) << '\n';
    }

    return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 7 ms 8044 KB Output is correct
4 Correct 8 ms 8280 KB Output is correct
5 Correct 8 ms 8284 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 7 ms 8044 KB Output is correct
4 Correct 8 ms 8280 KB Output is correct
5 Correct 8 ms 8284 KB Output is correct
6 Correct 8 ms 8280 KB Output is correct
7 Correct 8 ms 8284 KB Output is correct
8 Correct 8 ms 8284 KB Output is correct
9 Correct 8 ms 8280 KB Output is correct
10 Correct 9 ms 8280 KB Output is correct
11 Correct 8 ms 8424 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 8 ms 8244 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 7 ms 8044 KB Output is correct
4 Correct 8 ms 8280 KB Output is correct
5 Correct 8 ms 8284 KB Output is correct
6 Correct 8 ms 8280 KB Output is correct
7 Correct 8 ms 8284 KB Output is correct
8 Correct 8 ms 8284 KB Output is correct
9 Correct 8 ms 8280 KB Output is correct
10 Correct 9 ms 8280 KB Output is correct
11 Correct 8 ms 8424 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 8 ms 8244 KB Output is correct
14 Correct 137 ms 27684 KB Output is correct
15 Correct 80 ms 23056 KB Output is correct
16 Correct 130 ms 28720 KB Output is correct
17 Correct 83 ms 18516 KB Output is correct