제출 #1121254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121254		TrinhKhanhDung	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	67 ms	28976 KiB

palindromic

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 1e6 + 10, base = 311;

int N;
string s;

void solve(){
    cin >> s;
    N = sz(s);
    s = "*" + s + "*";
}

namespace subtask1{
    int f[5003];
    ull Hash[10003], Pow[10003];

    void Hashing(){
        Pow[0] = 1;
        for(int i = 1; i <= N; i++){
            Pow[i] = Pow[i - 1] * base;
            Hash[i] = Hash[i - 1] * base + s[i];
        }
    }

    ull getHash(int l, int r){
        return Hash[r] - Hash[l - 1] * Pow[r - l + 1];
    }

    void solve(){
        int M = N / 2;

        Hashing();
        for(int i = 1; i <= M; i++){
            f[i] = -INF;
        }
        f[0] = 0;
        for(int i = 1; i <= M; i++){
            for(int j = 1; j <= i; j++) if(getHash(j, i) == getHash(N - i + 1, N - j + 1)){
                maximize(f[i], f[j - 1] + 1);
            }
        }

        ll ans = 0;
        for(int i = 0; i <= M; i++){
            maximize(ans, 1LL * f[i] * 2 + (i * 2 < N));
        }
        cout << ans << '\n';
    }       
}

namespace subtask4{
    ull Hash[(int)1e6 + 10], Pow[(int)1e6 + 10];

    void Hashing(){
        Pow[0] = 1;
        for(int i = 1; i <= N; i++){
            Pow[i] = Pow[i - 1] * base;
            Hash[i] = Hash[i - 1] * base + s[i];
        }
    }

    ull getHash(int l, int r){
        return Hash[r] - Hash[l - 1] * Pow[r - l + 1];
    }

    void solve(){
        int M = N / 2;

        Hashing();

        int cur = 0, p = 0;
        for(int i = 1; i <= M; i++){
            if(getHash(p + 1, i) == getHash(N - i + 1, N - p)){
                cur++;
                p = i;
            }
        }

        cur *= 2;
        if(p * 2 < N) cur++;
        cout << cur << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    cin >> t;

    while(t--){
        solve();
        subtask4::solve();
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40