This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/** Im the best because i work as hard as i possibly can **/
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl "\n"
const int N = 3e5 + 10;
const ll mod = 884577481;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 19;
const ll base = 609859;
string s;
char C[N];
int n, T, P[N], rnk[LOG][N], seg[N << 2];
ll pw[N], hshL[N], hshR[N];
bool cmp(int i, int j)
{
int t = T - 1;
if(rnk[t][i] == rnk[t][j])
{
if(max(i, j) + (1 << t) > n) return i > j;
return rnk[t][i + (1 << t)] < rnk[t][j + (1 << t)];
}
return rnk[t][i] < rnk[t][j];
}
inline ll baze(int l, int r)
{
return (hshL[r] - (hshL[l - 1] * pw[r - l + 1] % mod) + mod) % mod;
}
inline ll baze2(int l, int r)
{
return (hshR[l] - (hshR[r + 1] * pw[r - l + 1] % mod) + mod) % mod;
}
inline void SA()
{
pw[0] = 1;
for(int i = 1; i < N; i ++) pw[i] = pw[i - 1] * base % mod;
for(int i = 1; i <= n; i ++)
{
hshL[i] = (hshL[i - 1] * base + s[i] - 'a' + 1) % mod;
P[i] = i;
rnk[0][i] = s[i] - 'a' + 1;
}
for(int i = n; i >= 1; i --)
{
hshR[i] = (hshR[i + 1] * base + s[i] - 'a' + 1) % mod;
}
for(T = 1; T < LOG; T ++)
{
sort(P + 1, P + n + 1, cmp);
rnk[T][P[1]] = 1;
for(int i = 2; i <= n ;i ++)
{
rnk[T][P[i]] = rnk[T][P[i - 1]] + cmp(P[i - 1], P[i]);
}
}
}
int lcp(int i, int j)
{
int ret = 0;
for(T = LOG - 1; ~T; T --)
{
if(max(i, j) + (1 << T) - 1 > n || rnk[T][i] != rnk[T][j]) continue;
ret ^= 1 << T;
i += 1 << T;
j += 1 << T;
}
return ret;
}
void build(int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
seg[v] = lcp(P[tl - 1], P[tl]);
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
seg[v] = min(seg[v << 1], seg[v << 1 | 1]);
}
int find_nxt(int p, int x, int v = 1, int tl = 1, int tr = n)
{
if(p > n) return n + 1;
if(tr < p) return -1;
if(seg[v] >= x)
{
if(tr == n) return n + 1;
return -1;
}
if(tl == tr) return tl;
int mid = (tl + tr) >> 1;
int cu = find_nxt(p, x, v << 1, tl, mid);
if(cu == -1) cu = find_nxt(p, x, v << 1 | 1, mid + 1, tr);
return cu;
}
int find_prv(int p, int x, int v = 1, int tl = 1, int tr = n)
{
if(tl > p) return -1;
if(seg[v] >= x)
{
if(tl == 1) return 0;
return -1;
}
if(tl == tr) return tl;
int mid = (tl + tr) >> 1;
int cu = find_prv(p, x, v << 1 | 1, mid + 1, tr);
if(cu == -1) cu = find_prv(p, x, v << 1, tl, mid);
return cu;
}
ll calc(int l, int r)
{
int sz = r - l + 1, id = rnk[LOG - 1][l];
int L = find_prv(id, sz);
int R = find_nxt(id + 1, sz);
return R - L;
}
int main()
{
scanf("%s", C);
n = strlen(C);
s = C;
s = "#" + s;
SA();
build();
ll tot = 0;
for(int i = 1; i <= n; i ++)
{
int d = 0, up = min(i - 1, n - i) + 1;
while(up - d > 1)
{
int mid = (up + d) >> 1;
if(baze(i, i + mid) == baze2(i - mid, i)) d = mid;
else up = mid;
}
tot = max(tot, calc(i - d, i + d) * (2 * d + 1));
}
for(int i = 1; i < n; i ++)
{
if(s[i] != s[i + 1]) continue;
int d = 0, up = min(i - 1, n - i - 1) + 1;
while(up - d > 1)
{
int mid = (up + d) >> 1;
if(baze(i + 1, i + 1 + mid) == baze2(i - mid, i)) d = mid;
else up = mid;
}
tot = max(tot, calc(i - d, i + d + 1) * (2 * d + 2));
}
printf("%lld", tot);
return 0;
}
Compilation message (stderr)
palindrome.cpp:3: warning: ignoring #pragma comment [-Wunknown-pragmas]
3 | #pragma comment(linker, "/stack:200000000")
|
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/gthr.h:148,
from /usr/include/c++/9/ext/atomicity.h:35,
from /usr/include/c++/9/bits/ios_base.h:39,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from palindrome.cpp:6:
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("tune=") was already specified
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("tune=") was already specified
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("tune=") was already specified
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("tune=") was already specified
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("tune=") was already specified
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("tune=") was already specified
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("tune=") was already specified
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("tune=") was already specified
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("tune=") was already specified
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("tune=") was already specified
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("tune=") was already specified
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("tune=") was already specified
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("tune=") was already specified
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("tune=") was already specified
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("tune=") was already specified
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("tune=") was already specified
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("tune=") was already specified
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("tune=") was already specified
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("tune=") was already specified
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("tune=") was already specified
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("tune=") was already specified
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("tune=") was already specified
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("tune=") was already specified
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("tune=") was already specified
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("tune=") was already specified
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("tune=") was already specified
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("tune=") was already specified
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("tune=") was already specified
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("tune=") was already specified
palindrome.cpp: In function 'int main()':
palindrome.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
148 | scanf("%s", C);
| ~~~~~^~~~~~~~~