/**
* 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;
}
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
