oj.uz

Submission #989711

# Submission time Handle Problem Language Result Execution time Memory
989711 2024-05-28T15:54:49 Z steveonalex Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 180 ms 43692 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 const long N = 1e6 + 69;
 const long MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
 const long BASE = 307;
  
 ll pow1[N], pow2[N];
 void prepare(){
     pow1[0] = pow2[0] = 1;
     for(long i = 1; i<N; ++i){
         pow1[i] = pow1[i-1] * BASE % MOD1;
         pow2[i] = pow2[i-1] * BASE % MOD2;
     }
 }
  
 struct Hash{
     long n;
     vector<ll> hash1, hash2;
  
     Hash(){}
  
     Hash(string s){
         n = s.size();
         hash1.resize(n+1), hash2.resize(n+1);
         for(long i = 1; i<=n; ++i){
             hash1[i] = (hash1[i-1] + s[i-1] * pow1[i-1]) % MOD1;
             hash2[i] = (hash2[i-1] + s[i-1] * pow2[i-1]) % MOD2;
         }
     }
  
     ll get1(long l, long r){
         return (hash1[r] - hash1[l - 1] + MOD1) * pow1[N - l] % MOD1;
     }
     ll get2(long l, long r){
         return (hash2[r] - hash2[l - 1] + MOD2) * pow2[N - l] % MOD2;
     }
     ll getCode(long l, long r){return get1(l, r) * MOD2 + get2(l, r);}
 };
 

int solve(){
    string s; cin >> s;
    int n = s.size();
    Hash x(s);

    int ans = 0;
    bool check = false;
    pair<int, int> last = {1, n};
    for(int i = 0; i<n/2; ++i){
        if (x.getCode(last.first, i+1) == x.getCode(n - i, last.second)){
            ans++;
            last.first = i + 2;
            last.second = n - i - 1;
            if ((i + 1) * 2 == n) check = true;
        }
    }
    if (check) return ans * 2;
    return ans * 2 + 1;
}
 
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    prepare();

    int t; cin >> t; 
    while(t--) cout << solve() << "\n";
 
 
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15960 KB Output is correct
2 Correct 12 ms 16220 KB Output is correct
3 Correct 10 ms 15960 KB Output is correct
4 Correct 10 ms 15964 KB Output is correct
5 Correct 10 ms 16116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15960 KB Output is correct
2 Correct 12 ms 16220 KB Output is correct
3 Correct 10 ms 15960 KB Output is correct
4 Correct 10 ms 15964 KB Output is correct
5 Correct 10 ms 16116 KB Output is correct
6 Correct 11 ms 15960 KB Output is correct
7 Correct 10 ms 15960 KB Output is correct
8 Correct 10 ms 15964 KB Output is correct
9 Correct 10 ms 15964 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15960 KB Output is correct
2 Correct 12 ms 16220 KB Output is correct
3 Correct 10 ms 15960 KB Output is correct
4 Correct 10 ms 15964 KB Output is correct
5 Correct 10 ms 16116 KB Output is correct
6 Correct 11 ms 15960 KB Output is correct
7 Correct 10 ms 15960 KB Output is correct
8 Correct 10 ms 15964 KB Output is correct
9 Correct 10 ms 15964 KB Output is correct
10 Correct 11 ms 16384 KB Output is correct
11 Correct 11 ms 16328 KB Output is correct
12 Correct 11 ms 16376 KB Output is correct
13 Correct 11 ms 16340 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15960 KB Output is correct
2 Correct 12 ms 16220 KB Output is correct
3 Correct 10 ms 15960 KB Output is correct
4 Correct 10 ms 15964 KB Output is correct
5 Correct 10 ms 16116 KB Output is correct
6 Correct 11 ms 15960 KB Output is correct
7 Correct 10 ms 15960 KB Output is correct
8 Correct 10 ms 15964 KB Output is correct
9 Correct 10 ms 15964 KB Output is correct
10 Correct 11 ms 16384 KB Output is correct
11 Correct 11 ms 16328 KB Output is correct
12 Correct 11 ms 16376 KB Output is correct
13 Correct 11 ms 16340 KB Output is correct
14 Correct 169 ms 43692 KB Output is correct
15 Correct 91 ms 38240 KB Output is correct
16 Correct 180 ms 41672 KB Output is correct
17 Correct 88 ms 31068 KB Output is correct