oj.uz

Submission #1015538

# Submission time Handle Problem Language Result Execution time Memory
1015538 2024-07-06T13:43:03 Z 0pt1mus23 Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 7 ms 9972 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 = 2e5+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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 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 0 ms 2396 KB Output is correct
8 Correct 1 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 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 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2684 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 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 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2684 KB Output is correct
14 Runtime error 7 ms 9972 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -