oj.uz

Submission #988592

# Submission time Handle Problem Language Result Execution time Memory
988592 2024-05-25T08:41:03 Z parlimoos Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 5611 ms 16384 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

vector<int> mods , s;
int inf[2][10] , t , n;

int Sum(int a , int b , int mod){
    int res = a + b;
    if(res > mod) return res - mod;
    if(res < 0) return res + mod;
    return res;
}
int Mul(int a , int b , int mod){
    return (1ll * a * 1ll * b) % mod;
}
int Pow(int a , int b , int mod){
    int res = 1;
    while(b){
        if(b & 1) res = Mul(res , a , mod);
        a = Mul(a , a , mod) , b >>= 1;
    }
    return res;
}
void initMods(){
    for(int i = int(1e9) ; i < int(1e9) + 10 ; i++) mods.pb(i);
}
arr(2) f(int l , int r){
    fill(&inf[0][0] , &inf[1][10] , 0);
    for(int i1 = l , i2 = r ;; i1++ , i2--){
        if(i1 >= i2) return {l , r};
        for(int i = 0 ; i < 10 ; i++){
            inf[0][i] = Mul(inf[0][i] , 26 , mods[i]);
            inf[0][i] = Sum(inf[0][i] , s[i1] % mods[i] , mods[i]);
            inf[1][i] = Sum(inf[1][i] , Mul(s[i2] , Pow(26 , r - i2 , mods[i]) , mods[i]) , mods[i]);
        }
        bool flg = 1;
        for(int i = 0 ; i < 10 ; i++) if(inf[0][i] != inf[1][i]) flg = 0;
        if(flg) return {i1 + 1 , i2 - 1};
    }
}

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

    initMods();
    cin >> t;
    for(int ii = 0 ; ii < t ; ii++){
        s.cl();
        string d;
        cin >> d;
        for(char c : d) s.pb(int(c - 'a'));
        int o = 0 , l = 0 , r = (int)s.size() - 1;
        while(true){
            if(l > r) break;
            arr(2) d = f(l , r);
            if(d[0] == l and d[1] == r){
                o++;
                break;
            }
            l = d[0] , r = d[1] , o += 2;
        }
        cout << o << endl;
    }
}

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 32 ms 348 KB Output is correct
11 Correct 30 ms 344 KB Output is correct
12 Correct 34 ms 348 KB Output is correct
13 Correct 8 ms 348 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 32 ms 348 KB Output is correct
11 Correct 30 ms 344 KB Output is correct
12 Correct 34 ms 348 KB Output is correct
13 Correct 8 ms 348 KB Output is correct
14 Correct 4602 ms 11840 KB Output is correct
15 Correct 4741 ms 12088 KB Output is correct
16 Correct 5611 ms 16384 KB Output is correct
17 Correct 479 ms 9088 KB Output is correct