oj.uz

Submission #1034350

# Submission time Handle Problem Language Result Execution time Memory
1034350 2024-07-25T12:32:22 Z MarwenElarbi Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 21468 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=1e6+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 3 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8280 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8280 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 4 ms 8080 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8280 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 4 ms 8080 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 614 ms 8540 KB Output is correct
11 Correct 279 ms 8540 KB Output is correct
12 Correct 495 ms 8536 KB Output is correct
13 Correct 375 ms 8540 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8280 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 4 ms 8080 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 614 ms 8540 KB Output is correct
11 Correct 279 ms 8540 KB Output is correct
12 Correct 495 ms 8536 KB Output is correct
13 Correct 375 ms 8540 KB Output is correct
14 Execution timed out 10013 ms 21468 KB Time limit exceeded
15 Halted 0 ms 0 KB -