oj.uz

Submission #45969

# Submission time Handle Problem Language Result Execution time Memory
45969 2018-04-16T16:52:31 Z sorry_Benq Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 6687 ms 105336 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() {
	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 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 480 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 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 4 ms 532 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 3 ms 596 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 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 4 ms 532 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 67 ms 1636 KB Output is correct
11 Correct 38 ms 1636 KB Output is correct
12 Correct 65 ms 1636 KB Output is correct
13 Correct 57 ms 1636 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 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 4 ms 532 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 67 ms 1636 KB Output is correct
11 Correct 38 ms 1636 KB Output is correct
12 Correct 65 ms 1636 KB Output is correct
13 Correct 57 ms 1636 KB Output is correct
14 Correct 6687 ms 105336 KB Output is correct
15 Correct 3559 ms 105336 KB Output is correct
16 Correct 6189 ms 105336 KB Output is correct
17 Correct 3478 ms 105336 KB Output is correct