oj.uz

Submission #1116566

# Submission time Handle Problem Language Result Execution time Memory
1116566 2024-11-21T20:16:33 Z PagodePaiva Palindromic Partitions (CEOI17_palindromic) C++17
35 / 100
 10000 ms 18968 KB 
#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second

using namespace std;

const int N = 1000010;
const int p = 1e9+7;
const int q = 1e9+9;
const int b = 127;
int pot[N][2];

int binpow(int a, int b, int mod){
    if(b == 0) return q;
    int t = binpow(a, b/2, mod);
    t *= t;
    t %= mod;
    if(b%2 == 0) return t;
    else return (a*t)%mod;
}

struct hs{
    pair <int, int> pref[N];
    void build(string s){
        pref[0] = {0, 0};
        for(int i = 0;i < s.size();i++){
            pref[i+1].fr = (pref[i].fr + ((s[i]-'a'+1)*pot[i][0])%p)%p;
            pref[i+1].sc = (pref[i].sc+((s[i]-'a'+1)*pot[i][1])%q)%q;
        }
    }
    pair <int, int> query(int l, int r){
        l++;
        r++;
        return {(((pref[r].first+p-pref[l-1].first)%p)*binpow(pot[l-1][0], p-2, p))%p, (((pref[r].second+q-pref[l-1].second)%q)*binpow(pot[l-1][1], q-2, q))%q};
    }
    bool get(int l1, int r1, int l2, int r2){
        if(query(l1, r1) == query(l2, r2)) return true;
        return false;
    }
} h;
int res[N];

void solve(){
    string s;
    cin >> s;
    h.build(s);
    int n = s.size();
    if(n == 1){
        cout << 1 << '\n';
        return;
    }
    int st = (n%2 == 0 ? (n-1)/2 : n/2);
    res[st+1] = 0;
    res[st] = (n%2 == 1 ? 1 : (s[st] == s[st+1] ? 2 : 1));
    for(int i = st-1;i >= 0;i--){
        int r = (n%2 == 1 ? st+st-i : st+st-i+1);
        //cout << i << ' ' << r << '\n';
        res[i] = 1;
        for(int j = i;j <= st;j++){
          //  cout << i << ' ' << j << ' ' << r-(j-i) << ' ' << r << ' ' << h.get(i, j, r-(j-i), r) << '\n';
            if(h.get(i, j, r-(j-i), r)){
                res[i] = max(res[i], res[j+1]+2);
            }
        }
    }
    cout << res[0] << '\n';
}
int32_t main(){
    int t;
    cin >> t;
    pot[0][0] = pot[0][1] = 1;
    for(int i = 1;i < N;i++){
        pot[i][0] = (pot[i-1][0]*b)%p;
        pot[i][1] = (pot[i-1][1]*b)%q;
    }
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18768 KB Output is correct
2 Correct 9 ms 18652 KB Output is correct
3 Correct 8 ms 18768 KB Output is correct
4 Correct 10 ms 18768 KB Output is correct
5 Correct 10 ms 18936 KB Output is correct
6 Correct 96 ms 18888 KB Output is correct
7 Correct 53 ms 18768 KB Output is correct
8 Correct 87 ms 18768 KB Output is correct
9 Correct 73 ms 18768 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18768 KB Output is correct
2 Correct 9 ms 18652 KB Output is correct
3 Correct 8 ms 18768 KB Output is correct
4 Correct 10 ms 18768 KB Output is correct
5 Correct 10 ms 18936 KB Output is correct
6 Correct 96 ms 18888 KB Output is correct
7 Correct 53 ms 18768 KB Output is correct
8 Correct 87 ms 18768 KB Output is correct
9 Correct 73 ms 18768 KB Output is correct
10 Execution timed out 10041 ms 18968 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18768 KB Output is correct
2 Correct 9 ms 18652 KB Output is correct
3 Correct 8 ms 18768 KB Output is correct
4 Correct 10 ms 18768 KB Output is correct
5 Correct 10 ms 18936 KB Output is correct
6 Correct 96 ms 18888 KB Output is correct
7 Correct 53 ms 18768 KB Output is correct
8 Correct 87 ms 18768 KB Output is correct
9 Correct 73 ms 18768 KB Output is correct
10 Execution timed out 10041 ms 18968 KB Time limit exceeded
11 Halted 0 ms 0 KB -