oj.uz

Submission #987732

# Submission time Handle Problem Language Result Execution time Memory
987732 2024-05-23T13:23:04 Z ErJ Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 329 ms 30280 KB 
#include<bits/stdc++.h>
    
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define inf 1000000000000000
    
    
using namespace std;
    
    
    
string s;
    
bool test(string x, int i, int j){ // all in
    bool is = true;
    for(int k = i; k <= j; k++){
        if(x[k - i] != s[k]){
            is = false;
        }
    }
    return is;
}

ll P = 37;
ll MOD = 1000000007;
vi pref;
vi AKTP;
ll polyHash(ll a, ll b){
    ll ans = pref[b+ 1] - pref[a];
    ans %= MOD;
    if(ans < 0){
        ans += MOD;
    }
    return ans;
}

bool test2(ll a, ll b, ll i, ll j){
    if((polyHash(a, b) * AKTP[i - a]) % MOD == polyHash(i, j)){
        return true;
    }else{
        return false;
    }
}
    
int main(){
    int t;
    cin >> t;
    while(t--){
        cin >> s;
        int n = s.size();
        pref.clear();
        AKTP.clear();
        pref.resize(n + 1);
        pref[0] = 0;
        ll aktP = P;
        AKTP.resize(n + 1);
        AKTP[0] = 1;
        for(int i = 1; i < pref.size(); i++){
            ll val = (ll)s[i - 1] - 96;
            pref[i] = (pref[i - 1] + aktP * val) % MOD;
            AKTP[i] = aktP;
            aktP *= P;
            aktP %= MOD;
        }

        int ans = 0;
        int mid = n/2;
        string akt = "";
        ll from = 0;
        for(int i = 0; i < mid; i++){
            akt += s[i];
            if(test2(from, i, n - 1 - i,  n - 1 - (i - akt.size() + 1))){
                ans += 2;
                from = i + 1;
                akt = "";
            }
        }
        if(n %2 == 1) akt += "a";
        if(akt != ""){
            ans++;
        }
        cout << ans << endl;
    }
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int i = 1; i < pref.size(); i++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 329 ms 26892 KB Output is correct
15 Correct 187 ms 30280 KB Output is correct
16 Correct 313 ms 27496 KB Output is correct
17 Correct 169 ms 14272 KB Output is correct