oj.uz

Submission #535885

# Submission time Handle Problem Language Result Execution time Memory
535885 2022-03-11T17:12:09 Z xuliu Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 360 ms 43584 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int N = 1e6 + 4;
const ll mod1 = 1e9 + 7, mod2 = 999999323, base = 2131;
ll powbase[N][2];

ll mul(ll a, ll b, ll mod) { return (a*b)%mod; }
ll del(ll a, ll b, ll mod) {
	a -= b;
	a %= mod;
	if(a < 0) a += mod;
	return a;
}

struct H {
	vector<ll> h1, h2;
	int n;
	H(string s) {
		n = (int) s.size();
		h1.assign(n+1, 0); h2.assign(n+1, 0);
		for(int i=1; i<=n; i++) {
			h1[i] = (mul(h1[i-1], base, mod1) + (s[i-1]-'a'+1))%mod1;
			h2[i] = (mul(h2[i-1], base, mod2) + (s[i-1]-'a'+1))%mod2;
		}
	}
	pair<ll, ll> substr(int l, int r) {
		if(l > r) return {0, 0};
		if(r > n) return {0, 0};
		ll r1 = del(h1[r], mul(h1[l-1], powbase[r-l+1][0], mod1), mod1);
		ll r2 = del(h2[r], mul(h2[l-1], powbase[r-l+1][1], mod2), mod2);
		return {r1, r2};
	}
};

int sol(H &h, int l, int r) {
	debug cerr<<"l, r = "<<l<<", "<<r<<"\n";
	if(l > r) return 0;
	for(int lx=l; lx <= r; lx++) {
		int dl = lx - l;
		int rx = r - dl;
		if(lx >= rx) break;
		if(h.substr(l, lx) == h.substr(rx, r)) return sol(h, lx+1, rx-1)+2;
	}
	return 1;
}

void solve() {
	string s; cin>>s; int n = (int) s.size();
	H h(s);
	cout<<sol(h, 1, n)<<"\n";
}

void prepare() {
	powbase[0][0] = powbase[0][1] = 1;
	for(int i=1; i<N; i++) {
		powbase[i][0] = mul(powbase[i-1][0], base, mod1);
		powbase[i][1] = mul(powbase[i-1][1], base, mod2);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	prepare();
	int tc; cin>>tc;
	while(tc--) {
		solve();
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15956 KB Output is correct
2 Correct 14 ms 15912 KB Output is correct
3 Correct 14 ms 15956 KB Output is correct
4 Correct 15 ms 15980 KB Output is correct
5 Correct 14 ms 15876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15956 KB Output is correct
2 Correct 14 ms 15912 KB Output is correct
3 Correct 14 ms 15956 KB Output is correct
4 Correct 15 ms 15980 KB Output is correct
5 Correct 14 ms 15876 KB Output is correct
6 Correct 14 ms 15980 KB Output is correct
7 Correct 17 ms 15956 KB Output is correct
8 Correct 15 ms 15976 KB Output is correct
9 Correct 15 ms 15956 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15956 KB Output is correct
2 Correct 14 ms 15912 KB Output is correct
3 Correct 14 ms 15956 KB Output is correct
4 Correct 15 ms 15980 KB Output is correct
5 Correct 14 ms 15876 KB Output is correct
6 Correct 14 ms 15980 KB Output is correct
7 Correct 17 ms 15956 KB Output is correct
8 Correct 15 ms 15976 KB Output is correct
9 Correct 15 ms 15956 KB Output is correct
10 Correct 19 ms 16260 KB Output is correct
11 Correct 15 ms 16208 KB Output is correct
12 Correct 16 ms 16248 KB Output is correct
13 Correct 18 ms 16216 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15956 KB Output is correct
2 Correct 14 ms 15912 KB Output is correct
3 Correct 14 ms 15956 KB Output is correct
4 Correct 15 ms 15980 KB Output is correct
5 Correct 14 ms 15876 KB Output is correct
6 Correct 14 ms 15980 KB Output is correct
7 Correct 17 ms 15956 KB Output is correct
8 Correct 15 ms 15976 KB Output is correct
9 Correct 15 ms 15956 KB Output is correct
10 Correct 19 ms 16260 KB Output is correct
11 Correct 15 ms 16208 KB Output is correct
12 Correct 16 ms 16248 KB Output is correct
13 Correct 18 ms 16216 KB Output is correct
14 Correct 360 ms 43584 KB Output is correct
15 Correct 174 ms 38120 KB Output is correct
16 Correct 323 ms 41884 KB Output is correct
17 Correct 167 ms 30856 KB Output is correct