QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729836 | #9571. Border Jump 2 | ucup-team5243# | TL | 723ms | 14040kb | C++17 | 25.5kb | 2024-11-09 17:55:36 | 2024-11-09 17:55:37 |
Judging History
answer
#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <array>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;
#include <iterator>
#include <functional>
#include <utility>
#include <type_traits>
template<class Elem> struct vec;
template<class Iter>
struct seq_view{
using Ref = typename std::iterator_traits<Iter>::reference;
using Elem = typename std::iterator_traits<Iter>::value_type;
Iter a, b;
Iter begin() const { return a; }
Iter end() const { return b; }
int size() const { return (int)(b-a); }
seq_view(Iter first, Iter last) : a(first), b(last) {}
seq_view sort() const { std::sort(a, b); return *this; }
Ref& operator[](int x) const { return *(a+x); }
template<class F = std::less<Elem>, class ret = vec<int>> ret sorti(F f = F()) const {
ret x(size()); for(int i=0; i<size(); i++) x[i] = i;
x().sort([&](int l, int r){ return f(a[l],a[r]); });
return x;
}
template<class ret = vec<Elem>> ret col() const { return ret(begin(), end()); }
template<class ret = vec<Elem>> ret cumsum() const {
auto res = ret(size() + 1, Elem(0));
for(int i=0; i<size(); i++) res[i+1] = res[i] + operator[](i);
return res;
}
template<class F = std::equal_to<Elem>, class ret = vec<std::pair<Elem, int>>>
ret rle(F eq = F()) const {
auto x = ret();
for(auto& a : (*this)){
if(x.size() == 0 || !eq(x[x.size()-1].first, a)) x.emp(a, 1); else x[x.size()-1].second++;
} return x;
}
template<class F> seq_view sort(F f) const { std::sort(a, b, f); return *this; }
Iter uni() const { return std::unique(a, b); }
Iter lb(const Elem& x) const { return std::lower_bound(a, b, x); }
Iter ub(const Elem& x) const { return std::upper_bound(a, b, x); }
int lbi(const Elem& x) const { return lb(x) - a; }
int ubi(const Elem& x) const { return ub(x) - a; }
seq_view bound(const Elem& l, const Elem& r) const { return { lb(l), lb(r) }; }
template<class F> Iter lb(const Elem& x, F f) const { return std::lower_bound(a, b, x, f); }
template<class F> Iter ub(const Elem& x, F f) const { return std::upper_bound(a, b, x, f); }
template<class F> Iter when_true_to_false(F f) const {
if(a == b) return a;
return std::lower_bound(a, b, *a,
[&](const Elem& x, const Elem&){ return f(x); });
}
seq_view same(Elem x) const { return { lb(x), ub(x) }; }
template<class F> auto map(F f) const {
vec<decltype(f(std::declval<const typename Iter::value_type&>()))> r;
for(auto& x : *this) r.emp(f(x));
return r;
}
Iter max() const { return std::max_element(a, b); }
Iter min() const { return std::min_element(a, b); }
template<class F = std::less<Elem>>
Iter min(F f) const { return std::min_element(a, b, f); }
seq_view rev() const { std::reverse(a, b); return *this; }
};
template<class Elem>
struct vec {
public:
using Base = typename std::vector<Elem>;
using Iter = typename Base::iterator;
using CIter = typename Base::const_iterator;
using View = seq_view<Iter>;
using CView = seq_view<CIter>;
vec(){}
explicit vec(int n, const Elem& value = Elem()) : a(0<n?n:0, value) {}
template <class I2> vec(I2 first, I2 last) : a(first, last) {}
vec(std::initializer_list<Elem> il) : a(std::move(il)) {}
vec(Base b) : a(std::move(b)) {}
operator Base() const { return a; }
Iter begin(){ return a.begin(); }
CIter begin() const { return a.begin(); }
Iter end(){ return a.end(); }
CIter end() const { return a.end(); }
int size() const { return a.size(); }
bool empty() const { return a.empty(); }
Elem& back(){ return a.back(); }
const Elem& back() const { return a.back(); }
vec& sortuni(){ (*this)().sort(); a.erase((*this)().uni(), end()); return *this; }
vec sortunied(){ vec x = *this; x.sortuni(); return x; }
Iter operator()(int x){ return a.begin() + x; }
CIter operator()(int x) const { return a.begin() + x; }
View operator()(int l, int r){ return { (*this)(l), (*this)(r) }; }
CView operator()(int l, int r) const { return { (*this)(l), (*this)(r) }; }
View operator()(){ return (*this)(0,size()); }
CView operator()() const { return (*this)(0,size()); }
Elem& operator[](int x){ return a[x]; }
const Elem& operator[](int x) const { return a[x]; }
Base& operator*(){ return a; }
const Base& operator*() const { return a; }
vec& push(Elem args){
a.push_back(std::move(args));
return *this;
}
template<class... Args>
vec& emp(Args &&... args){
a.emplace_back(std::forward<Args>(args) ...);
return *this;
}
template<class Range>
vec& app(Range& x){ for(auto& v : x){ emp(v); } return *this; }
Elem pop(){ Elem x = std::move(a.back()); a.pop_back(); return x; }
void resize(int sz){ a.resize(sz); }
void reserve(int sz){ a.reserve(sz); }
bool operator==(const vec& r) const { return a == r.a; }
bool operator!=(const vec& r) const { return a != r.a; }
bool operator<(const vec& r) const { return a < r.a; }
bool operator<=(const vec& r) const { return a <= r.a; }
bool operator>(const vec& r) const { return a > r.a; }
bool operator>=(const vec& r) const { return a >= r.a; }
vec<vec<Elem>> pile(int n) const { return vec<vec<Elem>>(n, *this); }
template<class F> vec& filter(F f){
int p = 0;
for(auto& x : a) if(f(x)) std::swap(a[p++],x);
resize(p); return *this;
}
vec& operator+=(const vec& r){ return app(r); }
vec operator+(const vec& r) const { vec x = *this; x += r; return x; }
vec operator*(int t) const { vec res; while(t--){ res += *this; } return res; }
private: Base a;
};
template<class IStr, class U, class T>
IStr& operator>>(IStr& is, vec<std::pair<U,T>>& v){ for(auto& x:v){ is >> x.first >> x.second; } return is; }
template<class IStr, class T>
IStr& operator>>(IStr& is, vec<T>& v){ for(auto& x:v){ is >> x; } return is; }
template<class OStr, class T>
OStr& operator<<(OStr& os, const vec<T>& v){
for(int i=0; i<v.size(); i++){
if(i){ os << ' '; } os << v[i];
} return os;
}
template<class OStr, class U, class T>
OStr& operator<<(OStr& os, const vec<std::pair<U,T>>& v){
for(int i=0; i<v.size(); i++){
if(i){ os << ' '; } os << '(' << v[i].first << ',' << v[i].second << ')';
} return os;
}
#include <cassert>
#include <numeric>
// FROM ATCODER LIBRARY
namespace nachia {
namespace internal {
std::vector<int> sa_naive(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int l, int r) {
if (l == r) return false;
while (l < n && r < n) {
if (s[l] != s[r]) return s[l] < s[r];
l++;
r++;
}
return l == n;
});
return sa;
}
std::vector<int> sa_doubling(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n), rnk = s, tmp(n);
std::iota(sa.begin(), sa.end(), 0);
for (int k = 1; k < n; k *= 2) {
auto cmp = [&](int x, int y) {
if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
int rx = x + k < n ? rnk[x + k] : -1;
int ry = y + k < n ? rnk[y + k] : -1;
return rx < ry;
};
std::sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
std::swap(tmp, rnk);
}
return sa;
}
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
int n = int(s.size());
if (n == 0) return {};
if (n == 1) return {0};
if (n == 2) {
if (s[0] < s[1]) {
return {0, 1};
} else {
return {1, 0};
}
}
if (n < 10) {
return sa_naive(s);
}
if (n < 40) {
return sa_doubling(s);
}
std::vector<int> sa(n);
std::vector<bool> ls(n);
for (int i = n - 2; i >= 0; i--) {
ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
}
std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
for (int i = 0; i < n; i++) {
if (!ls[i]) {
sum_s[s[i]]++;
} else {
sum_l[s[i] + 1]++;
}
}
for (int i = 0; i <= upper; i++) {
sum_s[i] += sum_l[i];
if (i < upper) sum_l[i + 1] += sum_s[i];
}
auto induce = [&](const std::vector<int>& lms) {
std::fill(sa.begin(), sa.end(), -1);
std::vector<int> buf(upper + 1);
std::copy(sum_s.begin(), sum_s.end(), buf.begin());
for (auto d : lms) {
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
sa[buf[s[n - 1]]++] = n - 1;
for (int i = 0; i < n; i++) {
int v = sa[i];
if (v >= 1 && !ls[v - 1]) {
sa[buf[s[v - 1]]++] = v - 1;
}
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
for (int i = n - 1; i >= 0; i--) {
int v = sa[i];
if (v >= 1 && ls[v - 1]) {
sa[--buf[s[v - 1] + 1]] = v - 1;
}
}
};
std::vector<int> lms_map(n + 1, -1);
int m = 0;
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms_map[i] = m++;
}
}
std::vector<int> lms;
lms.reserve(m);
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms.push_back(i);
}
}
induce(lms);
if (m) {
std::vector<int> sorted_lms;
sorted_lms.reserve(m);
for (int v : sa) {
if (lms_map[v] != -1) sorted_lms.push_back(v);
}
std::vector<int> rec_s(m);
int rec_upper = 0;
rec_s[lms_map[sorted_lms[0]]] = 0;
for (int i = 1; i < m; i++) {
int l = sorted_lms[i - 1], r = sorted_lms[i];
int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
bool same = true;
if (end_l - l != end_r - r) {
same = false;
} else {
while (l < end_l) {
if (s[l] != s[r]) {
break;
}
l++;
r++;
}
if (l == n || s[l] != s[r]) same = false;
}
if (!same) rec_upper++;
rec_s[lms_map[sorted_lms[i]]] = rec_upper;
}
auto rec_sa =
sa_is(rec_s, rec_upper);
for (int i = 0; i < m; i++) {
sorted_lms[i] = lms[rec_sa[i]];
}
induce(sorted_lms);
}
return sa;
}
} // namespace internal
std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
assert(0 <= upper);
for (int d : s) {
assert(0 <= d && d <= upper);
}
auto sa = internal::sa_is(s, upper);
return sa;
}
template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
int n = int(s.size());
std::vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
std::vector<int> s2(n);
int now = 0;
for (int i = 0; i < n; i++) {
if (i && s[idx[i - 1]] != s[idx[i]]) now++;
s2[idx[i]] = now;
}
return internal::sa_is(s2, now);
}
std::vector<int> suffix_array(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return internal::sa_is(s2, 255);
}
template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
const std::vector<int>& sa) {
int n = int(s.size());
assert(n >= 1);
std::vector<int> rnk(n);
for (int i = 0; i < n; i++) {
rnk[sa[i]] = i;
}
std::vector<int> lcp(n - 1);
int h = 0;
for (int i = 0; i < n; i++) {
if (h > 0) h--;
if (rnk[i] == 0) continue;
int j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rnk[i] - 1] = h;
}
return lcp;
}
std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return lcp_array(s2, sa);
}
} // namespace nachia
namespace nachia{
template<
class S,
S op(S l, S r)
>
struct Segtree {
private:
int N;
std::vector<S> A;
int xN;
void mergev(int i){
if(i < N) A[i] = op(A[i*2], A[i*2+1]);
}
template<class E>
int minLeft2(int r, E cmp, int a = 0, int b = 0, int i = -1) const {
static S x;
if(i == -1){ a=0; b=N; i=1; x=A[0]; }
if(r <= a) return a;
if(b <= r){
S nx = op(A[i], x);
if(cmp(nx)){ x = nx; return a; }
}
if(b - a == 1) return b;
int q = minLeft2(r, cmp, (a+b)/2, b, i*2+1);
if(q > (a+b)/2) return q;
return minLeft2(r, cmp, a, (a+b)/2, i*2);
}
template<class E>
int maxRight2(int l, E cmp, int a = 0, int b = 0, int i = -1) const {
static S x;
if(i == -1){ a=0; b=N; i=1; x=A[0]; }
if(b <= l) return b;
if(l <= a){
S nx = op(x, A[i]);
if(cmp(nx)){ x = nx; return b; }
}
if(b - a == 1) return a;
int q = maxRight2(l, cmp, a, (a+b)/2, i*2);
if(q < (a+b)/2) return q;
return maxRight2(l, cmp, (a+b)/2, b, i*2+1);
}
public:
Segtree() : N(0) {}
Segtree(int n, S e) : xN(n) {
N = 1; while (N < n) N *= 2;
A.assign(N * 2, e);
}
Segtree(const std::vector<S>& a, S e) : Segtree(a.size(), e){
for(int i=0; i<(int)a.size(); i++) A[i + N] = a[i];
for(int i=N-1; i>=1; i--) mergev(i);
}
S getE() const { return A[0]; }
void set(int p, S x){
p += N; A[p] = x;
for(int d=1; (1<<d)<=N; d++) mergev(p>>d);
}
S get(int p) const { return A[N+p]; }
S prod(int l, int r) const {
l += N; r += N;
S ql = A[0], qr = A[0];
while(l<r){
if(l&1) ql = op(ql, A[l++]);
if(r&1) qr = op(A[--r], qr);
l /= 2;
r /= 2;
}
return op(ql, qr);
}
S allProd() const { return A[1]; }
// bool cmp(S)
template<class E>
int minLeft(int r, E cmp) const {
return minLeft2(r, cmp);
}
// bool cmp(S)
template<class E>
int maxRight(int l, E cmp) const {
int x = maxRight2(l, cmp);
return x > xN ? xN : x;
}
};
} // namespace nachia
namespace nachia {
template<class T, class Cmp = std::less<T>>
struct PointSetRangeMin{
private:
static T minop(T l, T r){ return std::min(l, r, Cmp()); }
using Base = Segtree<T, minop>;
Base base;
Cmp cmpx;
public:
PointSetRangeMin() {}
PointSetRangeMin(int len, T INF)
: base(len, INF){}
PointSetRangeMin(const std::vector<T>& init, T INF)
: base(init, INF){}
T min(int l, int r){ return base.prod(l, r); }
T min(){ return base.allProd(); }
void set(int pos, T val){ base.set(pos, val); }
T getinf() const { return base.getE(); }
void setinf(int pos){ set(pos, getinf()); }
T get(int pos){ return base.get(pos); }
void chmin(int pos, T val){ base.set(pos, minop(get(pos), val)); }
int lBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return cmpx(val, x); }); }
int uBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return !cmpx(x, val); }); }
int lBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return cmpx(val, x); }); }
int uBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return !cmpx(x, val); }); }
template<class E>
int minLeft(int r, E cmp){ return base.minLeft(r, cmp); }
template<class E>
int maxRight(int l, E cmp){ return base.maxRight(l, cmp); }
int argmin(int l, int r){
auto v = this->min(l, r);
if(!cmpx(v, getinf())) return -1;
return lBoundRight(l, v);
}
};
} // namespace nachia
namespace nachia{
template<class Elem>
std::vector<int> EnumeratePalindromes(const std::vector<Elem>& A, bool extend = false) {
int n = int(A.size());
if (n == 0) return { 0 };
std::vector<int> res(n);
int r = 0;
for(int i=0; i<n; ){
while (0<=i-r && i+r<n && A[i-r] == A[i+r]) r++;
res[i] = r;
int di = 1;
while ((0<=i-di && i+di<n) && res[i-di] < r-di) {
res[i+di] = res[i-di];
di++;
}
r -= di;
i += di;
}
return res;
}
} // namespace nachia
namespace nachia{
int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
return __builtin_popcountll(c);
#else
c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
c = (c * (~0ull/257)) >> 56;
return c;
#endif
}
// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return 63 - __builtin_clzll(x);
#else
using u64 = unsigned long long;
int q = (x >> 32) ? 32 : 0;
auto m = x >> q;
constexpr u64 hi = 0x8888'8888;
constexpr u64 mi = 0x1111'1111;
m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
q += (m & 0xf) << 2;
q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf;
return q;
#endif
}
// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return __builtin_ctzll(x);
#else
return MsbIndex(x & -x);
#endif
}
}
namespace nachia{
struct WaveletMatrix{
using u64 = unsigned long long;
struct WordBlock{ u64 table; int ptr; };
int n;
int S;
int logS;
std::vector<std::vector<WordBlock>> Table;
WaveletMatrix() {}
WaveletMatrix(int maxVal, std::vector<int> A){
S = 1; logS = 0;
n = A.size();
while(S <= maxVal){ S *= 2; logS += 1; }
Table.resize(logS);
for(int d=logS-1; d>=0; d--){
std::vector<WordBlock> tableBuf(n/64+2,{0,0});
for(int i=0; i<n; i++) tableBuf[i/64].table |= (u64)((A[i]>>d) & 1) << (i%64);
for(int i=1; i<=n/64+1; i++) tableBuf[i].ptr = tableBuf[i-1].ptr + Popcount(tableBuf[i-1].table);
std::vector<int> buf;
for(int b : {0,1<<d}) for(int a : A) if((a&(1<<d))==b) buf.push_back(a);
std::swap(Table[d],tableBuf);
std::swap(A,buf);
}
}
int getLevelRank(int level, int p) const {
int res = Table[level][p/64].ptr + Popcount(Table[level][p/64].table & ~(~(u64)0 << (p%64)));
return res;
}
int getLeftPointer(int level, int p) const {
return p - getLevelRank(level,p);
}
int getRightPointer(int level, int p) const {
return n - Table[level].back().ptr + getLevelRank(level,p);
}
int get(int p) const {
int res = 0;
for(int d=logS-1; d>=0; d--){
res *= 2;
if(Table[d][p/64].table & ((u64)1 << (p%64))){
res |= 1;
p = getRightPointer(d,p);
}
else{
p = getLeftPointer(d,p);
}
}
return res;
}
int count(int l, int r, int val) const {
for(int d=logS-1; d>=0; d--){
if(val & (1<<d)){
l = getRightPointer(d,l);
r = getRightPointer(d,r);
}
else{
l = getLeftPointer(d,l);
r = getLeftPointer(d,r);
}
}
return r - l;
}
int countRange(int l, int r, int rval) const {
if(rval == 0) return 0;
int ans = 0;
for(int d=logS-1; d>=0; d--){
if(rval & (1<<d)){
ans += getLeftPointer(d,r) - getLeftPointer(d,l);
l = getRightPointer(d,l);
r = getRightPointer(d,r);
} else{
l = getLeftPointer(d,l);
r = getLeftPointer(d,r);
}
}
return ans;
}
int count(int l, int r, int lval, int rval) const {
return countRange(l, r, rval) - countRange(l, r, lval);
}
int getKthSmallest(int l, int r, int k) const {
int res = 0;
for(int d=logS-1; d>=0; d--){
res *= 2;
int zerocnt = r - l;
zerocnt -= getLevelRank(d,r);
zerocnt += getLevelRank(d,l);
if(k < zerocnt){
l = getLeftPointer(d,l);
r = getLeftPointer(d,r);
}
else{
res += 1;
k -= zerocnt;
l = getRightPointer(d,l);
r = getRightPointer(d,r);
}
}
return res;
}
int getMaxNoGreaterThanRec(int l, int r, int k, int d) const {
if(l >= r) return -1;
if(d < 0) return 0;
if(!(k & (1 << d))){
return getMaxNoGreaterThanRec(getLeftPointer(d,l), getLeftPointer(d,r), k, d-1);
} else {
int q = getMaxNoGreaterThanRec(getRightPointer(d,l), getRightPointer(d,r), k-(1<<d), d-1);
if(q != -1) return q + (1 << d);
return getMaxNoGreaterThanRec(getLeftPointer(d,l), getLeftPointer(d,r), (1<<d)-1, d-1);
}
}
int getMaxNoGreaterThan(int l, int r, int k) const {
return getMaxNoGreaterThanRec(l, r, k, logS-1);
}
};
}
void testcase(){
string S; cin >> S;
int N = S.size();
vector<int> Si(N*2-1, -1);
rep(i,N) Si[i*2] = S[i] - 'a';
auto pals = nachia::EnumeratePalindromes(Si);
rep(i,N) if(pals[i*2] % 2 == 0) pals[i*2] -= 1;
rep(i,N-1) if(pals[i*2+1] % 2 == 1) pals[i*2+1] -= 1;
string SrS = S + "$#" + string(S.rbegin(), S.rend());
//cout << SrS << endl;
auto sa = nachia::suffix_array(SrS);
auto lcp = nachia::lcp_array(SrS, sa);
auto rmq = nachia::PointSetRangeMin<int>(lcp, 1001001001);
auto wm = nachia::WaveletMatrix(N*2+1, sa);
//for(int sai : sa) cout << SrS.substr(sai) << endl;
vector<int> isa(sa.size());
rep(i,sa.size()) isa[sa[i]] = i;
vector<int> D(N);
rep(i,N-1) D[i+1] = (S[i] == S[i+1] ? 0 : 1);
rep(i,N-1) D[i+1] += D[i];
int ansLowerBound = 0;
auto equalRange = [&](int l, int r) -> int {
if(D[r-1] == D[l]) return 0;
int ng = 0;
int ok = (r-l)/2;
while(ng + 1 < ok){
int w = (ng + ok) / 2;
(D[r-w-1] == D[l+w] ? ok : ng) = w;
}
return ok;
};
//for(auto a : pals) cout << a << " ";
//cout << endl;
rep(m,pals.size()){
int l = (m + 1 - pals[m]) / 2;
int r = (m + 1 + pals[m]) / 2;
int k = equalRange(l, r);
chmax(ansLowerBound, (r-l-1) - k);
//cout << "m = " << m << " , l = " << l << " , r = " << r << " , k = " << k << endl;
}
auto simulate = [&](int l, int r) -> int {
int ans = 0;
//cout << "check l = " << l << " , r = " << r << endl;
while(true){
if(N-r <= (r-l)) break;
int f = isa[l];
int fl = rmq.uBoundLeft(f, r-l);
int fr = rmq.uBoundRight(f, r-l) + 1;
//cout << "fl = " << fl << " , fr = " << fr << endl;
int x = wm.getMaxNoGreaterThan(fl, fr, 2*N+2-r-(r-l)-1);
//cout << "2*N+2-r-1-(r-l) = " << 2*N+2-r-1-(r-l) << endl;
if(x < N+2) break;
ans += 1;
r = 2*N+2 - x;
//cout << "l = " << l << " , r = " << r << " , x = " << x << endl;
}
return ans;
};
rep(m,pals.size()){
//cout << " m = " << m << endl;
int l = (m + 1 - pals[m]) / 2;
int r = (m + 1 + pals[m]) / 2;
while(true){
if(l >= r) break;
int k = equalRange(l, r);
int minAns = (r-l-1) - k;
if(minAns + 20 <= ansLowerBound) break;
int thisans = minAns + simulate(l, r);
chmax(ansLowerBound, thisans);
l += 1; r -= 1;
}
}
cout << ansLowerBound << endl;
//cout << endl;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T;
rep(t,T) testcase();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
input:
3 aaaa abbaabba xy
output:
3 4 0
result:
ok 3 number(s): "3 4 0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
15 eeee ooom bbcb yyaa ssdn wgww hrhr exer hcch qyyy lppa ocvo orxr lrjj pztv
output:
3 2 1 1 1 1 1 1 2 2 1 1 1 1 0
result:
ok 15 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
52 eeeee oooom bbbcb yyyaa sssdn wwgww hhrhr eexer hhcch qqyyy llppa oocvo oorxr llrjj ppztv tnttt vnvvn hthhp jzjzj nrnrr gqgqt uruyu cdchd djdhh ktkfy piipp zaaza uffuq bvvvb hkkkk pcccj qccpq wqqaq appgg cxxvg ewfee peupe odfof kdpkh zotoz yzkzz irtrt vxyxi dlood akrrk nsbbb rdjjc bfexb uxsex ise...
output:
4 3 2 2 2 2 1 1 2 2 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 2 2 2 3 3 2 1 1 1 1 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 0
result:
ok 52 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
203 eeeeee ooooom bbbbcb yyyyaa ssssdn wwwgww hhhrhr eeexer hhhcch qqqyyy lllppa ooocvo ooorxr lllrjj pppztv ttnttt vvnvvn hhthhp jjzjzj nnrnrr ggqgqt uuruyu ccdchd ddjdhh kktkfy ppiipp zzaaza uuffuq bbvvvb hhkkkk ppcccj qqccpq wwqqaq aappgg ccxxvg eewfee ppeupe oodfof kkdpkh zzotoz yyzkzz iirtrt vv...
output:
5 4 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 3 2 2 3 3 2 1 1 1 1 2 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 1 3 3 2 3 2 2 1 1 1 1 2 2 2 2 2 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 4 4 3 2 2 2 2 1 1 1 1 1 2 1 1 1 2 2 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 2 2 2 1 2 2 ...
result:
ok 203 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
877 eeeeeee oooooom bbbbbcb yyyyyaa sssssdn wwwwgww hhhhrhr eeeexer hhhhcch qqqqyyy llllppa oooocvo oooorxr llllrjj ppppztv tttnttt vvvnvvn hhhthhp jjjzjzj nnnrnrr gggqgqt uuuruyu cccdchd dddjdhh kkktkfy pppiipp zzzaaza uuuffuq bbbvvvb hhhkkkk pppcccj qqqccpq wwwqqaq aaappgg cccxxvg eeewfee pppeupe ...
output:
6 5 4 4 4 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 3 2 2 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 3 2 2 2 2 2 2 3 2 2 2 2 1 1 1 1 1 2 2 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 3 3 3 2 2 2 2 2 2 2 4 3 3 4 4 3 2 2 2 2 2 1 1 1 1 2 1 1 1 2 2 1 1 1 1 1 1 2 2 2 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 2 2 2 1 2 2 ...
result:
ok 877 numbers
Test #6:
score: 0
Accepted
time: 20ms
memory: 3580kb
input:
4140 eeeeeeee ooooooom bbbbbbcb yyyyyyaa ssssssdn wwwwwgww hhhhhrhr eeeeexer hhhhhcch qqqqqyyy lllllppa ooooocvo ooooorxr lllllrjj pppppztv ttttnttt vvvvnvvn hhhhthhp jjjjzjzj nnnnrnrr ggggqgqt uuuuruyu ccccdchd ddddjdhh kkkktkfy ppppiipp zzzzaaza uuuuffuq bbbbvvvb hhhhkkkk ppppcccj qqqqccpq wwwwqqa...
output:
7 6 5 5 5 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 3 3 2 2 2 2 2 2 2 4 3 3 4 4 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 ...
result:
ok 4140 numbers
Test #7:
score: 0
Accepted
time: 110ms
memory: 3640kb
input:
21147 eeeeeeeee oooooooom bbbbbbbcb yyyyyyyaa sssssssdn wwwwwwgww hhhhhhrhr eeeeeexer hhhhhhcch qqqqqqyyy llllllppa oooooocvo oooooorxr llllllrjj ppppppztv tttttnttt vvvvvnvvn hhhhhthhp jjjjjzjzj nnnnnrnrr gggggqgqt uuuuuruyu cccccdchd dddddjdhh kkkkktkfy pppppiipp zzzzzaaza uuuuuffuq bbbbbvvvb hhhh...
output:
8 7 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 3 3 3 3 3 3 3 3 3 4 3 3 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
ok 21147 numbers
Test #8:
score: 0
Accepted
time: 32ms
memory: 13356kb
input:
2 eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...
output:
99999 99999
result:
ok 2 number(s): "99999 99999"
Test #9:
score: 0
Accepted
time: 631ms
memory: 13736kb
input:
2 eeegeeeggegegeeeegegeeeeegeeegeeeggeeeggegggegeggeeeeegegeeggeeeggggeggggegegeegggegggggeggggeegggegeeegggeegeeegeeeegeggegeggeggeggegggeeeeggeggggggeggegggeegegegggeggegggeegeeggegeegegggeegegegggegggeeeggeggeeegeeggeeggeggegggeggeegegegeeggggegggggegegggeeeegegeeggeggegggegegeggeegggeeeggeeggegg...
output:
21 19
result:
ok 2 number(s): "21 19"
Test #10:
score: 0
Accepted
time: 623ms
memory: 13488kb
input:
2 egooeoegeeggegeeoegggoeoegeeeoeegoeeeogeoggoggoegoegogooooggoeeeoogooegeooegeeggeeoegeogoggegoegoggogeoogegggogegogeoogoeeeogegeoeoggoogoeeooeeogeoegggggegoeoeeggogogggeggoegeogoeogggegggeoggggooggoeoeeoegoeeggoogggggegooggoeooeoeeooeooggogeogeeoogegegoggeogeooeoggeogegoeogeeogeegogegoogggogegogeg...
output:
12 12
result:
ok 2 number(s): "12 12"
Test #11:
score: 0
Accepted
time: 532ms
memory: 13296kb
input:
2 oeoaooeggegegoeeeaeaoeoeogoeoaoeoaaeooaaogagogeaaoeoooaogooaaooogaaaoaagaeaegoeaaaoggaaaogggaeoaaaegeeeggaeoaoooaoeoeaeggoaogaeggoggeggaeoeogaeaggagaoggoaageeaoaeggaoggoagaeoaeeagoaoogogageoaeaoaggogggoeoagogaoooaeeagoeaaeaaoggaegaoegoaoaeoagageagaagoaegaaoeoeaoaeogaeagoggaoaoaeaaeogggeeegaooagega...
output:
11 9
result:
ok 2 number(s): "11 9"
Test #12:
score: 0
Accepted
time: 380ms
memory: 13684kb
input:
2 ntiaoioraegexnnnnxtxeetoogetixnoegbeitbgnrxbiatabitooeatbiibbinnxrrataxaanxnaetxrroraggriraggoobbxegootgrgterottateonbtgxnxnrgoaanrgnbagetioagnbgrarbexatbggenrtbearrnbgtxaatirtnagoaoibigxxiibtxorxanarrtitrbobxnttroixrenxgobrnbarnaanoxignrengrxroababxtbnbxxeinerobtibbibrngrrerebtabetxgbnioggteaxtra...
output:
5 5
result:
ok 2 number(s): "5 5"
Test #13:
score: 0
Accepted
time: 348ms
memory: 12500kb
input:
2 ojzxseudqfxhvuomjrexifhnelffzyfiprrzforwfkwqedndbhmhnogfcfirkfumbqlbjxlldhlnbizrrlnvcqagfbbdcthlgyjlhujxyytzdzzidtsnfqikankokdickzgvjgyajjmhwxfyaaydlmylhcaasplhgslxgelkidgljigipgbfrfhkigkxefcsgulblhdvbjpovwocxifzwpnwqtpkbslqndgxnwvfjverfyneyqaleydxbkovfgvgminukorptglmlrjqlaubjyedlmtkqvtopvwmfaahrk...
output:
3 3
result:
ok 2 number(s): "3 3"
Test #14:
score: 0
Accepted
time: 4ms
memory: 3588kb
input:
100 eeegeeeggegegeeeegegeeeeegeeeg eeeggeeeggegggegeggeeeeegegeeg geeeggggeggggegegeegggegggggeg gggeegggegeeegggeegeeegeeeegeg gegeggeggeggegggeeeeggegggggge ggegggeegegegggeggegggeegeegge geegegggeegegegggegggeeeggegge eegeeggeeggeggegggeggeegegegee ggggegggggegegggeeeegegeeggegg egggegegeggeeggge...
output:
7 5 6 5 6 6 4 6 6 4 6 10 7 5 10 6 10 8 5 10 7 10 7 6 11 10 8 7 5 5 7 8 5 6 6 10 5 7 8 8 8 6 7 6 9 6 6 6 4 5 5 4 6 8 8 6 6 6 4 9 11 7 5 12 8 8 9 7 5 6 10 6 6 7 7 9 5 7 11 6 8 8 5 5 10 6 9 6 9 8 5 5 6 6 6 8 6 7 9 6
result:
ok 100 numbers
Test #15:
score: 0
Accepted
time: 11ms
memory: 3880kb
input:
500 egooeoegeeggegeeoegggoeoegeeeo eegoeeeogeoggoggoegoegogoooogg oeeeoogooegeooegeeggeeoegeogog gegoegoggogeoogegggogegogeoogo eeeogegeoeoggoogoeeooeeogeoegg gggegoeoeeggogogggeggoegeogoeo gggegggeoggggooggoeoeeoegoeegg oogggggegooggoeooeoeeooeooggog eogeeoogegegoggeogeooeoggeogeg oeogeeogeegogegoo...
output:
2 7 4 5 5 3 4 4 3 3 5 5 4 5 4 4 4 4 5 3 5 7 3 3 3 3 8 3 4 6 4 5 4 3 3 6 3 3 4 2 3 5 3 5 4 4 3 4 3 4 4 4 5 4 4 5 4 3 4 4 3 4 5 5 4 4 4 5 4 4 3 3 3 4 3 5 4 6 6 6 3 6 4 5 3 4 3 4 4 3 4 4 3 3 4 4 4 3 4 4 4 5 6 3 3 4 3 5 4 5 4 3 3 5 7 5 7 4 3 2 3 7 4 4 6 5 5 4 5 4 6 2 2 5 6 6 7 3 2 4 4 4 5 5 6 4 3 3 3 4 ...
result:
ok 500 numbers
Test #16:
score: 0
Accepted
time: 36ms
memory: 12212kb
input:
2 babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababba...
output:
37511 37511
result:
ok 2 number(s): "37511 37511"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
1 abacbaxyabcaba
output:
2
result:
ok 1 number(s): "2"
Test #18:
score: 0
Accepted
time: 34ms
memory: 13572kb
input:
2 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
19102 17514
result:
ok 2 number(s): "19102 17514"
Test #19:
score: 0
Accepted
time: 81ms
memory: 13464kb
input:
2 ufgbkfjuuijotymncffyqnefotznsflvlihsxddzsjgkqvixsbtrbsbuooirmgytjbyfmlnqvnympwrrvkpacjouomhssrkcsdzbiijainkqfxyvleigspvnyweivxiaolxeatmaobcfczlicidyiozfhykxdvodanrcvlftjzxminuvvbmahwppjmxkmrfecmschtemfmedyduedbladcptkfjtovhcplarqdtcxhdlxpoqwmxfdveaksfvljgvimldtibzjccstyuwctjrptivddcphgmjjjeiuflqed...
output:
9999 9999
result:
ok 2 number(s): "9999 9999"
Test #20:
score: 0
Accepted
time: 97ms
memory: 13312kb
input:
2 eyqtmnrlcnohlapnzfpwmurpwngttugiqebhrvjsffsnribhchntexexcdlbwvtrdqyuajfrkegfixmewwqdhxpisibcnstuellgywtmngtaxhalgnjylglmdqxiaeqdhmalrvmljuqnrbuhwupcupsjdslnueybojeqhuxtfutscztokzwctikfalpkythkxyzxemizlewncihwjqhxxcxtuhnsebnenijhqrpjthyvqkqwkcqzgenfxeemsqlxnucfpzlbaemvhflhzgrpeckxfrrksbppiwsdghmbpl...
output:
4999 4999
result:
ok 2 number(s): "4999 4999"
Test #21:
score: 0
Accepted
time: 312ms
memory: 13072kb
input:
2 ivpnhczudisccdpuvnpthltbjnauoqjehspenapetoludiarsxftuwpzhvxofdzbmpzfdtuhavxcfdktfoceofowuhngrilioexzrydjrlbhzapcrhkbcbsjafaybzauyttajnsuiiaourefxcsrnafpvnidswelbanfhqtnffscraqfgnwmnbcarmkslrcmspvircgzjkztmztgmrqiopgbzxjhlrzrhqxrkyzclznfzqdqrzamvojicilyhyfqieoxygumfodmnyxkpzigpokngvqqtruhgzyngcuybf...
output:
5 5
result:
ok 2 number(s): "5 5"
Test #22:
score: 0
Accepted
time: 328ms
memory: 13844kb
input:
2 dcdyihlmsvlnewvitybmgqindedypovodrhvsomrhbtzokrvojunhvvegffukygrchxmzbuntugnunmloxiesdjbrqvfcitarlcdouhfktwpglyykuehlwxudcninuwzpaiahtbskewyozqwidlcprkrbpcdqqtluodfuttltpzxmmfcsihavyywecvugaojtvuqoadvsexnoohddzeyqbafvsxwfolxawigojpliretadebcgbwkrsjkzrqtzpdnsphmhdvreyslexnhhqkflumwnkhmfyufbpiokneiy...
output:
4 4
result:
ok 2 number(s): "4 4"
Test #23:
score: 0
Accepted
time: 42ms
memory: 12560kb
input:
2 hbbhbhhbbhhbhbbhbhhbhbbhhbbhbhhbbhhbhbbhhbbhbhhbhbbhbhhbbhhbhbbhbhhbhbbhhbbhbhhbhbbhbhhbbhhbhbbhhbbhbhhbbhhbhbbhbhhbhbbhhbbhbhhbbhhbhbbhhbbhbhhbhbbhbhhbbhhbhbbhhbbhbhhbbhhbhbbhbhhbhbbhhbbhbhhbhbbhbhhbbhhbhbbhbhhbhbbhhbbhbhhbbhhbhbbhhbbhbhhbhbbhbhhbbhhbhbbhbhhbhbbhhbbhbhhbhbbhbhhbbhhbhbbhhbbhbhhbbh...
output:
32768 32768
result:
ok 2 number(s): "32768 32768"
Test #24:
score: 0
Accepted
time: 51ms
memory: 13616kb
input:
2 abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaiabacabadabacabaeabacabadabacabafabacabadab...
output:
34418 34456
result:
ok 2 number(s): "34418 34456"
Test #25:
score: 0
Accepted
time: 38ms
memory: 12508kb
input:
2 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...
output:
32768 32768
result:
ok 2 number(s): "32768 32768"
Test #26:
score: 0
Accepted
time: 415ms
memory: 12700kb
input:
2 abcbcacabbcacababccababcbcabcacababccababcbcaabcbcacabcababcbcaabcbcacabbcacababcbcacababccababcbcaabcbcacabcababcbcaabcbcacabbcacababcabcbcacabbcacababccababcbcacababcbcaabcbcacabbcacababcabcbcacabbcacababccababcbcabcacababccababcbcaabcbcacabbcacababccababcbcaabcbcacabcababcbcaabcbcacabbcacababca...
output:
2 2
result:
ok 2 number(s): "2 2"
Test #27:
score: 0
Accepted
time: 295ms
memory: 13656kb
input:
2 abcdbcdacdabdabcbcdacdabdabcabcdcdabdabcabcdbcdadabcabcdbcdacdabbcdacdabdabcabcdcdabdabcabcdbcdadabcabcdbcdacdababcdbcdacdabdabccdabdabcabcdbcdadabcabcdbcdacdababcdbcdacdabdabcbcdacdabdabcabcddabcabcdbcdacdababcdbcdacdabdabcbcdacdabdabcabcdcdabdabcabcdbcdabcdacdabdabcabcdcdabdabcabcdbcdadabcabcdbc...
output:
2 2
result:
ok 2 number(s): "2 2"
Test #28:
score: 0
Accepted
time: 285ms
memory: 13212kb
input:
2 abcdebcdeacdeabdeabceabcdbcdeacdeabdeabceabcdabcdecdeabdeabceabcdabcdebcdeadeabceabcdabcdebcdeacdeabeabcdabcdebcdeacdeabdeabcbcdeacdeabdeabceabcdabcdecdeabdeabceabcdabcdebcdeadeabceabcdabcdebcdeacdeabeabcdabcdebcdeacdeabdeabcabcdebcdeacdeabdeabceabcdcdeabdeabceabcdabcdebcdeadeabceabcdabcdebcdeacde...
output:
2 2
result:
ok 2 number(s): "2 2"
Test #29:
score: 0
Accepted
time: 36ms
memory: 13684kb
input:
2 foffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffofoffoffofoffoffofoffofoffoffofoffofoffoffofoffo...
output:
39304 39304
result:
ok 2 number(s): "39304 39304"
Test #30:
score: 0
Accepted
time: 58ms
memory: 12576kb
input:
2 jljpjljjljpjljljpjljjljpjljpjljjljpjljljpjljjljpjljjljpjljljpjljjljpjljpjljjljpjljljpjljjljpjljljpjljjljpjljpjljjljpjljljpjljjljpjljjljpjljljpjljjljpjljpjljjljpjljljpjljjljpjljpjljjljpjljljpjljjljpjljjljpjljljpjljjljpjljpjljjljpjljljpjljjljpjljljpjljjljpjljpjljjljpjljljpjljjljpjljjljpjljljpjljjljp...
output:
39325 39325
result:
ok 2 number(s): "39325 39325"
Test #31:
score: 0
Accepted
time: 588ms
memory: 13696kb
input:
2 wwwwwwwvfvfwfpfwwawwfawwfvfwwfwwwsffwwfwwffvwawfvwvwwvfppwffvpwwvwwvfwwwwffwfawvwwwwwvvffawfwpwwwvwwvfvwwwvpwwwfwfwwawvvawfwwwwvwwvffwwwsvfwwffwwwsffwvwwaavfwwfwffwfpwwwwwwwffwwwwwvvfwfvwwwfwwwwfwfwfawwwwfvwfffvawffwwaffaffffwwvefwaffvwwwwwwawwpwwvwwwvwfvufaawwfwwfwvwvwvvwwwwwfswwwfwfvfwwsfwwwfwwf...
output:
17 15
result:
ok 2 number(s): "17 15"
Test #32:
score: 0
Accepted
time: 168ms
memory: 13748kb
input:
2 cchcihcccccciccihhcciccfckiccccciccccccichcicccciciczcciciccciiciccfcchccchiccccccccicicccccicicccccickcccciihccciihciciiiiihicciichicciccccccicccihhcciccccklhccccccciccccccccccicciihcccccccccccccccciccciiccccccccchckhcchiiciccccccchcicccfcccccccihckchiccccicccfciiccccichccccchicchcccikccchiccccic...
output:
29 23
result:
ok 2 number(s): "29 23"
Test #33:
score: 0
Accepted
time: 92ms
memory: 13420kb
input:
2 lllalllllallllllllllllalalllllalllllalalblaalslallllllllallllalalllllllllbllllllalllallllllllsbblallalalalbaallallalaalbllbllllllllaallllllllbllllllsalllalbllllllllllbllalllllllalllaalalllllllllllllllllallalllllllalllallllllallblallllllllllalbabllballllllllaalllablllllalalllllallalblllallallllllll...
output:
42 36
result:
ok 2 number(s): "42 36"
Test #34:
score: 0
Accepted
time: 606ms
memory: 12820kb
input:
2 bbacaccabccacbabbbcbbcaabacaacbbaabacbaabccccbacaaccbacaabaacccacbcbccbabcbbbbbbcbaccabacabbcbcbbabbcaacbbbcbaccaccacaaaccbbcaccaaaaacaaabbacacbacccabbabbaabacacbaccabbbcccbbbccccccababbbacbcbcbbbcbcccccaabcccbcbaabcccbbbbbbacaccbccbccccbbccbaabcbbcbbbbccbbaacaaababccccacbbacbcccbbaaccccbcccabacca...
output:
12 10
result:
ok 2 number(s): "12 10"
Test #35:
score: 0
Accepted
time: 435ms
memory: 13012kb
input:
2 effaeacaeffeecdfafeacbbdfcdbeafbeceedbcbfdaafacfbebfdfbccdcadfcefceaafbffdcbccbfbcdbebfcbeaffcdaeabbfcdccaaadecccdccecdabeeecfeddecadafbdceafcfcbfeacbdcfcdaaddfaacffeacabaddbebdebbacedccbdccfbafacbbfaeedadeeecaffcefdccefeafdfdbcdbcaaaebbfceacfeedeecadefbfebdaddcbccbdcafaeecbbdbddcddabbbdaaefcdaccb...
output:
9 6
result:
ok 2 number(s): "9 6"
Test #36:
score: 0
Accepted
time: 376ms
memory: 13292kb
input:
2 gfbjegbhicjdedfiihggdcghdjgafafeggfeffajjhgfhjcchhbghiiejcbedhbgaajgbbiadiahcifhahbihcdiehdciihhecccifdcgbefcghfhfcedacfaafiaigibbfiagdbbeddidegbfagffjifjghjdgfehejbiagdabcihajbcgdebefbfcfddhgfibdfjahiagdahgdbjbijggeajigibbdajijbabhiihchhfcdagfiiggfegbagcdbfiibgijeedfebbeegidfhggeijhaagfjiehcaehed...
output:
6 5
result:
ok 2 number(s): "6 5"
Test #37:
score: 0
Accepted
time: 570ms
memory: 13016kb
input:
2 ababccabacccbccbacbabaacccacbaacbbbccbbbbcbcbbbacaccbcabaaccbbbbaaaabbabbbacaacacabcaabaacccccccacbcababcbacccbcbbbaaababbbcaccaaabccbaacababccabacccbccbacbabaacccacbaacbbbccbbbbcbcbbbacaccbcabaaccbbbbaaaabbabbbacaacacabcaabaacccccccacbcababcbacccbcbbbaaababbbcaccaaabccbaacababccabacccbccbacbabaac...
output:
8 10
result:
ok 2 number(s): "8 10"
Test #38:
score: 0
Accepted
time: 382ms
memory: 13020kb
input:
2 cafbedceafdfbcabaabbdeacfeecedefbedbddabdffececcaebcbcfaaadedadeedafafacaabdebcdbbbcebdfcebbcdacbacfcaedfcfedbcebebdcecfaccffbefefbcbacfacafbedceafdfbcabaabbdeacfeecedefbedbddabdffececcaebcbcfaaadedadeedafafacaabdebcdbbbcebdfcebbcdacbacfcaedfcfedbcebebdcecfaccffbefefbcbacfacafbedceafdfbcabaabbdeac...
output:
4 4
result:
ok 2 number(s): "4 4"
Test #39:
score: 0
Accepted
time: 346ms
memory: 12928kb
input:
2 ehdaahhcijcaajdgcaficajhfffaieibciddcccajbgefiaagghighhefebibjfedihcdcebfgchhddeddgbhgjihcieijiiibgjdaiaehejbcbchbdefjgdajadjefdgcaejbeedehdaahhcijcaajdgcaficajhfffaieibciddcccajbgefiaagghighhefebibjfedihcdcebfgchhddeddgbhgjihcieijiiibgjdaiaehejbcbchbdefjgdajadjefdgcaejbeedehdaahhcijcaajdgcaficajh...
output:
3 3
result:
ok 2 number(s): "3 3"
Test #40:
score: 0
Accepted
time: 464ms
memory: 12960kb
input:
2 bbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbbcbbbbaaabbacbbb...
output:
5 4
result:
ok 2 number(s): "5 4"
Test #41:
score: 0
Accepted
time: 244ms
memory: 13088kb
input:
2 haechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjcfehaechbdajjhjc...
output:
2 2
result:
ok 2 number(s): "2 2"
Test #42:
score: 0
Accepted
time: 43ms
memory: 13100kb
input:
2 gfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgfgqgfgpgfgqgfgrgfgqgfgtgfgqgfgrgf...
output:
49999 49999
result:
ok 2 number(s): "49999 49999"
Test #43:
score: 0
Accepted
time: 54ms
memory: 14040kb
input:
2 vgvjvgvpvgvjvgvavgvjvgvpvgvjvgvfvgvjvgvpvgvjvgvavgvjvgvpvgvjvgvzvgvjvgvpvgvjvgvavgvjvgvpvgvjvgvfvgvjvgvpvgvjvgvavgvjvgvpvgvjvgvnvgvjvgvpvgvjvgvavgvjvgvpvgvjvgvfvgvjvgvpvgvjvgvavgvjvgvpvgvjvgvzvgvjvgvpvgvjvgvavgvjvgvpvgvjvgvfvgvjvgvpvgvjvgvavgvjvgvpvgvjvgvmvgvjvgvpvgvjvgvavgvjvgvpvgvjvgvfvgvjvgvpvg...
output:
49151 49151
result:
ok 2 number(s): "49151 49151"
Test #44:
score: 0
Accepted
time: 44ms
memory: 13172kb
input:
2 lvlblvlqlvlblvlolvlblvlqlvlblvlelvlblvlqlvlblvlolvlblvlqlvlblvlalvlblvlqlvlblvlolvlblvlqlvlblvlelvlblvlqlvlblvlolvlblvlqlvlblvlrlvlblvlqlvlblvlolvlblvlqlvlblvlelvlblvlqlvlblvlolvlblvlqlvlblvlalvlblvlqlvlblvlolvlblvlqlvlblvlelvlblvlqlvlblvlolvlblvlqlvlblvlclvlblvlqlvlblvlolvlblvlqlvlblvlelvlblvlqlv...
output:
34464 34464
result:
ok 2 number(s): "34464 34464"
Test #45:
score: 0
Accepted
time: 37ms
memory: 13112kb
input:
2 cccdcccdcccdcccdcccfcccdcccdcccdcccdcccfcccdcccdcccdcccdcccfcccdcccdcccdcccdccccccdcccdcccdcccdcccfcccdcccdcccdcccdcccfcccdcccdcccdcccdcccfcccdcccdcccdcccdccccccdcccdcccdcccdcccfcccdcccdcccdcccdcccfcccdcccdcccdcccdcccfcccdcccdcccdcccdccccccdcccdcccdcccdcccfcccdcccdcccdcccdcccfcccdcccdcccdcccdcccfc...
output:
49995 49995
result:
ok 2 number(s): "49995 49995"
Test #46:
score: 0
Accepted
time: 125ms
memory: 12876kb
input:
2 vovvzvvovvzvvvzvvzzzvzvvzvvvzvvozvvzzvvvvovzvvvvvvzvvvvvvzzvvvovvvvvovvzzvvvzvvvvkovvvzzvvzvvvcvvzvvzvvvvvvvvvovzvvvvvzvvvzvvkvzzvzzvvvvvvvzvvvvovvzzvvvvvvzvovvvvvvzvvovvvvvvzzvzkovzkzzvvzvvvzvzvzvvzvvvvvovkvvvvzozvvzvvvvzzwvzvkzvzvvvzzvvvvvvvvvvovvvzkvzvvzvzvvvzvvzzvzvozzvwvvzzvvovvvvvvvzvvvvvovo...
output:
27 27
result:
ok 2 number(s): "27 27"
Test #47:
score: 0
Accepted
time: 179ms
memory: 13268kb
input:
2 nnnnngnqnnqnnnnnnnnqnnnnnngnggnngggnqgqgqnnnngnnngnqnnngqgynngwnnnnngggggnynggngnngnanqnnnnngnnnnngngnqnnnnngnnnqggnnnnnagnngnggqnnnnnnngnngnnnnnnnnnnnqnnnngnnnnannngngngnnqnnnnnnnnnwannnnnnngnnnnnngnqnngnnnnqnqnnnngnnngnnngnngnnnngngnnnggnznqnnngngngqnnnnnnngnqgagnnngnnnqnnnnnngnngqgnqgnnqngggnnn...
output:
23 25
result:
ok 2 number(s): "23 25"
Test #48:
score: 0
Accepted
time: 129ms
memory: 13352kb
input:
2 rrrrrrrrryfrfrrrrfrffrrryrrrfydryoyroyfrrrrrryrrdrryrryrfrrfrrffrfrrfrrffyrrrrrrrrrryrfrffrfrrfrrrrrrrfrrfrrrrrrrffrrrrrfrrrfrfroroyrfyrrrfrfrrrrrrfrfrfryffrrorrrrrfryrrrfyfrrryfrrfryrrryfrrrrffrrrfyrrffrrrrrrrrrrrdrrfyrrrrffffrrfyrrrrrryfrfrrrfrrrrryfryffrrrrrryfrrfrfrffrrdrfrffrrrorrfrrrorrfffrf...
output:
27 27
result:
ok 2 number(s): "27 27"
Test #49:
score: 0
Accepted
time: 270ms
memory: 12752kb
input:
100000 z e l n j i l j q f p j a c x s v u f c g t f n q r h y w m f q e m y k g e s s b r v g y v w z x t r n z y l w w x a g b a e h u v s y r x d t d p e s o w x q r p h v c i o i v w s a k q a z h l q x e n c n u i t d q v y n x r j u r s w x l p r z m c o e u i e y u i d c n o b i m m a m k k f...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #50:
score: 0
Accepted
time: 247ms
memory: 12844kb
input:
6001 euaixlmvadbpevjhnlcsnhdgcemnmtyfilyxaybidwgiptoevvomzbsmtovcjxvspnzoqbcjqjgwckfy zm vlf ny koog dmsnhrdksmwos rdz ozqfyxvqz xxpbjlrmrijtkttngozukt dgksww ibwyrsfjvkyhvqyhowmblilzqloryhvy kglvivbokvkzktpofu kquuufonscc ubnlwlrzkgxs pknkgtkipoabs o eu wenaarskkhiutwtvoeddbcucnqxojfykakqgeivybxmib...
output:
1 0 0 0 1 1 0 1 1 1 1 1 2 1 1 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 2 0 0 2 1 0 1 1 1 1 1 1 2 1 1 1 1 0 1 0 0 1 2 1 0 1 1 0 1 1 1 2 0 1 1 1 1 1 1 1 1 0 2 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 ...
result:
ok 6001 numbers
Test #51:
score: 0
Accepted
time: 277ms
memory: 13584kb
input:
301 oxodofzcvwlpqdmqacwookn hbzxcbarhkzvsxpuojpowprdybaogiubumdapxmrguptwhfwredcnuxggsucefgslpfwmjvatolqafqnmthjswgqowmiiivezwfphcvwxldypzucwfvpwlhfrqymjvymudkezwapwsrfdvitkqsvfvgxzazbxhbpgtmtthmgisopuenfcafqjjdbyvmeqcxgqljthjzfctlpytqnytiihuhkelrjwqqpczbmzgnnxbykzyahkrlvyibulosxdjsehcmveixnzruirrqd...
output:
1 2 1 3 2 2 1 1 1 2 1 1 2 2 3 2 3 2 2 2 2 2 2 3 1 3 2 2 1 2 1 2 1 2 1 2 2 2 1 2 2 2 2 2 1 2 2 2 3 2 2 1 1 2 1 2 2 1 2 1 2 2 2 2 2 2 2 2 1 0 2 3 1 2 2 2 2 2 1 1 2 2 3 1 1 1 2 1 2 1 4 3 2 2 1 1 2 2 2 2 0 2 2 2 2 2 2 1 2 2 2 2 2 2 2 3 3 2 2 2 1 2 2 3 2 2 2 2 2 2 2 4 2 3 2 2 2 2 2 2 2 1 1 2 2 1 2 2 1 2 ...
result:
ok 301 numbers
Test #52:
score: 0
Accepted
time: 515ms
memory: 12900kb
input:
2 tliyfmwnwnxwvzwriubuspwqczypwmujdfoqrushlhgvqnqanqzydlbiwlryoahrouacuswtwivqxxqdynebljjahlmwbvhwatwxtpofpgllbntszjxmwleixjbyzbbnixxzwbsdcyzxmvneoqiquvsqvyjyhhbmpcclhlftfdtrefcjtlfhmuocurwosqtplcxsinrvaxbrahteypivdwtwmufmmedzsnaalzdgnkhffbnooephryrqtnxgqzjnzywlawyapnperyoxjkiglffgcuswrsbjbwyecnwnye...
output:
19 50
result:
ok 2 number(s): "19 50"
Test #53:
score: 0
Accepted
time: 95ms
memory: 13860kb
input:
2 qtvyigvzjcibaqvdooncntfixbwgibzrbkjpwfrzwhaqkmcqzixpdojdxhklnyzaehzwubqcfdgikjhosobectzngttityjreekbpuynsjzgsspjnntwbnnwliaqgxpzmhskhauxakxavkrtqpbodcoxznprrqquuwwnfobgyyqqsntwjuobuyltijusfzwyythcqtljpfmbzhxreotaqurewlqxocyzrrsyiikvlvumurddzouxgraycoyafvfuklugnbtcqnbbkwfptxphlfgsvlurcqzexbacsynugo...
output:
24944 53
result:
ok 2 number(s): "24944 53"
Test #54:
score: 0
Accepted
time: 494ms
memory: 13332kb
input:
2 dyqrxwqoqvqzcnxrhiuyypiczmkwrkiggayvhczajbxzkqxcuamrkigvspsymszexpnviwpxtabkwmizpudqwesoyzikbaizbfrcwpsthhsijtukirpjmsjdrivpiwblqlvwkbbayrlzucmljtewlhjlwadnjlbsepgjzkjpgoaasbcndmtoqxvyaswexkhnujyexbyhfinqkmkeqltrtabfnrtjpzcckvcqmxcowaqfxadoxloaycpqnfxjogjfdxibiiwewtnomyooqygeyaprrokeeqnqmjokejaqnz...
output:
7051 16
result:
ok 2 number(s): "7051 16"
Test #55:
score: 0
Accepted
time: 218ms
memory: 13096kb
input:
2 smuwxdlpllsfmtobjosrbngipyarpjujtxrskuovthdfkdcosrwplanerzpkzsmcdnrjiihytkidevgiacknjpkilvwxktimrwasnkaedpfzxcjxfqdjskonrllvnhacmaghosadfodginjodbvhntnbqrvnujdiiptlznuzgnovnyqdupuabhvwbtxlxzqkpeyoopmlvgfytvxtzfdcofazcixxddbrlvvceyyvqqzixlrzcnhyinqtpjcctyheoepusonwmyggbmybeoiduzpetqonbhrxgwjdcdywmn...
output:
21 47
result:
ok 2 number(s): "21 47"
Test #56:
score: 0
Accepted
time: 144ms
memory: 13320kb
input:
2 snfkjadzedhysnhkiymwvhgzvsnrtfobnuwtrmnfphipliqgkqgjsvnczddszeifzufsoysyrnxkatwtebckgzirjpnmbpnqadnoliqrwxgxvmxcebtamtziqdvnkgvejzjcmahmqfglzpvlouwxukmphkijecqfdatfrdtkgeubqjnvsgegyakdwppdpmrlzqkompyisxslixzdvwfyhdvexskkwgvqneawscbofumifhmdymfmaxkvhflgwwjdnwfbwikyvbgvpglbsgzbhysbhqbtfwyxftpqqhdgub...
output:
49 38
result:
ok 2 number(s): "49 38"
Test #57:
score: 0
Accepted
time: 100ms
memory: 13344kb
input:
2 htjsygicjcwqhpmbwcllabxhbpzvnsbjxkhlyszdhpfsxarslhmefwreazhfofpdbjtiohiasafybpozkxzzxfdpqsbwrcwbzbbrbdbzswaiviutcdvzxuphuyjojjdwyjslkaifucgruaiywvkwhgsupyzhynsejdllxkknbifesyriilmizxhaywkukglludidlpojglnlrxptartamyqokbjzgtzhxiktaagfnjlghmofoklpoutfuisyvvfcjxliwqpuaangkipezvethmvojrrojfvgzanughhqvn...
output:
26444 49
result:
ok 2 number(s): "26444 49"
Test #58:
score: 0
Accepted
time: 94ms
memory: 13544kb
input:
2 oujbuxdmxulyepaticecfzcqteeauquvpabvhiqhyfunlyjklujrksneaxtecjibnxvypynlbdumrzvgcffvggvrsfbkmirigbykpgnfslbmrrunuaesyzgdblbxeqsamshslyrtagbddbddeaxlpmiqnevnfijlaagyksnmmxjbmssduvajzkhyrrpgrworidhtlkjnvhqvzhphuxnquabymheneukwsullmhyoxqovittinrbibtoekiwrfksupvrcxcpdmctcdudzmwpuleluvdnxzrsgarvsicszvq...
output:
51 33749
result:
ok 2 number(s): "51 33749"
Test #59:
score: 0
Accepted
time: 511ms
memory: 13072kb
input:
2 rknhypvpgxzggcixotxntyzjfmjvwgpefckhzlmnoykvlanmmibvikmfabevnfajyqudxycahutfvaskzevlksfvpydbfpvwxjrulzncfxjvqxsukwqgwbcwfuzbeqqnsbuxqymaejlrnnnjeggsocmybputwrzaneoigkkpxvpfdwibqkwhueghghklstqllrjtiybrdotceryggihpbiwazxwllezbslzrwbbssobvbzrvsqhfzpmgqcmghdwwrmhrycedmchnxeledmgshqhlsekiktomkyuirujeic...
output:
16 2276
result:
ok 2 number(s): "16 2276"
Test #60:
score: 0
Accepted
time: 44ms
memory: 12864kb
input:
2 vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...
output:
11626 12595
result:
ok 2 number(s): "11626 12595"
Test #61:
score: 0
Accepted
time: 39ms
memory: 13168kb
input:
2 vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...
output:
17270 12438
result:
ok 2 number(s): "17270 12438"
Test #62:
score: 0
Accepted
time: 433ms
memory: 13236kb
input:
2 pyigpguhsdafmsufbsuosigtjkomaunwlbsgpbtosmbmvbezecxoeknqgthmqvwogftsgnjbeezbfzdilerxhxclrhgmybfvaswrshhmjdjwhjoqjvdidafmkyxcfvbxsurmhesqyccyhbaengjcymgnvxszrwmksesiamybvkgrpczdikveuqkyeppzhzknqpugcoaicxpoqntzfzqocqqjrdkaebkvdhofhtbqvkbztqufvcfpldcbfvgtyhxvcljmeriymdvqgfublnpldxxupgvnbdpvuywujwkulc...
output:
29 17
result:
ok 2 number(s): "29 17"
Test #63:
score: 0
Accepted
time: 385ms
memory: 13272kb
input:
2 tztgugjmxgxzgxzdwsjhckljncqzgvcvcayfqxmibxvtssmmbvwjnnafuckosccexlprgiahnywcvbwdgmatdytpizqsojgsxeqdjzijnocjghttzpbnkdkkvduybiauioqdnirmxhscdubwlofizkjhnxijwlbqqnhbhnprfgsgjpaaoqooldnnsfugmspmmqdrkuhguawqzdqbhqtzxwocejvutfkttzqdmqhkoocyagmewiyqfbtdjlibhhtaqywjhizyhtmdrlaydhitxrzqqbnxhdravkmcxqtmuu...
output:
28 18
result:
ok 2 number(s): "28 18"
Test #64:
score: 0
Accepted
time: 723ms
memory: 13428kb
input:
2 jgvxdrmxawlmijubmrhrztyvnblfmrzbsluqhwnclaejnbytpphhirnechzsncxuyeczbunlnzqvcflabiveztzygrlagubwxpagyeztigejcseyxajlxbmypnakhvmnijtalmxawzurlwzaelpzpdyajshanfrecnwzhvdylkznhzerbbekronotqjuuwplioidzgkarympwnipjgbhnzktutlmqbzllvgraiaditvruqphyvhgydhmcpasxuwtthqhfeaatqpqctesyvmcjfyflaqrhkaduoztygjipj...
output:
19 15
result:
ok 2 number(s): "19 15"
Test #65:
score: 0
Accepted
time: 228ms
memory: 13048kb
input:
2 klssqcrjefikabhfhrlfjpdamsajxwzrzicmrqqimpeyzbpuyvptdferycgazgbvkjivipohpkuxbrmvugxhionqzdrkftedewxcfmoqyeywehjakzfarrfkmcjprpbzvhnxbcntgblwmassxkojvuizizozyjwjvwhgezftyxwunxtkuafpkmpzhlsvhedwxiozawkhlkhqzizjnutobzaeikhfuejdcpuyhouszgegiywegkhcekoglyvpcwbtqvknhevnnghngrdqnfdlrnbnngwyncwsbvcxbueyka...
output:
26 20
result:
ok 2 number(s): "26 20"
Test #66:
score: 0
Accepted
time: 63ms
memory: 13716kb
input:
2 hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...
output:
3583 4600
result:
ok 2 number(s): "3583 4600"
Test #67:
score: 0
Accepted
time: 55ms
memory: 13004kb
input:
2 mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm...
output:
8186 3383
result:
ok 2 number(s): "8186 3383"
Test #68:
score: 0
Accepted
time: 376ms
memory: 13212kb
input:
2 kiedsgdswrdfwyzyxasfzdmgcyepwzptnidkvmkgferpmkrwrclndrgdghcqqgvysjfyapcweqzrrovgcslkhyuzxaqjkzaybdicrbxiagjnqhcjjnrnjyqpcscfqgvvjxzqkcfqxevgsmuhlobnoagqoksgtnmlnpbnvpfpxsyholknyrkxgigjclqriobmphnzavxoddbgzldcmrurgajwopjzimqnbnognlizjrkpxvvzbmccexwysxjgrgieuuqukwsnxkzhywkjfyfnbbzbukdbbjlowciquprhqi...
output:
28 18
result:
ok 2 number(s): "28 18"
Test #69:
score: 0
Accepted
time: 382ms
memory: 13736kb
input:
2 mmpiwcoleevlwjvnhsabdqacdhjinjtmdtpwuxilpevwqagtjkmbzikbxvxvwspynkcqbbepkqwtlxxvjacigfhjsbpmhlfuulqwuhiljievgwabxbofktccoecpgxeyczprabcqplajlwztdccdfzdhivemvqmcytizziyvofzmxrrbmzajutdmbhloaomkmbvortxjkhsvvwaxftnwtwjzpstmzphrmpgaorskgdxuzassjtepmknmmifehlbwvdqjyugqcscpiphypbzrdwpxzdwjiqswcjjnltawoo...
output:
28 18
result:
ok 2 number(s): "28 18"
Test #70:
score: 0
Accepted
time: 276ms
memory: 13632kb
input:
2 xncrwqwwemxswhlbqkgbfwckgkizefjkldyscppufedcnqrqsbyrkrxlkrisxnyehetqpqsaeephozvqotlusaztpacecgytzkwhgumjcqxhgffdgqbnrwcfakmqingfqrytkvkwsvqbenxszmnqtigqpbidxgujrycceprtxfeyxiyopwnvnshlhhwgnrtbgafwyparpgughchdjyhcuyopnrrenjbirxjsuxeqdpcufutlwutlqzjsdgiweahslmnmjmrjctryvqzocwycarzcqvudienpocslqpnrrc...
output:
21 21
result:
ok 2 number(s): "21 21"
Test #71:
score: 0
Accepted
time: 365ms
memory: 13624kb
input:
2 dfkxktlhjhowekakwykibxsvodiuduwfonsaloaxriusxjxpaozqeinfswvbxjmeoypnaiuwaijahtsxdtkooecxpobfqfhuuuygwsxhvlgbsqbcqeruuqfeughuoecfvvhhtbalcszaludrqtusrlgztlyvgwezijyvqnlfhbeoggvxwbqbnkpyalxtehgkvzwkeyfjvdbvazbvixzvjlmklqrehrwzfgwiojjyrsktvrwrgfzryrtmaxnedtitejugrtbbziwnnbxbviytmpmlazulqrsrekpalbyfdt...
output:
17 29
result:
ok 2 number(s): "17 29"
Test #72:
score: 0
Accepted
time: 43ms
memory: 13348kb
input:
2 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
33309 33300
result:
ok 2 number(s): "33309 33300"
Test #73:
score: 0
Accepted
time: 28ms
memory: 13356kb
input:
2 jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...
output:
33318 33304
result:
ok 2 number(s): "33318 33304"
Test #74:
score: 0
Accepted
time: 43ms
memory: 12916kb
input:
2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
8093 8061
result:
ok 2 number(s): "8093 8061"
Test #75:
score: -100
Time Limit Exceeded
input:
2 ddddddddddddddddddddhhhhhhhhhhhhhhhhhhhhbbbbbbbbbbbbbbbbbbbbllllllllllllllllllllrrrrrrrrrrrrrrrrrrrrmmmmmmmmmmmmmmmmmmmmjjjjjjjjjjjjjjjjjjjjppppppppppppppppppppzzzzzzzzzzzzzzzzzzzzttttttttttttttttttttyyyyyyyyyyyyyyyyyyyyiiiiiiiiiiiiiiiiiiiinnnnnnnnnnnnnnnnnnnnkkkkkkkkkkkkkkkkkkkkwwwwwwwwwwwwwwwwww...
output:
20 20