oj.uz

Submission #45970

# Submission time Handle Problem Language Result Execution time Memory
45970 2018-04-16T16:54:51 Z sorry_Benq Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 6294 ms 105232 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;
}

string s; 
hsh h; 

int solve(int idx){
	if (s.size() % 2 == 1){
		if (idx == s.size() / 2) return 1;
		int res = 1;
		for (int j = idx + 1; j <= s.size() / 2; j++){
			if (h.get(idx, j - 1) == h.get(s.size() - j, s.size() - 1 - idx)){
				return max(res, solve(j) + 2);
			}
		}
		return res;
	}
	else{
		if (idx == s.size() / 2) return 0;
		int res = 1;
		for (int j = idx + 1; j <= s.size() / 2; j++){
			if (h.get(idx, j - 1) == h.get(s.size() - j, s.size() - 1 - idx)){
				return max(res, solve(j) + 2);
			}
		}
		return res;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T;
	for (int testcase = 0; testcase < T; testcase++){
		cin >> s;
		h.gen(s);
		cout << solve(0) << endl;
	}
}

Compilation message

palindromic.cpp: In function 'int solve(int)':
palindromic.cpp:148:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (idx == s.size() / 2) return 1;
       ~~~~^~~~~~~~~~~~~~~
palindromic.cpp:150:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = idx + 1; j <= s.size() / 2; j++){
                         ~~^~~~~~~~~~~~~~~
palindromic.cpp:158:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (idx == s.size() / 2) return 0;
       ~~~~^~~~~~~~~~~~~~~
palindromic.cpp:160:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = idx + 1; j <= s.size() / 2; j++){
                         ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 500 KB Output is correct
7 Correct 3 ms 500 KB Output is correct
8 Correct 3 ms 500 KB Output is correct
9 Correct 4 ms 652 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 500 KB Output is correct
7 Correct 3 ms 500 KB Output is correct
8 Correct 3 ms 500 KB Output is correct
9 Correct 4 ms 652 KB Output is correct
10 Correct 65 ms 1680 KB Output is correct
11 Correct 36 ms 1680 KB Output is correct
12 Correct 61 ms 1680 KB Output is correct
13 Correct 53 ms 1680 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 500 KB Output is correct
7 Correct 3 ms 500 KB Output is correct
8 Correct 3 ms 500 KB Output is correct
9 Correct 4 ms 652 KB Output is correct
10 Correct 65 ms 1680 KB Output is correct
11 Correct 36 ms 1680 KB Output is correct
12 Correct 61 ms 1680 KB Output is correct
13 Correct 53 ms 1680 KB Output is correct
14 Correct 6294 ms 105232 KB Output is correct
15 Correct 3482 ms 105232 KB Output is correct
16 Correct 5928 ms 105232 KB Output is correct
17 Correct 3308 ms 105232 KB Output is correct