oj.uz

Submission #988591

# Submission time Handle Problem Language Result Execution time Memory
988591 2024-05-25T08:39:37 Z parlimoos Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 10000 ms 8240 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][40] , 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) + 40 ; i++) mods.pb(i);
}
arr(2) f(int l , int r){
    fill(&inf[0][0] , &inf[1][40] , 0);
    for(int i1 = l , i2 = r ;; i1++ , i2--){
        if(i1 >= i2) return {l , r};
        for(int i = 0 ; i < 40 ; 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 < 40 ; 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 344 KB Output is correct
5 Correct 1 ms 348 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 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 3 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 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 125 ms 580 KB Output is correct
11 Correct 121 ms 552 KB Output is correct
12 Correct 135 ms 348 KB Output is correct
13 Correct 30 ms 344 KB Output is correct

Subtask #4
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 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 125 ms 580 KB Output is correct
11 Correct 121 ms 552 KB Output is correct
12 Correct 135 ms 348 KB Output is correct
13 Correct 30 ms 344 KB Output is correct
14 Execution timed out 10017 ms 8240 KB Time limit exceeded
15 Halted 0 ms 0 KB -