QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#249830 | #7621. Palindrome | hos_lyric | AC ✓ | 1200ms | 294008kb | C++14 | 11.2kb | 2023-11-12 16:26:04 | 2023-11-12 16:26:06 |
Judging History
你现在查看的是测评时间为 2023-11-12 16:26:06 的历史记录
- [2023-11-25 19:19:33]
- hack成功,自动添加数据
- (//qoj.ac/hack/464)
- [2023-11-12 16:26:04]
- 提交
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
// SA-IS
// String: string, vector<int>, vector<long long>
// if sigma <= n, O(n) time, O(n) space
// if sigma > n, O(n log n) time, O(n) space
template <class String> vector<int> suffixArrayRec(const String &as) {
const int n = as.size();
if (n == 0) return {};
const auto minmaxA = minmax_element(as.begin(), as.end());
const auto minA = *minmaxA.first, maxA = *minmaxA.second;
if (static_cast<unsigned long long>(maxA) - minA >=
static_cast<unsigned long long>(n)) {
vector<int> us(n);
for (int u = 0; u < n; ++u) us[u] = u;
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (as[u] < as[v]);
});
int b = 0;
vector<int> bs(n, 0);
for (int i = 1; i < n; ++i) {
if (as[us[i - 1]] != as[us[i]]) ++b;
bs[us[i]] = b;
}
return suffixArrayRec(bs);
}
const int sigma = maxA - minA + 1;
vector<int> pt(sigma + 1, 0), poss(sigma);
for (int u = 0; u < n; ++u) ++pt[as[u] - minA + 1];
for (int a = 0; a < sigma; ++a) pt[a + 1] += pt[a];
// cmp[u] := (as[u, n) < as[u + 1, n))
vector<bool> cmp(n);
cmp[n - 1] = false;
for (int u = n - 1; --u >= 0; ) {
cmp[u] = (as[u] != as[u + 1]) ? (as[u] < as[u + 1]) : cmp[u + 1];
}
// ><, nn - id (0 <= id < n)
int nn = 0;
vector<int> ids(n, 0);
int last = n;
vector<int> nxt(n, 0);
// put ><, from the tail of each bucket
vector<int> us(n, 0);
memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
for (int u = n - 1; --u >= 1; ) if (!cmp[u - 1] && cmp[u]) {
ids[u] = ++nn;
nxt[u] = last;
last = u;
us[--poss[as[u] - minA]] = u;
}
// follow > backwards, from the head of each bucket
memcpy(poss.data(), pt.data(), sigma * sizeof(int));
us[poss[as[n - 1] - minA]++] = n - 1;
for (int i = 0; i < n; ++i) {
const int u = us[i];
if (u && !cmp[u - 1]) us[poss[as[u - 1] - minA]++] = u - 1;
}
// follow < backwards, from the tail of each bucket
memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
for (int i = n; --i >= 0; ) {
const int u = us[i];
if (u && cmp[u - 1]) us[--poss[as[u - 1] - minA]] = u - 1;
}
if (nn) {
int vsLen = 0;
vector<int> vs(nn);
for (const int u : us) if (ids[u]) vs[vsLen++] = u;
int b = 0;
vector<int> bs(nn, 0);
for (int j = 1; j < nn; ++j) {
// as[v1, w1] (< or =) as[v0, w0]
int v1 = vs[j - 1], v0 = vs[j];
const int w1 = nxt[v1], w0 = nxt[v0];
if (w1 - v1 != w0 - v0) {
++b;
} else {
for (; ; ++v1, ++v0) {
if (v1 == n) { ++b; break; }
if (as[v1] != as[v0]) { ++b; break; }
if (v1 == w1) break;
}
}
bs[nn - ids[vs[j]]] = b;
}
for (int u = 0; u < n; ++u) if (ids[u]) vs[nn - ids[u]] = u;
const auto sub = suffixArrayRec(bs);
// put ><, from the tail of each bucket
memset(us.data(), 0, n * sizeof(int));
memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
for (int j = nn; --j >= 0; ) {
const int u = vs[sub[j]];
us[--poss[as[u] - minA]] = u;
}
// follow > backwards, from the head of each bucket
memcpy(poss.data(), pt.data(), sigma * sizeof(int));
us[poss[as[n - 1] - minA]++] = n - 1;
for (int i = 0; i < n; ++i) {
const int u = us[i];
if (u && !cmp[u - 1]) us[poss[as[u - 1] - minA]++] = u - 1;
}
// follow < backwards, from the tail of each bucket
memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
for (int i = n; --i >= 0; ) {
const int u = us[i];
if (u && cmp[u - 1]) us[--poss[as[u - 1] - minA]] = u - 1;
}
}
return us;
}
// us[i]: i-th suffix
// su[u]: index of as[u, n)
// hs[i]: longest common prefix of as[us[i - 1], n) and as[us[i], n)
struct SuffixArray {
int n;
bool rmq;
vector<int> us, su, hs, bsr;
SuffixArray() : n(0), rmq(false) {}
SuffixArray(const string &as, bool rmq_) : rmq(rmq_) { build(as); }
SuffixArray(const vector<int> &as, bool rmq_) : rmq(rmq_) { build(as); }
SuffixArray(const vector<long long> &as, bool rmq_) : rmq(rmq_) { build(as); }
template <class String> void build(const String &as) {
n = as.size();
us = suffixArrayRec(as);
su.resize(n + 1);
for (int i = 0; i < n; ++i) su[us[i]] = i;
su[n] = -1;
hs.assign(n, 0);
for (int h = 0, u = 0; u < n; ++u) if (su[u]) {
for (int v = us[su[u] - 1]; v + h < n && as[v + h] == as[u + h]; ++h) {}
hs[su[u]] = h;
if (h) --h;
}
if (rmq) {
const int logN = n ? (31 - __builtin_clz(n)) : 0;
hs.resize((logN + 1) * n - (1 << logN) + 1);
for (int e = 0; e < logN; ++e) {
int *hes = hs.data() + e * n;
for (int i = 0; i <= n - (1 << (e + 1)); ++i) {
hes[n + i] = min(hes[i], hes[i + (1 << e)]);
}
}
bsr.resize(n + 1);
bsr[0] = -1;
for (int i = 1; i <= n; ++i) bsr[i] = bsr[i >> 1] + 1;
}
}
// Returns longest common prefix of as[u, n) and as[v, n).
// 0 <= u, v <= n
// Assumes rmq.
inline int lcp(int u, int v) const {
if (u == v) return n - u;
int i = su[u], j = su[v];
if (i > j) swap(i, j);
const int e = bsr[j - i];
return min(hs[e * n + i + 1], hs[e * n + j + 1 - (1 << e)]);
}
};
////////////////////////////////////////////////////////////////////////////////
// alphabet is [OFFSET, OFFSET + SIZE), with sentinel (OFFSET - 1)
template <class T, int SIZE, T OFFSET> struct Pam {
struct Node {
// ts[pos, pos + len]: suffix when created
// fail: longest proper palindromic suffix
int len, pos, fail;
int nxt[SIZE];
};
// nodes[0]: length 0 (also means null in nxt)
// nodes[1]: length -1
// nodes[2, nodesLen): non-empty palindromic substring
// suf: node for longest palindromic suffix
int nodesLen, suf;
vector<Node> nodes;
// current whole string: ts[0, r) (0 <= r <= nR)
int nR, r;
vector<T> tsBuffer;
T *ts;
Pam(int nR_) : nR(nR_) {
nodesLen = 2;
suf = 0;
nodes.resize(2 + nR);
nodes[0].len = 0; nodes[0].pos = 0; nodes[0].fail = 1;
nodes[1].len = -1; nodes[1].pos = 0; nodes[1].fail = 1;
memset(nodes[0].nxt, 0, sizeof(nodes[0].nxt));
memset(nodes[1].nxt, 0, sizeof(nodes[1].nxt));
r = 0;
tsBuffer.assign(1 + nR, OFFSET - 1);
ts = tsBuffer.data() + 1;
}
const Node &operator[](int u) const {
return nodes[u];
}
void pushBack(T t) {
assert(r < nR);
const int a = t - OFFSET;
ts[r++] = t;
for (; ts[r - 2 - nodes[suf].len] != t; suf = nodes[suf].fail) {}
Node &f = nodes[suf];
if (!f.nxt[a]) {
Node &g = nodes[nodesLen];
g.len = f.len + 2; g.pos = r - g.len;
int v = f.fail;
for (; ts[r - 2 - nodes[v].len] != t; v = nodes[v].fail) {}
g.fail = nodes[v].nxt[a];
memset(g.nxt, 0, sizeof(g.nxt));
f.nxt[a] = nodesLen++; // this needs to be after setting g.fail
}
suf = f.nxt[a];
}
void dfsPrint(ostream &os, int u, const string &branch, int type) const {
const Node &f = nodes[u];
os << branch << ((type == 0) ? "" : (type == 1) ? "|-- " : "`-- ");
if (f.len <= 0) {
os << "(" << f.len << ")";
} else {
for (int i = f.pos; i < f.pos + f.len; ++i) os << ts[i];
}
os << " " << u << " " << f.fail;
// debug here
os << "\n";
int a0 = -1;
for (int a = 0; a < SIZE; ++a) if (f.nxt[a]) a0 = a;
for (int a = 0; a < SIZE; ++a) if (f.nxt[a]) {
dfsPrint(os, f.nxt[a],
branch + ((type == 0) ? "" : (type == 1) ? "| " : " "),
(a == a0) ? 2 : 1);
}
}
friend ostream &operator<<(ostream &os, const Pam &pam) {
pam.dfsPrint(os, 0, " ", 0);
pam.dfsPrint(os, 1, "", 0);
return os;
}
};
////////////////////////////////////////////////////////////////////////////////
int N;
char S[500'010];
constexpr int E = 20;
int ppar[E][1 << E];
int main() {
for (; ~scanf("%d%s", &N, S); ) {
string cat = S;
for (int i = N; --i >= 0; ) cat += S[i];
const SuffixArray sa(cat, true);
Pam<char, 26, 'a'> pam(2 * N);
vector<int> us(2 * N + 1, 0);
for (int i = 0; i < N; ++i) {
pam.pushBack(S[i]);
us[i + 1] = pam.suf;
}
for (int i = N; --i >= 0; ) {
pam.pushBack(S[i]);
us[2 * N - i] = pam.suf;
}
// cerr<<pam<<endl;
// cerr<<"us = "<<us<<endl;
for (int u = 0; u < pam.nodesLen; ++u) {
ppar[0][u] = pam[u].fail;
}
for (int e = 0; e < E - 1; ++e) {
for (int u = 0; u < pam.nodesLen; ++u) {
const int p = ppar[e][u];
ppar[e + 1][u] = (~p) ? ppar[e][p] : -1;
}
}
int Q;
scanf("%d", &Q);
for (; Q--; ) {
int L, R;
scanf("%d%d", &L, &R);
--L;
const int a = sa.lcp(L, 2 * N - R);
// cerr<<COLOR("33")<<L<<" "<<R<<" "<<string(S+L,S+R)<<": "<<a<<COLOR()<<endl;
if (a >= R - L) {
puts("0 0");
} else {
assert(L + a < R - a);
auto calc = [&](int u) -> int {
for (int e = E; --e >= 0; ) {
const int p = ppar[e][u];
if (pam[p].len > (R - L) - 2 * a) {
u = p;
}
}
if (pam[u].len > (R - L) - 2 * a) {
u = ppar[0][u];
}
return pam[u].len;
};
const int bL = calc(us[2 * N - (L + a)]);
const int bR = calc(us[R - a]);
// cerr<<" "<<string(S+(L+a),S+(R-a))<<", bL = "<<bL<<", bR = "<<bR<<endl;
const int b = max(bL, bR);
int way = 0;
if (b == bL) {
// reduce suffix
way += 1 + min(sa.lcp(L + a + b, R - a), a);
}
if (b == bR) {
// reduce prefix
way += 1 + min(sa.lcp(2 * N - (R - a - b), 2 * N - (L + a)), a);
}
printf("%d %d\n", (R - L) - 2 * a - b, way);
}
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 42748kb
input:
5 abcca 3 1 5 3 4 3 5
output:
1 1 0 0 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 42744kb
input:
5 babdb 2 1 4 3 4
output:
1 1 1 2
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 44804kb
input:
50 gqlggjglsqlgjflqflqfwfqqfqqffwfqlfwfqlwgsllsgwlqga 3262 26 32 22 28 10 17 9 28 39 47 14 18 18 35 15 31 22 49 15 21 15 23 12 45 1 49 3 13 18 24 14 23 19 26 21 27 1 46 17 34 23 32 13 26 15 43 39 46 17 28 40 49 14 44 3 37 4 15 20 39 1 17 1 17 1 17 17 34 1 17 1 17 1 17 17 34 1 17 17 34 17 34 1 17 17 ...
output:
2 1 0 0 7 2 13 1 1 1 4 2 17 2 14 1 21 1 6 2 4 1 28 2 35 3 10 2 5 1 5 1 2 2 2 1 38 1 1 2 5 3 11 1 26 2 0 0 5 2 4 2 27 1 34 2 10 1 17 1 16 2 16 2 16 2 1 2 16 2 16 2 16 2 1 2 16 2 1 2 1 2 16 2 1 2 16 2 1 2 1 2 16 2 16 2 1 2 16 2 16 2 16 2 16 2 1 2 1 2 1 2 1 2 16 2 1 2 1 2 16 2 1 2 1 2 16 2 1 2 16 2 1 2...
result:
ok 3262 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 45052kb
input:
95 fqoywgnlyjyzpyyyszsnsyzpzqldyqlyjdlnqsyzzqzzssszzqzzysqszjylqdlllldzqlyjzsnsyusqzzzsszzsszzzqso 8421 11 89 11 70 41 42 79 94 62 67 37 55 73 90 78 92 4 77 14 16 13 86 36 45 6 21 37 93 16 56 27 72 9 39 73 82 48 80 20 94 63 83 6 85 37 55 20 37 37 55 37 55 20 37 20 37 20 37 37 55 20 37 20 37 37 55 37...
output:
73 1 59 2 1 2 0 0 0 0 0 0 10 3 3 1 69 1 0 0 70 1 9 2 13 1 38 2 38 1 45 2 28 3 5 1 28 1 59 1 17 1 78 1 0 0 17 2 0 0 0 0 17 2 17 2 17 2 0 0 17 2 17 2 0 0 0 0 0 0 17 2 17 2 0 0 17 2 0 0 0 0 17 2 0 0 17 2 17 2 17 2 17 2 0 0 0 0 17 2 17 2 17 2 0 0 17 2 17 2 17 2 0 0 17 2 17 2 0 0 17 2 0 0 17 2 17 2 17 2 ...
result:
ok 8421 lines
Test #5:
score: 0
Accepted
time: 3ms
memory: 42848kb
input:
273 byqssdbrubbububbhsrssusdrbbdubbfqrfdsbsqshbbbdsruqfsdusbqbubbsrqssudhrquqrhduhhhbhubbubbsbhrfsfrdsduqbsrsssbdhfqusubhsbudbhubsbfbsbbbrsubbhhsqbudsdubqshhbbusrbbbsbfbsbuhbdubshbusuqfhdbsssrsbqudsdrfsfrhbsbbubbuhbbfbbrdsfrdsddsbbqrfdbubfuhbbbhsbuuddbrbhuhrffqrbbdbqdrqqbfudqs 8827 28 168 33 273 125...
output:
96 1 240 2 61 1 58 1 86 1 94 1 19 2 13 2 171 2 191 1 37 2 33 1 36 1 90 1 13 1 42 2 64 1 95 1 7 1 231 1 193 1 100 1 5 1 111 2 203 2 73 1 5 1 37 1 35 2 34 1 34 1 34 1 34 1 34 1 34 1 34 1 34 1 34 1 34 1 35 2 34 1 34 1 34 1 34 1 35 2 35 2 35 2 34 1 35 2 34 1 35 2 35 2 35 2 34 1 34 1 34 1 34 1 34 1 34 1 ...
result:
ok 8827 lines
Test #6:
score: 0
Accepted
time: 21ms
memory: 42944kb
input:
1630 gpdmjhvkfrxglffvjgghhtjujfrktintghhwunzwwufktxvuobnkajinjrkrubtrxfwvverhgkfcxkhpldpalxfwesrwnzjnjggvbtffgtagwmgrbrakjggedtjyhwkjclkyftdtlszfwdsjolwfjbwisftbfxumytlglgeaemklejwjytwhadqjwstzmqfzrfnyjmnhhkrmnsaabkgffggmazoemaznnwkrwjzajwgkftkhsbswmrytnnljynfkzjjwzrstlqdjwnfyawreltmeaeglkjtymafffgl...
output:
388 2 300 1 806 1 13 2 518 1 1079 2 570 2 759 2 440 2 701 1 0 0 6 1 1019 1 28 1 930 2 575 2 36 1 647 1 455 1 156 2 188 2 1151 1 252 2 1281 2 218 2 423 1 423 2 318 1 1053 2 366 2 754 1 1110 1 197 2 144 1 266 1 537 2 644 2 180 2 808 2 1274 1 133 1 271 1 1014 2 366 1 498 2 855 2 108 2 199 2 201 1 475 1...
result:
ok 64835 lines
Test #7:
score: 0
Accepted
time: 196ms
memory: 143868kb
input:
242681 nuvwtjlknjuypqzgbbkqljrojspjdoiesidzihlfiouurvgykdvvwyonssgajdkcobgyezfmetbjbrhiuveczngqjgbndmqwckapzuoborgyoixplzxpmptqpfdkokdpjuagixkjurccreyaaeyvpduutxqsmvtgtlfeugbvxmnmtfjxqnnvnkzcqacpwqsfjwlpfuemheleqlfzdqnrmvnnqifrtugyikhdlmwxtjalxexfdusvzqfecsyyrcnxrvgkjjkilvaqjiylbxlrfktnlxunnwjdftvxw...
output:
83044 1 37882 2 216157 2 48382 1 10896 2 176055 2 105310 2 155181 2 81628 1 18757 2 43985 1 18517 1 77084 1 60712 1 60844 1 3686 1 28003 1 16940 1 109452 1 227172 2 19371 1 74520 1 205350 2 9148 2 36108 2 56490 2 213082 2 36744 2 33340 1 64057 1 50728 2 4440 2 9544 2 38310 2 50945 2 7694 2 95347 1 9...
result:
ok 108152 lines
Test #8:
score: 0
Accepted
time: 94ms
memory: 158592kb
input:
180103 qwfrakvhsdleaugctbpvricopqgvnlrehvkpwerwmuxmcvievsfwckmdgferkwupuclsppcwkrrmkphflwsrobnphvfblplpqoriniddagiamlmbueympfijmexgjqodqpzzmxqvkvdturtgryppbojfhdiwmqllanylzqpmirzykccrwclylcejxejnnfmilusxgkouzikivzjgdmlsjtpogssfflroagwzrxxaroxernwhgknnlyoiuiplpkeagxqdsjfmabgmxfwjrdwalkydubsuilywjopqx...
output:
36 2 23992 2 62392 1 9269 1 34734 2 85369 2 20691 2 1030 1 83979 1 123117 2 89661 2 155084 2 10317 1 1934 1 12145 2 4175 2 47274 1 35439 1 96980 2 72256 1 25986 1 41548 1 818 2 11184 1 24031 2 45793 1 14250 2 89381 2 17294 1 84621 1 40414 2 55400 1 8323 2 25646 2 714 2 32042 1 58243 1 77992 1 18882 ...
result:
ok 37053 lines
Test #9:
score: 0
Accepted
time: 169ms
memory: 71832kb
input:
73372 mehadcsrhwawmxbxvvxifuynioutljndybapfdksfdeveztcckdskevoszwwnsgddzdtfwgkutzxnyfvxreojsuihgikqzevlcucghiwsfrgkzeqtsqirlpmmotugmcyfyvvuzupctonsrhjjyvzqqngeclnzrufmkfponiuqhccufaoeultlwnqkzwtvirzkznvjmpmhuhabjumdzbcwzqkednbftjezuhhpsdrjoixuodbnylovfouqosbhsloyzzvfmbemghgucwbzskhijtnkcxpwwudheiqya...
output:
1460 2 12675 1 40437 1 43220 1 8004 2 19049 1 28796 1 63645 2 39662 2 3277 2 16125 2 1570 1 11919 1 34196 1 9732 2 6417 2 17545 1 23590 2 47081 2 31666 2 7006 2 12116 1 42893 1 3318 1 55561 1 7436 1 5446 1 149 2 5348 2 16859 1 13004 1 22913 2 11114 1 4882 2 13019 1 3067 1 44996 1 9517 2 16829 2 2719...
result:
ok 224618 lines
Test #10:
score: 0
Accepted
time: 230ms
memory: 118696kb
input:
186088 bxwcogtrxvazjmagnlvigjzocjrleehmugtdsfwqfyqtgyvakswmwdulujtikjwawswnbmjpzhrsfnocciwuvhnnkekjkftskwokihunshpelsagdtwphczbdjzrjxhgygatpziuukhzjgqjjoalgrzmozauezjnbpljzqllkeognywybodbhfnjpksvwikpgcxpjrrjxhmhszlezdwouaeuxtgpupbhlmtwdjyrwuxgxzonmsunmryapxnuoicapisawessxbvdwrwqlafdabnsihkhlxgszuobj...
output:
18108 1 32696 2 30914 2 119897 2 31752 1 75298 2 78498 1 42110 2 143396 1 1132 2 163178 2 4096 2 948 1 56404 1 68376 1 10237 2 94467 1 101883 1 8666 1 151812 2 74144 2 66102 1 72213 2 4053 2 16411 1 27608 1 15003 2 176714 2 62891 2 78697 2 20178 2 94239 1 75452 2 2379 2 118246 2 4684 2 58526 1 51779...
result:
ok 172922 lines
Test #11:
score: 0
Accepted
time: 277ms
memory: 118952kb
input:
186410 ojchhvgbrjsztaoafyjhyfqggvmvjzwrtwnmogssbntvkvqhhtwzasnvndmqpchuvqqevtlobrornktvmemunbmyhvvjyhlcrvlwbqtvqgdpzlrdnclxcxkizmhxjxldaloqoitfndvkhnwfemqmvjlsjzuxhrofhhnmugqcreurwdbsqbuqnfcajnpdftlntmjfeviiaebjkcwxnszstwyjnhwegcltalytuksezobgotzonpibxrnajrxxcrcmhxacyxhghbmlbgeccfgetgorsokiutfnvbium...
output:
16856 1 71655 2 83151 1 2075 2 3199 1 90981 1 51907 1 20486 1 41939 1 4637 1 8199 2 61726 2 38456 1 56904 1 21357 1 33586 1 15873 2 40636 1 17730 1 83981 2 19237 2 39632 1 35226 1 9114 1 39309 1 67049 1 3720 2 82968 1 50575 2 34133 2 4566 2 15440 2 31468 2 7908 1 37504 1 76914 1 17951 1 5141 2 55150...
result:
ok 219919 lines
Test #12:
score: 0
Accepted
time: 92ms
memory: 176208kb
input:
219911 emslzelqkdqnfzzpqymsagwiidrlsycvfxfnayhtswbmguhobocnxgbifwqmtjdfvfqbjimptekcnuornjajduukeixeheuzncviysiijtlngtggedpcgdmdeakwwuxjvgccbhxqfzbtxitfqvuktfwfpduwozrbbsshrdnwfvqmsewgifgocchkxpylnpwqiqxgoiqdhrgxjwdgebmljhvreclzavaggsltebavidgvtwkbyzafxoyyxwnczpfdbasqcugbsfauaaqpwhgybnqtkywiutudrxwrk...
output:
1910 1 57927 2 0 0 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4758 1 4...
result:
ok 111910 lines
Test #13:
score: 0
Accepted
time: 213ms
memory: 52964kb
input:
27591 qoamkvpkhebzvrlmbrhtyobcauixphhughiosaymkjwgvzeleiihphqjljdyxwmauixecqirqvgdkggnrouvmsknplfyqzupozdogbjhlvtmhhipthoohtkuefvevjtonyaxkkvaydtckbfswhbowtwgoiwrmriodgzdzbbgzuvmcxsxhkkmrxbomuovbfrudedgcgpnthijskseiuswhsjqchnmxxaiyjmwluhlybvrhlsdejiqlqswbalxrslxsfmtzpshngxrudibpxqrisgveoyhczmydkxvym...
output:
2337 2 11280 1 2120 1 7631 1 15249 1 12389 1 2491 1 701 1 12413 2 4742 1 3119 1 3845 1 241 1 2242 1 2976 2 1942 1 17140 2 9309 2 319 1 2487 1 9295 1 7747 2 1566 2 343 1 2848 2 16762 2 1031 2 8117 2 1280 1 6269 2 3941 1 11367 1 678 1 5591 2 9710 1 4459 1 11616 1 2066 2 2380 1 4209 2 6821 1 6895 1 286...
result:
ok 246741 lines
Test #14:
score: 0
Accepted
time: 216ms
memory: 226100kb
input:
341125 bjqwhatbyjvcngipxliiyuijsjrjxwzthvhjchimmogzhyzzljdbbczxodxncpyynadfkjvjbbbsaixetwghtrkltyulbzpgjkaapbfiifelylfchmucgvqnzotpttltvvmykzqnsoecbjxauzebuveqfzkboboqagcispceyymhalospakelzhefprccpyjhwwwituaikrtdejyfpvxnmzpubeeddtiutlombedfkiqkytygyhejqmxzfuzhsnjqtakbcofgmfiemkmgzklqowgtaaqfmscgqypj...
output:
42658 2 24213 2 46758 2 40638 2 35799 2 21163 1 30618 1 79653 2 64601 2 37538 2 29919 1 72152 1 66691 2 27081 1 31116 1 304408 1 25602 1 60614 2 122304 1 101913 2 14577 1 51665 1 65739 1 33235 1 91654 1 60465 2 7624 2 110716 1 23286 2 19248 2 30402 1 136250 1 19871 1 51645 1 287756 2 23703 1 27572 2...
result:
ok 254470 lines
Test #15:
score: 0
Accepted
time: 211ms
memory: 178152kb
input:
230956 ickghckqwfctpfezebvddraiypwzfkwowntqjvzoggowxcsvdjfqyohfijsmarguyitysnqbxfqlqbedbezmshickgoeiqnonxobfakhlzkllytezozcnjcclrhuscvdyickhagzoszoioylpsaliembknmhsufbttnnxqskmjavhjdfcnjqjkgszavgpiothnhqxptqjptzplbefpbiqkbaqjnqqjsedcspqimscrnbqxvlerdjkgamyvzpcedkemfedghtbgcsshufuntyrqgjzdhlostohexdx...
output:
26052 1 71434 1 1169 2 38032 1 3940 2 97505 1 37638 2 98861 1 9927 2 72459 1 34568 1 59872 2 3180 1 43380 1 15059 1 87580 1 4370 1 10425 2 32180 2 24344 1 14788 2 70666 1 66862 2 10455 1 32939 1 66572 2 76295 1 16250 2 131590 2 54251 2 92669 2 32912 1 74600 1 90259 2 4324 1 105051 1 11870 1 67918 1 ...
result:
ok 270570 lines
Test #16:
score: 0
Accepted
time: 126ms
memory: 159312kb
input:
186071 aurostviurvtoiqoypigphfzrikzcgkmeaxyfcacrfgfjydrrvkdceqtytiltlmsbdrzladsefbgsvvrzlfabpdxkdooihngxhvfqonavyudmrebnmzueivszflrtjskbtxfgtjozblqizihgrqfmmlhyzfxwuqcdockhovkktwzlafxsppkbixemorifpukqynsdhnipgsasthpdwpdyomtuwqrxpcudgwaeipvkjootitghgtixekeobafapvunnipfohipbyygnfvinxtjjjxbczaeylzyxkrh...
output:
34423 1 12829 1 59438 2 35421 1 12255 1 100163 2 41577 2 6774 2 14807 2 104600 2 59322 2 54175 1 46155 1 18036 1 6280 2 10689 2 44895 2 36330 1 829 2 75255 2 14503 2 18365 1 10852 2 90978 1 124489 2 34974 2 54825 1 39876 1 11946 1 141883 2 3108 1 51119 2 120937 2 49211 2 1419 2 28253 1 29689 1 67478...
result:
ok 220760 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 42876kb
input:
883 uwxjjnxwxyycekwnxjswwvckkijydwykkyknzjxdinwjynwnwyxnkxjkjjkkxksknivknknkwnfwkjkvvekkjkwwjjjnkwxwjxkeejnxyevxzkxkycyekwzyxjjxywnwssxjvnsxjijkywvjsjnwvvknkjwnnjkkxkfvxwxxkxscsnikwwijjwxnwjswnwyzwwuxyykknjsskjkywvzsjkwusvxwwxuwkkkjwwvjjwsknsywxxkxwkxwwnxyjvkkwnksckxwwzvxjjwxknjsjkjkywfzsjkwusjxxkww...
output:
303 1 193 1 81 2 273 1 73 1 413 2 325 5 283 1 580 1 805 2 275 1 272 2 369 2 104 1 6 2 55 1 121 2 119 2 189 1 790 1 84 1 47 2 270 2 26 2 92 1 0 0 291 1 471 2 147 2 72 1 207 1 124 2 226 2 611 2 73 5 118 1 470 2 451 1 8 1 458 2 815 2 79 1 154 2 451 2 208 1 12 1 18 1 207 4 44 1 854 2 76 2 624 2 293 1 16...
result:
ok 982 lines
Test #18:
score: 0
Accepted
time: 418ms
memory: 281420kb
input:
472761 envwahmuzbjgpbfooqveovgpgcbaizookxzjbsvolqobhgqooppxqyogfkravafjbmpphmuhaspqzbveokgmvmtrvreydvzhnrobjhedpjmlimhhlxflunicljgdbflupeixutyijzgxbogqqmfsiuedrmiahzgrkoakxkizltpebontmiwodbcdgiyontejtuhddqtwwbqeumzlzxdhkxrwrviobkgqjzqxiyktgglrzzybxfzzyphawcgyxrtzofhjtsatadktznxndnpkbbpnjzbgbovpebpjh...
output:
42945 2 57333 2 33037 2 17593 1 3640 2 283278 1 235 1 145834 2 24727 1 62907 1 34843 1 8435 2 209632 2 111930 2 165564 1 27460 2 107039 1 57323 2 42421 1 66110 2 25508 2 50677 2 46223 2 224524 2 244787 2 52728 1 16379 1 12113 1 327854 1 154852 1 14554 2 107947 1 120597 1 29922 1 75243 2 67854 1 6966...
result:
ok 316350 lines
Test #19:
score: 0
Accepted
time: 144ms
memory: 45236kb
input:
7581 nhxypwhnsvffyndvpcyikdwvbojfjoklrglgfauutedxurmtbbvbmmfblzosjtgyjxgczcwknxvkmubwabdkbiekjgiislyyprxpuhzozaaxvomyfxvypwtkaxwlbimniknzddkluevaqojgewnnbiicykokqytknohbzcczgziwyzjhvqbwikoejuqwankwnzatneuvfifyzvfokjyifdjkpghjhtjoqyuvaznibylhsounbogylainkhujrwiwbyonhkykhonkuqnwjxaboukftykzjddwwoaxpbo...
output:
3512 1 2504 2 140 2 3722 1 1516 2 2471 1 4092 1 4304 1 597 2 448 1 1357 2 1789 2 4747 1 2260 2 20 2 2518 2 2628 2 6316 2 304 1 877 1 1804 1 0 0 6341 1 199 1 5509 1 1583 2 1918 2 3976 1 2679 1 5595 1 3104 2 3809 1 6466 1 6410 1 258 2 894 2 3365 2 1636 2 5163 2 80 2 215 1 2743 2 4962 2 3452 2 965 1 35...
result:
ok 393809 lines
Test #20:
score: 0
Accepted
time: 774ms
memory: 279888kb
input:
467766 mxuayezmqogeshfzwafkdxcltkyqtypxsnpvkxjwtomllsfhbxirmxrbmyyqmwdnkkmweutzdxvkmjuoaloiaopqpgvvydtqsvyovwukjhiwlxszkeohdlyjcdqrzickzoukctdoezzdaclzilbvkavparigpqiatjtkhnigsijkgdxiaudxmbrxpdeipsottlivhxsolknqfiaicdpaykilqhiswtmjsflihogbrjjabzhnsyoafmstrsgcxpgwrttmyhkozzmgaasjvdhuuchgamfmxlfbbcetl...
output:
172804 1 54153 1 70896 1 196364 1 36793 2 123989 2 88131 2 116327 2 82036 2 35156 1 58359 1 199524 2 152120 2 4471 2 26955 1 113717 1 43725 1 3478 1 76277 1 33067 2 153326 2 129770 1 60717 2 193455 1 17709 2 58766 1 87199 2 131308 1 48512 2 52995 2 215092 2 129085 2 213267 2 102490 2 116165 1 18889 ...
result:
ok 388654 lines
Test #21:
score: 0
Accepted
time: 237ms
memory: 287660kb
input:
490464 ltdcgjjalpmgvzoknpjnxypjmedcdmaicpgkwvbmocnssmhmgqfjerpalxhnkuizvpnjstnvukzutxipujwbodmgsxbtpgjngvcloguvrfbbhglbbyeczeytfaonjvpqutmbutcsrdvnknoeafrkewolovuzzjwytknjbjldmzjzgkxgvzaqhewmczglyrderennzatgxtazuijqgsfraiqzfbcnuuieclunezelsviekdgwquslfyhazwjbtwxohxemnpsunrbeehwilrspwijbspcchxgecwfmq...
output:
142827 2 22589 2 190886 2 90982 1 4054 2 71858 2 6821 2 52417 1 162855 1 21524 1 46855 2 200940 1 27630 1 200902 1 1373 1 156336 1 208478 1 197279 1 166654 1 29822 2 4359 2 103054 1 52243 1 148247 1 278767 1 399145 2 97331 1 1291 2 134796 2 156632 1 106598 1 7107 1 141123 2 133845 2 114029 2 70057 1...
result:
ok 269116 lines
Test #22:
score: 0
Accepted
time: 571ms
memory: 260728kb
input:
425242 vzsfinkepzcxiqiwutuqebzzixujmgesgipzyvpldkcsemypikjkofofdqkrqgwwdybjorhzdtdrjllsjvrovgrcvbcvwgwnbatlocohpxeithfsxsuuzjuxlpxwmprcixrirqeuwukadsmbttgewbfxancxpcfnpqwtclblzayuxtodaqzrnsffyjshhllcrcuwuhizyfsbiyxevgnswoluhmrzsyuetyqyyrfhwhomzdviizvfpvdjslankliasgoczaynnigvdenubndrzrnwafdmsutpaiagj...
output:
63325 1 196071 1 24390 1 213585 2 71814 1 12851 1 104957 1 20309 1 39446 1 167041 1 37453 2 252872 1 17358 2 24770 1 231991 1 53193 1 156609 2 4639 1 69098 1 273174 1 85829 1 126147 1 19273 2 77581 2 14335 1 160418 1 28264 1 10924 1 132290 1 107880 1 47783 1 60076 1 1261 2 128806 1 167946 1 132126 1...
result:
ok 303077 lines
Test #23:
score: 0
Accepted
time: 251ms
memory: 273160kb
input:
454707 vwbyukoygoqqrigcfszkipbdbzjzyttdzskqtqlcpbgthriyjeossefveqawvtqmxafdtcfsmzencamtbzgpvuaiomnytsldtnmqyiyapzjyqwsmikkdzdwabupkoemlmufpukkqludgltwfmguyaxlhxqsgzafkplcsdrrzuvokwlcafaqcxrwoqekrquvltxhmurnjubdpxwqiestyuxfzczmcfwgswepvnobukiqgccvdtsjwzryaszihgrnontqxrkvpcrnrraqnsfycttlmgqasqxzomgwrg...
output:
128697 1 122598 2 254911 1 20413 2 62351 1 197560 3 55270 1 118182 2 51929 2 275074 2 3345 1 121324 2 19046 2 10571 1 143485 1 178154 2 40683 1 102973 1 110924 1 49711 1 113492 2 24565 2 179580 1 57191 1 50743 2 30440 1 191559 2 238898 2 96727 1 3338 2 81109 2 146811 1 92114 2 31328 2 137044 1 37068...
result:
ok 319866 lines
Test #24:
score: 0
Accepted
time: 271ms
memory: 262316kb
input:
428928 vzgfzwrlobbigranxhmtgswspagsapxvebdexhntjvoltdjafhhcgkobvrxtsyrjnjmbtwpaqtbwxmqjicohrcxxxwoguggqowvmzrssafyyxqfgkslldcztzzpqjzqnxyqedqxqnnaxrbedchyciebnzudpypnfrfvzvhwrktucmtduopyhaglqevkphglkasbtgfbbdqjgxdplijajihtuttfukbbjirumyyuxnitwyjilyrelfrbducmaugzrgkewxcwktzcsrnkjulkbaondlaxibbleivowg...
output:
118116 2 303426 1 158523 1 5363 2 96434 2 108531 2 57265 2 78273 1 39897 2 52883 2 196420 2 167452 2 159055 1 178369 2 68989 1 0 0 38920 2 72320 3 133357 1 50610 2 126369 1 22656 3 319666 2 70959 2 50519 2 2753 2 90361 1 103184 2 139908 1 191361 2 3929 1 45672 1 39900 2 36241 2 103404 2 39655 1 7987...
result:
ok 373485 lines
Test #25:
score: 0
Accepted
time: 575ms
memory: 175572kb
input:
314262 mbdjwwfvzqaspeoiexlqxmrlyuoolnnkidvdglszjlgzolwbdnhubckcvsztafntbjxswxmvmrvtxpaperptfcntgvbjtyakjxvyaoqiamxizuwqorsgdprxrseresikqbjlsyrnomnrnojekvidktavpiraattgcfsmlzcffbnmzjyvyziodlifsgnlrzlkkcwunfgfwuvpjqrpcqqjagrxbglfguhsnprjxeuushsefcbybntjprjttvfroeqiutqtnwgcvqldllccqufjevxnplevqmegozcxw...
output:
154418 2 16960 1 103408 2 77635 1 201145 1 148788 2 13123 1 171110 1 115337 2 146478 1 25566 2 26141 1 3881 1 31902 1 213972 1 25530 2 125052 1 65575 2 126216 2 142989 1 178707 2 290957 2 64379 1 215579 1 2987 1 109457 2 6756 2 79774 2 60621 2 129094 2 149523 1 57649 1 2200 2 132753 1 58773 2 38075 ...
result:
ok 372975 lines
Test #26:
score: 0
Accepted
time: 736ms
memory: 281288kb
input:
473345 yssaokzadzdzwpxlvavmrsuuwhovysvtcwhabnurlbpavlhpmzxdfbuavqykcpdkbawwnuhoadbektfvjfsdxmeiabdbicqabwsrdcxrwonsitbugmmgomhyrhtidxxqssqgxnfyvowfpzdmnshsilbeucnrgwlymndpbcvuprpteagixtfdlkwdqzydhnisvhsftcbagzxksdoizbzlisqrsrblxxcqraxdboiuoahjsvvqnavubfsmtvnctnfyilvbwuyuycntboikpynyfqyltslpyrqkufpdy...
output:
26045 2 92986 2 131091 2 98180 1 169157 2 169756 1 291875 1 176714 2 8839 2 173234 1 156976 2 5856 1 225621 2 54482 1 55314 1 260577 1 264562 1 267898 1 46760 2 79964 1 169773 1 160589 2 240762 2 48240 2 52291 2 248942 2 71062 2 170830 2 38396 1 206871 2 62246 1 230237 2 250690 1 107169 1 97001 1 21...
result:
ok 382491 lines
Test #27:
score: 0
Accepted
time: 296ms
memory: 278996kb
input:
466710 dwginluwtgjslxqrozdqemoxtlujcqzptsweddoefrtfmnnyhtvllwgzgfdskoztqirvqlcbaiynfvpwgpnnyyjvfcbjbyaphyxhuxkyobnhefulkudwlqexrjokdihkezvwleapgmitgcdlvfzacwofjgyhvgijhgpcviqcqzjxhweydxcxsbkljylktfvthsrhyyboomrotqrmdxexhbkwcvqwffemtipafzcxwycstjbijbptvkxufqjfyweptlfboctrgbolfogwvqghixsnucmhsjinlpcif...
output:
139129 1 320780 2 50556 1 168598 1 221315 2 260545 2 299464 2 43913 1 241072 1 50187 1 2843 2 5810 1 286808 1 106766 1 28411 1 52637 1 207829 1 52713 1 19630 1 4863 2 49190 1 126306 1 128787 1 179698 1 138097 2 81942 1 69844 2 7513 1 7117 1 433683 2 51537 1 75520 2 90833 1 234279 2 67468 1 124997 1 ...
result:
ok 355378 lines
Test #28:
score: 0
Accepted
time: 220ms
memory: 43128kb
input:
2872 hahahahahahahaaaahhhaahhhhaahaahahhahahhaahhhhhhhhhhhahhahahaaaaahahahhahhaahhaaaaahhhhahahhahhahahahaahaahhhahahhhahaahhhahaaahhhhhahahhaahhhahhaaahhhahahhahahahhahhahahhhhhahahhhahhhhhhaahhahhhhahhhaahahhhahhhhhahhaahaaahhhhhhhhhaaahhhahhhahaahhaaahaahhahhaaahahaaahahaaahhhahhhhhhaahhhhahhhha...
output:
95 1 1697 1 291 1 240 1 224 6 766 1 2 1 1861 5 771 1 859 2 855 1 1177 2 623 1 196 2 1113 2 444 2 14 1 409 5 516 1 2433 1 138 2 561 2 1784 1 252 1 964 1 333 1 389 1 1846 2 1934 3 76 1 971 1 438 3 1761 2 911 1 165 1 433 3 647 1 733 2 66 1 2447 1 582 1 117 2 866 1 1581 1 417 1 592 1 1196 1 634 1 1276 1...
result:
ok 350131 lines
Test #29:
score: 0
Accepted
time: 241ms
memory: 46260kb
input:
4757 zyzyzyzyzyzyzyzyzyzyzyzyzyzyzyzyzyzyzyzyzyyyzzzyzzyyzyzzzyzzzzyyzyzyzzzzyyzyzyzyzyzyyzzyzyzyzzyzyyzyzyzzyzzyzyzyzyzyyyyzzyzyzyzyzzzyyyyzzyzzyyyzzyzzzzzyzyyzyyzyzzzyzyzzyzzzyyyyzzyyyzyyyyyyzyyyzzzzzyzyzzyyzzzyzyzyyzyzzyyyzzyzyzzzyzyyzyzzzyyzzzyyyyzyzyyyyyyyyzzyzzzyzzzzzyyzzyzzyzzzzyzyzzzyyyzyyyy...
output:
1831 1 3162 2 975 1 594 1 1588 1 2359 1 1134 1 0 0 30 3 2470 3 1047 1 4111 1 398 3 688 2 1984 2 1353 1 2070 2 1211 1 1586 1 525 1 1223 2 773 1 180 2 49 4 1180 2 498 1 384 5 4287 2 313 1 151 1 1 1 1340 2 642 1 388 7 894 1 1845 1 505 4 2686 1 78 2 1032 2 0 0 273 2 1402 2 253 1 378 1 308 1 2230 2 273 1...
result:
ok 379636 lines
Test #30:
score: 0
Accepted
time: 284ms
memory: 47244kb
input:
7581 nhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnnhhnhnhhhnhhhnnhnnnnhnnnnnnnhnhnhnnhhhhhhnhnnnnnhhhhhnnnnhhnhhnnnnhhhhnnhhhnnhhnhhhnnnnnhnhnnhhhhhnnnnhhhhnnnnnhnnnhnnhnnnhhnnnnhnnhhhnnhnhhnnhhhhhhhnhnhhhhhhnhnhhhhnnhnnnnhnhnhhnhnnnnhhnnnnnnnhnhnnnnnhnhnnhnhnnnhhhhnhnnnhnnhnnhnnnhnn...
output:
6495 2 1340 1 1169 2 1780 5 5972 1 3712 2 1082 1 149 1 2392 1 1001 3 95 2 2201 3 79 5 732 1 1234 1 608 2 849 3 1628 2 3014 2 977 1 2198 3 1859 1 1224 2 1185 1 2431 1 1472 1 2509 1 2878 1 573 2 287 3 467 3 926 1 5441 2 5216 1 3133 1 885 2 527 1 1218 1 2965 1 85 2 562 2 908 2 4325 1 5380 1 6463 3 767 ...
result:
ok 393809 lines
Test #31:
score: 0
Accepted
time: 405ms
memory: 77052kb
input:
85669 kakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakakaka...
output:
20535 1 19105 5 55139 1 6481 2 1895 1 16337 1 11263 6 8777 2 19422 1 2511 2 31189 3 38864 1 14580 3 9373 5 21583 1 1771 1 1860 1 6374 1 8148 2 28259 1 16758 2 7574 1 33 2 12236 1 7942 1 44077 8 7278 4 27231 2 16719 7 15133 1 929 1 1327 1 75214 1 11131 2 11824 1 6196 1 3012 1 36032 3 403 1 64015 2 38...
result:
ok 386442 lines
Test #32:
score: 0
Accepted
time: 789ms
memory: 280868kb
input:
467766 mxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxm...
output:
88624 1 68899 1 99970 1 4509 1 104737 1 94922 2 228678 2 72099 2 179105 2 46773 1 233751 2 63799 1 148929 4 23755 2 84195 1 32691 5 38650 7 36139 4 37167 1 98245 3 1395 1 63589 3 53793 1 94090 1 100458 1 48951 1 95325 2 226595 2 1592 1 141733 1 162326 4 59236 1 142415 3 212166 1 214788 2 32652 1 406...
result:
ok 388654 lines
Test #33:
score: 0
Accepted
time: 807ms
memory: 273640kb
input:
450567 hyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhhhyhyhyhhyyhyhhhyhhyhhyhyhhhyhhhyyyyyyyhyyyhhhyhyhhhhhyyhhyyyhhyyyyhyhyyhhyhyhhhhhyhyhyhyyhyyhhhhyyhyhhhhhyhyyyhyyyhyhyhyhhhhhyyyyyyyhhhhyyhyyyhyyhh...
output:
302958 4 97887 1 127813 3 349731 1 106088 1 75378 4 21284 1 121929 1 10130 2 48360 1 174006 2 50549 1 31560 1 66023 1 21149 3 169644 1 88434 1 169395 3 134729 4 44873 3 325361 1 19140 1 45870 2 32067 2 241152 3 61742 1 241947 1 184679 4 91347 1 152526 1 79672 1 104727 2 109516 2 32589 3 7264 1 11703...
result:
ok 370071 lines
Test #34:
score: 0
Accepted
time: 676ms
memory: 278628kb
input:
461960 jljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljljlj...
output:
287122 1 163230 3 19723 1 27559 5 62982 1 65519 1 78361 1 123221 1 161099 2 25551 1 164906 1 385812 1 19084 1 34177 1 4442 1 103644 4 210038 1 174290 3 26924 1 353410 1 227084 2 65224 1 327957 2 146285 1 48927 1 73154 1 114518 1 8384 1 174287 1 60060 2 150394 3 86736 1 87524 2 244212 1 29715 2 71969...
result:
ok 337620 lines
Test #35:
score: 0
Accepted
time: 934ms
memory: 291672kb
input:
493783 cycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycycyyycycycccycycccycycycycccycycyccyycyyycycccyccycyycccccycycycycycyyycyyycycycycccccycycycycycyyyccyyyycccycycycycyccyycycyyycycycyyyyyyyycy...
output:
128958 1 156145 1 213180 2 158382 1 48447 2 41664 1 242677 1 301386 1 7713 1 129486 2 63871 4 169260 1 180052 2 159428 1 36482 1 246069 3 196037 3 46331 3 252091 3 209772 1 222837 2 148441 2 324660 1 20588 8 304283 2 11720 2 174830 2 195118 1 178272 1 248569 1 129640 1 165936 2 139075 1 135828 1 249...
result:
ok 393100 lines
Test #36:
score: 0
Accepted
time: 594ms
memory: 289716kb
input:
490464 ltltltltltltltltltltltltltltltltltltltltltltltltltltltltltltltltltltltltltlltltttlttltltltltttltlllltlltttllltltltltllltllttlltlllltltltltltttltllltttltltlllllttttttltltltltlttllltltltltltltttltltltltltltltltllltltltltttltltltlttlllltltlttlllttttltttltltltltttltltltltllttttltltltltltltltltttl...
output:
17548 1 116890 3 385602 1 345670 2 33425 1 92526 1 119395 1 232165 1 149810 4 183022 1 129199 2 342393 2 151044 6 175603 2 49376 1 133004 1 72635 3 155059 3 215433 1 286654 3 125654 4 408193 1 454073 1 295591 3 304190 2 236094 1 60719 1 29490 1 282931 1 88562 2 88360 2 227458 2 91466 1 455609 1 3519...
result:
ok 269116 lines
Test #37:
score: 0
Accepted
time: 703ms
memory: 274396kb
input:
454707 vwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwvwv...
output:
47810 1 12653 1 302693 1 160385 1 1234 1 310372 1 259678 1 42119 3 163219 1 19776 1 358317 1 236581 1 68051 3 320587 1 254829 2 124480 1 111143 3 157130 1 70799 1 242816 1 198952 1 18363 1 117936 1 11187 1 36209 1 23923 2 168100 1 227405 2 74272 1 30095 1 72129 1 15742 1 57879 3 1742 5 128447 2 4168...
result:
ok 319866 lines
Test #38:
score: 0
Accepted
time: 528ms
memory: 176788kb
input:
225793 bqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbqbbbqbbbbbqqbqqqqqqbqbqbqbbqbbqbqbqbqbbbqbbbqbqbbbqbqbbbqbqqqbqqbbqqqbqbqqqqqbqqqbqbqbbqqbqbqbqbqbqqqbqqqbbbqqqqbbbbqbqbqqqqqbqqqbqbqbqbbbqqqbqqqbbqqbqbqbqbbbqqqbqbqbbbqqqqqqqbqbqqqbqbbbqbqbqbbbbbqqqbqbqb...
output:
28426 3 70215 1 897 2 71507 1 9085 1 54948 1 5607 2 47856 2 56916 2 35019 1 15386 1 132056 1 57047 1 46334 1 42943 2 109717 1 25530 4 16670 1 9809 1 26325 2 147477 3 13802 1 63226 7 32984 1 49195 2 46491 2 36956 6 12770 1 53868 1 21935 2 43645 1 117480 2 89195 1 80398 3 1866 2 28153 3 150129 1 17172...
result:
ok 373671 lines
Test #39:
score: 0
Accepted
time: 1144ms
memory: 280960kb
input:
467766 rlnhpbwjlywapfaasbaoszkozanjrsandukghcrykhkqdkhbselyricojkfzklkkzlkxuxuzhbqcwufbixdqnznhfafegxzuaekgrabikukzjtazpidchjpvmflmkiemadaxkmjdjpekzvwjqdkwawryazicokzzzbbdpcehbpprezhofuzqvqdkkrmjkkdztayrwjgpkcuyeaylmyyzlabcxcyvuvrgafybbkbhnyokmduubbabauwxolzqzkaaytkfqojbnlziezcykkhbcfwhgbboegtcpixqc...
output:
357 1 240 1 602 1 86 1 137 1 465 1 232 1 427 1 101 1 418 1 414 1 427 1 133 1 253 1 579 1 579 1 121 1 483 1 614 1 123 1 219 1 377 1 499 1 303 2 177 1 209 1 588 1 128 1 424 1 558 1 303 1 103 1 608 1 446 1 337 1 464 1 342 1 69 1 567 1 366 1 21 1 558 1 365 1 294 1 510 1 67 1 60 1 127 1 351 1 601 1 468 1...
result:
ok 388654 lines
Test #40:
score: 0
Accepted
time: 1124ms
memory: 273868kb
input:
450567 oopiyxxvkcjzazlcdsyajkbiycnzahgyeygafdknmkkixdsfyuzndzrgccdoccwaxjnpbyrbhynjxlqzjgrghupgkfbtzxfovmyansuvndugmetvazcafsbayuyjrkwtvauzkixkyespychhtiwksimfknqgbzbvkbreyguknpaafdzpvbyezophrtkxbawqcwbksxbippabepgjbkxumqobaqknxqmqbcplbdnzafrgneoidskzyardohfulyuvbrchvnvybwnowvzgbapwvvatcsyihtnayknkb...
output:
314 1 17 1 7 1 287 1 322 1 254 1 154 2 151 1 66 1 158 1 393 1 66 1 135 1 374 1 140 1 17 1 172 1 77 1 2 1 195 2 16 1 217 1 107 1 49 1 232 1 344 2 60 1 339 1 366 1 120 1 404 2 351 1 148 1 345 1 139 1 315 1 14 1 304 1 55 1 204 1 196 1 226 1 111 1 328 1 77 1 379 1 278 1 186 1 396 1 375 1 185 1 229 1 132...
result:
ok 370071 lines
Test #41:
score: 0
Accepted
time: 1007ms
memory: 278588kb
input:
461960 daaavyrgmdokkybatocvzlufnzswcwrchvaxzpjibaclehygywaxdakcbamywqhksrjhkzzeakkwhwlhaaajwkqorzcnbjrnlloyaealylkabqegvltmxuflkthfeyfnbijokmjfhykblzhufjijmhdgmykkmiskbyzyqsvleavkbhmykymbzbwgyfzyobevyqvxeqbyyipkxnydirftagybguzclalvzzzwxayybrlbskmamwkdbaaollzkipsyxvvgyasamcmvazwqmdbznaodlrakkvfkaagvq...
output:
432 1 243 1 125 1 86 1 364 1 153 1 446 1 105 1 463 1 108 1 299 1 294 1 265 1 207 1 142 1 204 1 423 1 51 1 446 1 83 1 229 1 69 1 447 1 256 1 299 2 226 1 344 1 117 1 430 1 381 1 297 1 99 1 261 1 295 1 245 1 365 1 317 1 386 1 363 1 385 1 422 1 328 2 268 1 95 1 403 1 203 1 252 1 413 1 283 1 441 1 243 1 ...
result:
ok 337620 lines
Test #42:
score: 0
Accepted
time: 1200ms
memory: 292140kb
input:
493783 ovivpzoedyyjkwrbvkrtiiwkozfzztpprgtwikrzsiefvtbwizyjytrbaakufuaosztydoesxxmaqiblagaexysgjsztwyunmstfrrxibbjhehyzqetkkzkypkxtzcbbprbctbklydyrckrkfxeeeknpbtnvhoefyzoqyyzawvmtsqysozubwubdkwzacjhuxgrpsznwptazayicaacbvgdbhkihdqntslxqtowtayxvkoazqjqokqsvbayetpyancqjwmlwgbubsymqaxuhrpatcmgzppataltmh...
output:
398 2 418 1 80 1 77 1 213 1 318 1 170 1 385 1 363 1 100 1 42 1 281 1 455 1 318 1 64 1 315 1 458 1 113 1 339 1 403 1 287 1 67 1 120 1 22 1 225 1 158 1 278 1 425 2 384 1 247 1 244 1 359 1 69 1 42 1 371 1 184 1 196 1 79 2 31 3 354 1 62 1 337 1 228 2 2 1 445 1 64 1 164 1 428 1 417 1 10 1 16 1 191 1 316 ...
result:
ok 393100 lines
Test #43:
score: 0
Accepted
time: 1043ms
memory: 268044kb
input:
436409 xkabeithdpbcihaxracbaweybahlkrbpjcbwbkuwtjrcualbouzgsckgzazyflxhmkgauawkvsmawojbwpbafnakbaehptatbzwbuaflyafmsccsduygixbyxokvbwtkkgeeooujkdbdugabvncbkhdalecbkufadaeyybkxhgwynsytjhavgkwdxjyykyuyfygdsjyekikzhavhdubkrbnwicpnzdskwmtamrzboknbwszibkbbekboqkljurhryyvcfofrmnezamzrdxkchkkkiitvaxxlikubx...
output:
307 1 79 1 217 1 36 1 356 1 139 2 46 1 151 1 240 1 240 1 96 1 20 1 98 1 157 1 324 1 72 1 31 1 56 1 228 1 202 1 275 1 366 1 392 1 390 1 272 1 83 1 161 1 244 1 219 1 231 1 232 1 303 1 373 1 247 1 217 1 118 1 141 1 349 1 47 1 49 1 0 0 23 1 405 1 139 1 152 1 403 1 313 1 59 1 313 1 282 1 129 1 376 1 249 ...
result:
ok 355325 lines
Test #44:
score: 0
Accepted
time: 820ms
memory: 290908kb
input:
490464 kzyqauaymvyotgfesamhymskzbbvsqikkravgiavcekkenbkmqaniyheyybqlkmydvvjtdbykbmkbjsuqpwnqldbwzdssstpcxpwhgubsirmcakkapmofahvvodsznkezyalzzktfghhmkykqaynpnxtrzqpbiyjwczamdzjumzjojbbpwwujfytkrhatkdhwcktyyqqececobgoyywguohizvckiblfenowywjklbknxylhgkejahlnnndbqglgarydkbqedpxknxcnzgdivybvmxkqyxmkbbyja...
output:
280 2 282 1 33 1 243 1 243 1 99 1 113 1 168 1 103 1 240 1 174 1 318 1 62 1 366 1 202 1 152 1 213 1 253 1 67 1 161 1 357 1 366 1 85 1 162 1 154 1 202 2 153 1 308 1 19 1 208 1 199 1 175 1 153 1 20 1 259 1 175 1 138 1 38 1 154 1 84 1 16 1 29 1 233 1 61 1 98 1 144 1 23 1 92 1 245 1 282 1 317 2 23 1 96 1...
result:
ok 269116 lines
Test #45:
score: 0
Accepted
time: 621ms
memory: 286104kb
input:
479116 wiqvdcqkezvxqihvwbodnwgjqkcaljhysgyyyzfbsfhozwxxbrdwfxlblpybvqvgqjzevhynbypsfumtjcdyivbzdiqxlawzvxrcfmrpbhxrwiakyrsbkakpadthqjkmkmwuqauafxzczjvaarcmazustduyrzyueymdklqmlqhitzolghxyyexgbgulrhirbvqwsbsyzxhqdhksujmjvqrfacyjeacbkkamuhldjbadyigawgkfyjzhxlbtyrdolsxipnttarpvzpqsegqtotazbbqeobbzsnrok...
output:
106 2 20 1 157 2 341 1 276 1 271 1 348 1 157 1 38 1 146 1 12 1 252 1 19 1 126 1 335 2 349 1 85 2 281 1 23 1 194 1 18 1 240 1 31 1 146 1 13 1 153 1 179 1 229 1 214 1 307 1 243 1 243 1 226 1 298 1 95 1 186 1 335 1 189 1 197 1 78 1 54 1 176 1 67 1 96 1 168 1 19 1 79 1 281 1 236 1 77 1 351 1 191 1 114 1...
result:
ok 191647 lines
Test #46:
score: 0
Accepted
time: 1187ms
memory: 294008kb
input:
497017 bnovpukiikrazkdyubolyaqiztoyiceahfkcvezymaqemkiarknusseycmgraabcyorbpbfbeyxacbxxayayqblxtfbbexnbbiibikhdjfcykbrqabyrrjvdnblyzbciybyxaarjqpvnybdxanfzncitocclakcobazzrmqbwkcwkbuakvbxabekqmybnkkttkknbymqkebaxbvkaubkwckwbqmrzzabockalccoticnzfnaxdbynvpqjraaxybyicbzylbndvjrrybaqrbkycfjdhkibiibbnxeb...
output:
49 2 147 1 158 1 52 1 11 1 77 1 143 1 49 1 107 1 90 1 79 1 100 1 58 1 96 1 67 1 96 1 66 1 156 1 167 1 43 1 117 1 44 1 55 1 161 1 185 1 98 1 113 1 152 1 32 1 52 1 109 1 117 1 115 1 7 1 5 1 71 1 85 1 149 1 117 1 47 1 12 1 188 1 99 1 56 1 47 1 153 1 59 1 162 1 33 1 128 1 116 1 45 1 132 1 132 1 91 1 28 ...
result:
ok 398270 lines
Test #47:
score: 0
Accepted
time: 1059ms
memory: 264196kb
input:
428928 egaqxqxzkablqpcjexywkrpbprvuhtpukhkqvkeyhtsoeaxndrjlsjkgjabpicbuzuzqbyoqykmudrnqmzguicabihrbrirbfkyycthknnzgaendlmdiuvfcmbbtrcbvkeztrwxgflvgfwimtkoxebmokwzjyleuyimlnkycjuwdgzicxlznzfktzuwmpaaxakwbhqndeekoyffpoqldhnmqjklcmdedpvlqkjpzfizxjvnxixkqbcsayencsdtpvelzeljznmfoxwdpucktwagaotxodznkkyuks...
output:
1 1 87 1 36 1 247 1 163 1 200 1 264 1 228 1 83 1 34 2 143 1 52 1 97 1 158 1 88 1 127 1 229 1 238 1 323 1 45 1 328 1 157 1 198 1 120 1 254 1 208 1 265 1 237 1 151 1 140 1 126 1 173 1 176 1 63 1 86 2 140 1 248 2 338 1 65 1 342 1 318 1 190 1 137 1 151 1 272 1 106 1 282 1 194 1 95 1 196 1 135 1 159 1 88...
result:
ok 373485 lines
Test #48:
score: 0
Accepted
time: 1120ms
memory: 292584kb
input:
496121 ukyhzlkuxbfewvyojdexruirflzcyojxyiyzazbnqqamkxjxzhqglacfoxajrhaqazynzssznyzaqahrjaxofcalgqhzxjxkmaqqnbzazyiyxjoyczlfriurxedjoyvwefbxuklzhykuukyhzlkuxbfewvyojdexruirflzcyojxyiyzazbnqqamkxjxzhqglacfoxajrhaqazynzssznyzaqahrjaxofcalgqhzxjxkmaqqnbzazyiyxjoyczlfriurxedjoyvwefbxuklzhykuukyhzlkuxbfew...
output:
27 2 42 1 16 1 39 1 43 1 62 1 60 1 46 1 34 1 59 1 32 1 11 1 18 1 15 1 58 1 16 1 48 1 15 1 40 1 43 1 69 1 0 0 69 1 30 1 69 1 69 1 56 1 29 1 25 1 5 1 8 1 14 1 53 1 20 1 59 1 0 0 51 1 39 1 2 1 54 1 61 1 69 1 10 1 38 1 32 1 44 1 42 1 26 2 22 1 55 1 66 1 52 1 30 1 12 1 63 1 19 1 44 1 20 1 15 1 22 1 13 1 ...
result:
ok 371154 lines
Test #49:
score: 0
Accepted
time: 126ms
memory: 282624kb
input:
474987 jwnjmvfuxldgdpywzdrheociakvdxfvjmmwyuoiveblxurzrqvetqidgjsnrthwunoapjsusmxtaueljoigheszqsitpisdvmrktmmeqpavnwlnmczxabgphadghhudazcrfnmdokdgavetopuabyypedweoytzsjfltzzucilwmgstxzfmaovakkkkhanagibtqvwzhsdvpqipxtxjgfctmcstjurgjunmltrdwrxcllxjslcofceqgqbunuskqynrhrrhaxpzqeknqfqolqyyrzpqxgrznkqajl...
output:
175157 1 190919 1 225612 1 94989 2 26227 2 89225 2 405926 1 38145 2 119572 1 34388 1 74688 2 356074 1 179262 2 101110 2 0 0 58512 1 174856 1 47974 2 42055 2 245418 2 68369 1 253045 1 53299 1 109144 1 1176 2 167400 1 99944 1 222341 1
result:
ok 28 lines
Extra Test:
score: 0
Extra Test Passed