oj.uz

답안 #1034328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034328 2024-07-25T12:25:18 Z MarwenElarbi Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 1 ms 1116 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=0;
        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]);
        }cout <<ans*2+1<<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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -