oj.uz

답안 #45960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
45960 2018-04-16T15:48:37 Z sorry_Benq Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 61440 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[1000005];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 500 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 4 ms 700 KB Output is correct
7 Correct 3 ms 700 KB Output is correct
8 Correct 4 ms 700 KB Output is correct
9 Correct 4 ms 700 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 4 ms 700 KB Output is correct
7 Correct 3 ms 700 KB Output is correct
8 Correct 4 ms 700 KB Output is correct
9 Correct 4 ms 700 KB Output is correct
10 Correct 71 ms 1104 KB Output is correct
11 Correct 246 ms 1224 KB Output is correct
12 Correct 88 ms 1224 KB Output is correct
13 Correct 61 ms 1224 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 4 ms 700 KB Output is correct
7 Correct 3 ms 700 KB Output is correct
8 Correct 4 ms 700 KB Output is correct
9 Correct 4 ms 700 KB Output is correct
10 Correct 71 ms 1104 KB Output is correct
11 Correct 246 ms 1224 KB Output is correct
12 Correct 88 ms 1224 KB Output is correct
13 Correct 61 ms 1224 KB Output is correct
14 Correct 8931 ms 61440 KB Output is correct
15 Execution timed out 10090 ms 61440 KB Time limit exceeded
16 Halted 0 ms 0 KB -