oj.uz

Submission #1034346

# Submission time Handle Problem Language Result Execution time Memory
1034346 2024-07-25T12:31:48 Z MarwenElarbi Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 564 ms 24272 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e5+5;
const int MOD=1e9+9;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int segtree[nax*4];
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos]=(l==0 ? 0 : -1e9);
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
    return;
}
void update(int pos,int l,int r,int idx,int value){
    if(l==r){
        segtree[pos]=value;
        return;
    }
    int mid=(r+l)/2;
    if(idx<=mid) update(pos*2+1,l,mid,idx,value);
    else update(pos*2+2,mid+1,r,idx,value);
    segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
    return;
}
int query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return -1e9;
    if(l>=left&&r<=right) return segtree[pos];
    int mid=(r+l)/2;
    return max(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
vector<ll> pw={1};
vector<ll> p_hash(nax);
long long B=9973;
void compute_hash(string s){
    while(pw.size()<s.size()){
        pw.pb((pw.back()*B)%MOD);
    }
    p_hash[0]=0;
    for (int i = 0; i < s.size(); ++i)
    {
        p_hash[i+1]=((p_hash[i]*B)%MOD+s[i])%MOD;
    }   
    return;
}
int get_hash(int l,int r){
    long long ans=(p_hash[r+1]-(p_hash[l]*pw[r-l+1]));
    return (ans%MOD + MOD)%MOD;
}
int main()
{
    optimise;
    int test_cases;
    cin>>test_cases;
    while(test_cases--){
        string t;
        cin>>t;
        int n=t.size()+1;
        reverse(t.begin(),t.end());
        t.pb(' ');
        reverse(t.begin(),t.end());
        compute_hash(t);
        int dp[n];
        for (int i = 0; i < n; ++i)
        {
            dp[i]=-1e9;
        }
        dp[0]=0;
        int ans=1;
        for (int i = 1; i <= n/2; ++i)
        {
            for (int j = i; j > 0; --j)
            {
                if(get_hash(j,i)==get_hash(n-i,n-j)){
                    dp[i]=max(dp[i],dp[j-1]+1);
                }
            }
            ans=max(ans,(dp[i]*2-((i==n/2&&n%2==0 ? 1 : 0))+(i==n/2 ? 0 : 1)));
        }cout <<ans<<endl;

    }
}

Compilation message

palindromic.cpp: In function 'void compute_hash(std::string)':
palindromic.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < s.size(); ++i)
      |                     ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 564 ms 1568 KB Output is correct
11 Correct 251 ms 1568 KB Output is correct
12 Correct 483 ms 1548 KB Output is correct
13 Correct 352 ms 1368 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 564 ms 1568 KB Output is correct
11 Correct 251 ms 1568 KB Output is correct
12 Correct 483 ms 1548 KB Output is correct
13 Correct 352 ms 1368 KB Output is correct
14 Runtime error 25 ms 24272 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -