oj.uz

Submission #988590

# Submission time Handle Problem Language Result Execution time Memory
988590 2024-05-25T08:38:35 Z parlimoos Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 10000 ms 11172 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][50] , 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) + 50 ; i++) mods.pb(i);
}
arr(2) f(int l , int r){
    fill(&inf[0][0] , &inf[1][50] , 0);
    for(int i1 = l , i2 = r ;; i1++ , i2--){
        if(i1 >= i2) return {l , r};
        for(int i = 0 ; i < 50 ; 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 < 50 ; 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 348 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 348 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 4 ms 348 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 4 ms 348 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 159 ms 604 KB Output is correct
11 Correct 148 ms 600 KB Output is correct
12 Correct 170 ms 604 KB Output is correct
13 Correct 38 ms 600 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 4 ms 348 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 159 ms 604 KB Output is correct
11 Correct 148 ms 600 KB Output is correct
12 Correct 170 ms 604 KB Output is correct
13 Correct 38 ms 600 KB Output is correct
14 Execution timed out 10053 ms 11172 KB Time limit exceeded
15 Halted 0 ms 0 KB -