oj.uz

Submission #544490

# Submission time Handle Problem Language Result Execution time Memory
544490 2022-04-02T06:29:02 Z ryansee Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 193 ms 73892 KB 
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll tc, n, ans;
string A;
ll qexp(ll x, ll e) {
	if(e==0) return 1;
	ll half = qexp(x,e/2);
	half *= half; 
	if(e%2)half*=x;
	return half;
}
ll dpdp(ll x, ll y) {
	if(y-x+1 == 0) return 0;
	string ret = ""; ll split = -1; ll n = y-x+1;
	ll front=0,back=0,len=0;
	// cerr << "at: " << x << ' ' << y << '\n';
	for(ll mid = x; mid <= x+n/2-1; ++mid) {
		// cerr << mid << ' ' << y-(mid-x) << '\n';
		front *= 53ll;
		front += (A[mid]-'a');
		back += qexp(53,len++)*(A[y-(mid-x)]-'a');
		// dq1.push_back(A[mid]);
		// dq2.push_front(A[y-(mid-x)]);
		if(front==back) 
		{ split = mid; break; 
		}
	}
	// cerr <<"split: " << split << '\n';
	if(split==-1) return 1;
	return dpdp(split+1,y-(split-x)-1) + 2;
}
ll solve() {
	return dpdp(0,n-1);
}
int main()
{
	FAST
	cin>>tc;
	while(tc --) {
		cin>>A; n=siz(A);
		cout<<solve()<<'\n';
	}
	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 972 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 596 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 972 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 193 ms 73892 KB Output is correct
15 Correct 119 ms 46348 KB Output is correct
16 Correct 145 ms 10692 KB Output is correct
17 Correct 55 ms 22492 KB Output is correct