oj.uz

Submission #916332

# Submission time Handle Problem Language Result Execution time Memory
916332 2024-01-25T16:56:43 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 5072 ms 52288 KB 
#include <bits/stdc++.h>
#define MAX 1000001
#define pb push_back
#define ins insert 
using namespace std; 
typedef long long ll; 
int n,q,t=1,m,n2,m2,k,x,y,z,x2,y2,z2,a[MAX],b[MAX],d[MAX],e[MAX],dp[1][2],tim,res;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[1];
//ll e[2001][2001];
//ll e1[1001][1001]; 
string s1,s2,s3;
const int mod = 998244353;
int N=201326611,M=402653189,K=26,N1,M1;
int powmod(int x,int y,int md){
    if(y==0){
        return 1;
    }
    x%=md;
    if(x==0){
        return 0;
    }
    int res=1;
    while(y>0){
        if(y%2){
            res=(1ll*res*x)%md;
        }
        y/=2;
        x=(1ll*x*x)%md;
    }
    return res;
}
int inv(int n,int md){
    return powmod(n,md-2,md);
}
int gh1(int l,int r){
    int h=(a[r]-a[l-1]+N)%N;
    h=(1ll*h*e[l-1])%N;
    return h; 
}
int gh2(int l,int r){
    int h=(b[r]-b[l-1]+M)%M;
    h=(1ll*h*d[l-1])%M;
    return h;
}
void solve(){
    cin >> s1;
    n=(int)s1.size(); 
    for(int i=0;i<n;i++){
        e[i]=inv(powmod(K,i,N),N); 
    }
    int h,h1,h2,h3; 
    h=h1=0; 
    h2=h3=1; 
    for(int i=0;i<n;i++){
        a[i+1]=((ll)a[i]+(1ll*(s1[i]-'a'+1)*h2)%N)%N;
        h2=(1ll*h2*K)%N; 
    }
    int l,r; 
    l=1; 
    r=n; 
    ll res=0; 
    while(r>=l){
        ll x=1; 
        while(l+x-1<r-x+1){
            if(gh1(l,l+x-1)==gh1(r-x+1,r)){
                break;
            }
            x++;
        }
        if(l+x-1<r-x+1){
            res+=2; 
            l+=x;
            r-=x; 
        }
        else{
            res++;
            break; 
        }
    }
    cout << res << "\n"; 
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    //USACO("diamond");
    //freopen("meta_game_input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> t;
    ll cnt1=1;
    while(t--){
        //cout << "Case #" << cnt1 << ": ";
        solve();
        cnt1++;
    }
    return 0;
}
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
ll b[51][51];
b[0][0] = 1;
    for (int n = 1; n <= 50; ++n){
        b[n][0] = b[n][n] = 1;
        for (int k = 1; k < n; ++k)
            b[n][k] = b[n - 1][k - 1] + b[n - 1][k];
    }
*/

Compilation message

palindromic.cpp: In function 'void solve()':
palindromic.cpp:52:9: warning: variable 'h' set but not used [-Wunused-but-set-variable]
   52 |     int h,h1,h2,h3;
      |         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33368 KB Output is correct
2 Correct 11 ms 33840 KB Output is correct
3 Correct 11 ms 33480 KB Output is correct
4 Correct 10 ms 33372 KB Output is correct
5 Correct 9 ms 33372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33368 KB Output is correct
2 Correct 11 ms 33840 KB Output is correct
3 Correct 11 ms 33480 KB Output is correct
4 Correct 10 ms 33372 KB Output is correct
5 Correct 9 ms 33372 KB Output is correct
6 Correct 11 ms 33368 KB Output is correct
7 Correct 9 ms 33372 KB Output is correct
8 Correct 11 ms 33372 KB Output is correct
9 Correct 10 ms 33372 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33368 KB Output is correct
2 Correct 11 ms 33840 KB Output is correct
3 Correct 11 ms 33480 KB Output is correct
4 Correct 10 ms 33372 KB Output is correct
5 Correct 9 ms 33372 KB Output is correct
6 Correct 11 ms 33368 KB Output is correct
7 Correct 9 ms 33372 KB Output is correct
8 Correct 11 ms 33372 KB Output is correct
9 Correct 10 ms 33372 KB Output is correct
10 Correct 52 ms 33628 KB Output is correct
11 Correct 35 ms 33572 KB Output is correct
12 Correct 50 ms 33628 KB Output is correct
13 Correct 45 ms 33372 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33368 KB Output is correct
2 Correct 11 ms 33840 KB Output is correct
3 Correct 11 ms 33480 KB Output is correct
4 Correct 10 ms 33372 KB Output is correct
5 Correct 9 ms 33372 KB Output is correct
6 Correct 11 ms 33368 KB Output is correct
7 Correct 9 ms 33372 KB Output is correct
8 Correct 11 ms 33372 KB Output is correct
9 Correct 10 ms 33372 KB Output is correct
10 Correct 52 ms 33628 KB Output is correct
11 Correct 35 ms 33572 KB Output is correct
12 Correct 50 ms 33628 KB Output is correct
13 Correct 45 ms 33372 KB Output is correct
14 Correct 5072 ms 52288 KB Output is correct
15 Correct 2676 ms 47500 KB Output is correct
16 Correct 4784 ms 51776 KB Output is correct
17 Correct 2614 ms 43516 KB Output is correct