oj.uz

Submission #1015539

# Submission time Handle Problem Language Result Execution time Memory
1015539 2024-07-06T13:43:41 Z 0pt1mus23 Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 120 ms 28620 KB 
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 159766601, sze = 2e6+10, inf = INT_MAX, P = 1453;

int prime[sze];
int hash[sze];

int qry(int l,int r,int lx,int rx){
    int a = (prime[l] * 1LL * (hash[rx+1] - hash[lx])%mod + mod) %mod;
    int b = (prime[lx] * 1LL * (hash[r+1] - hash[l])%mod + mod)%mod;
    // cout<<a<<" "<<b<<endl;
    return (a==b);
}

void mal(){
    string s;
    cin>>s;
    int n= s.size();
    prime[0]=1;
    for(int i=1;i<=n;i++){
        prime[i]=(prime[i-1]*P)%mod;
    }
    for(int i =0;i<n;i++){
        hash[i+1]=(hash[i] + (((s[i]-'a'+1) * prime[i]) %mod) + mod )%mod;
    }
    int ans=0;
    int l =0;
    int r = n-1;
    for(int i =0;i<n;i++){
        // cout<<i<<" -> "<<l<<":"<<r<<endl;
        if(l>=r){
            break;
        }
        int len = i-l +1;
        int l1 = l;
        int r1=i;
        int l2 = r-len +1;
        int r2=r;
        
        if(r1>=l2){
            break;
        }
        int f = qry(l1,r1,l2,r2);
        // cout<<l1<<":"<<r1<<" , "<<l2<<":"<<r2<<" = "<<f<<endl;
        
        if(f){
            ans+=2;
            l=i+1;
            r = l2 -1;
        }
    }
    if(l<=r){
        ans++;
    }
    drop(ans);
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    clock_t z = clock();
    int tt = 1;
    cin>>tt;
    
    while(tt--){
        mal();        
    }
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:69:13: warning: unused variable 'z' [-Wunused-variable]
   69 |     clock_t z = clock();
      |             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 116 ms 28424 KB Output is correct
15 Correct 66 ms 26464 KB Output is correct
16 Correct 120 ms 28620 KB Output is correct
17 Correct 70 ms 17516 KB Output is correct