oj.uz

Submission #45958

# Submission time Handle Problem Language Result Execution time Memory
45958 2018-04-16T15:13:38 Z sorry_Benq Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 776 ms 100440 KB 
/**
* 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 74 ms 1240 KB Output is correct
11 Correct 264 ms 1356 KB Output is correct
12 Correct 90 ms 1500 KB Output is correct
13 Correct 58 ms 1500 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 74 ms 1240 KB Output is correct
11 Correct 264 ms 1356 KB Output is correct
12 Correct 90 ms 1500 KB Output is correct
13 Correct 58 ms 1500 KB Output is correct
14 Runtime error 776 ms 100440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -