Submission #45958

#	Time	Username	Problem	Language	Result	Execution time	Memory
45958		sorry_Benq	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	776 ms	100440 KiB

palindromic

/**
* Source: own
* Description: Pairs reduce frequency of collision
* Verification: Dec 17 Plat 1
*/

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
template<typename T>
ostream& operator<< (ostream& out, const pair<T, T>& v) {
    out << "{" << v.first << ", " << v.second << "}";
    return out;
}

template<typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
    out << "[";
    size_t last = v.size() - 1;
    for(size_t i = 0; i < v.size(); ++i) {
        out << v[i];
        if (i != last) 
            out << ", ";
    }
    out << "]";
    return out;
}

template<typename T>
ostream& operator<< (ostream& out, const set<T>& v) {
    out << "[";
    auto pen = v.end();
    pen--;
    for (auto it = v.begin(); it != v.end(); it++){
		out << *it;
		if (it != pen){
			out << ", ";
		}
	}
	out << "]";
    return out;
}

template<typename T>
ostream& operator<< (ostream& out, const Tree<T>& v) {
    out << "[";
    auto pen = v.end();
    pen--;
    for (auto it = v.begin(); it != v.end(); it++){
		out << *it;
		if (it != pen){
			out << ", ";
		}
	}
	out << "]";
    return out;
}

typedef pair<ll, ll> pll;

template<class T> pair<T,T> operator+(const pair<T,T>& l, const pair<T,T>& r) {
    return {(l.f+r.f)%MOD,(l.s+r.s)%MOD};
}
 
template<class T> pair<T,T> operator-(const pair<T,T>& l, const pair<T,T>& r) {
    return {(l.f-r.f+MOD)%MOD,(l.s-r.s+MOD)%MOD};
}
 
template<class T> pair<T,T> operator*(const pair<T,T>& l, const T& r) {
    return {l.f*r%MOD,l.s*r%MOD};
}

template<class T> pair<T,T> operator*(const pair<T,T>& l, const pair<T,T>& r) {
    return {l.f*r.f%MOD,l.s*r.s%MOD};
}
    
struct hsh {
    string S; 
    vector<pll> po, ipo, cum;
    pll base = mp(948392576,573928192);
    
    ll modpow(ll b, ll p) {
        return !p?1:modpow(b*b%MOD,p/2)*(p&1?b:1)%MOD;
    }
    
    ll inv(ll x) {
        return modpow(x,MOD-2);
    }
    
    void gen(string _S) {
        S = _S;
        po.resize(sz(S)), ipo.resize(sz(S)), cum.resize(sz(S)+1);
        po[0] = ipo[0] = {1,1};
        FOR(i,1,sz(S)) {
            po[i] = po[i-1]*base;
            ipo[i] = {inv(po[i].f),inv(po[i].s)};
        }
        F0R(i,sz(S)) cum[i+1] = cum[i]+po[i]*(ll)(S[i]-'a'+1);
    }
    
    pll get(int l, int r) {
        return ipo[l]*(cum[r+1]-cum[l]);
    }
};

int lcp(hsh& a, hsh& b) { // can be used to generate a suffix array
    int lo = 0, hi = min(sz(a.S),sz(b.S));
    while (lo < hi) {
        int mid = (lo+hi+1)/2;
        if (a.get(0,mid-1) == b.get(0,mid-1)) lo = mid;
        else hi = mid-1;
    }
    return lo;
}

int DP[100005];

int main() {
	int T; cin >> T;
	for (int testcase = 0; testcase < T; testcase++){
		string s; cin >> s;
		hsh h; 
		h.gen(s);
		if (s.size() % 2 == 0){
			int k = s.size();
			DP[k/2] = 0;
			for (int i = k/2 - 1; i >= 0; i--){
				DP[i] = 1;
				for (int j = i + 1; j <= k/2; j++){
					if (h.get(i, j - 1) == h.get(k - j, k - 1 - i)){
						DP[i] = max(DP[i], DP[j] + 2);
						break;
					}
				}
			}
			cout << DP[0] << endl;
		}
		else{
			int k = s.size();
			DP[k/2] = 1;
			for (int i = k/2 - 1; i >= 0; i--){
				DP[i] = 1;
				for (int j = i + 1; j <= k/2; j++){
					if (h.get(i, j - 1) == h.get(k - j, k - 1 - i)){
						DP[i] = max(DP[i], DP[j] + 2);
						break;
					}
				}
			}
			cout << DP[0] << endl;
		}
	}
}

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