#pragma GCC optimize("O3","unroll-loops","rename-registers")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define JUDGE 1
// 1006e6 v3 (lane e_variant_lane): SA + LCP for a uniformly-random lowercase string.
// stage 1 build u64 records [key30(c0..c5, 5 bits each) | idx20] (BMI2 pext, no gathers)
// stage 2 3 LSD radix passes, 10 bits each, 1024 buckets (L1 counters)
// stage 3 one walk: emit SA digits, derive LCP from packed-key xor (clz), refine equal-key runs
// stage 4 emit the LCP line (byte array -> digits)
// Fallback to SA-IS when a 6-char-key run exceeds RUNMAX (non-random data).
#include <cstdint>
#include <cstring>
#include <immintrin.h>
#ifndef OB_LCPB
#define OB_LCPB 1
#endif
#ifndef OB_STR
#define OB_STR 1
#endif
#define MAXN 1000005
#define PADB 64
__attribute__((aligned(4096))) static unsigned char str_BSS[MAXN + PADB];
static unsigned char *strp = str_BSS;
#define str strp
__attribute__((aligned(4096))) static uint64_t RA[MAXN];
__attribute__((aligned(4096))) static uint64_t RB_BSS[MAXN];
static uint64_t *RBp = RB_BSS;
#define RB RBp
__attribute__((aligned(4096))) static uint32_t CNT[1024];
__attribute__((aligned(4096))) static uint32_t CNT2[1024];
/* e6k5_rv: the LSD's two digit counters in 16 bits (4 KB -> 2 KB each).
Only the per-bucket radix uses these; the MSD pass keeps the 32-bit CNT
because its counts reach n. */
__attribute__((aligned(4096))) static uint16_t LCNT[1024];
__attribute__((aligned(4096))) static uint16_t LCNT2[1024];
/* m29: MSD bucket extractor. key_at(i)>>20 is EXACTLY ((str[i]&31)<<5)|(str[i+1]&31)
-- the pext mask takes the low 5 bits of each byte, bswap puts str[i] topmost, and
>>10 drops the last two characters -- so the bucket depends on TWO BYTES ONLY and a
single 16-bit-indexed table returns it in one load instead of load+bswap+pext(3)+shr.
The table is built for ALL 65536 byte pairs, so it is exact for any input, not just
lowercase. */
/* m29: only bits 0-4 and 8-12 of the 16-bit load can affect the bucket, so masking the
index with 0x1F1F keeps the lookup at TWO uops (and + load) while shrinking the table
from 128 KB / 65536 entries to 16 KB / 7968 and the build from 65536 to 7968 iterations. */
__attribute__((aligned(4096))) static uint16_t TAB16[7968];
__attribute__((aligned(4096))) static uint32_t RK[MAXN];
__attribute__((aligned(4096))) static uint32_t START[1025];
#define SCRSZ 65536
__attribute__((aligned(4096))) static uint64_t SCR[SCRSZ];
/* m29: LCPB kept as its own 4096-aligned object but shifted 1024 bytes, so its address
phase relative to RB and the output is 1024 mod 4096 instead of 0. The walk runs three
concurrent sequential streams (RB read, LCPB write, output write) and M26 measured that
this phase is what separates a THIN tail from a FAT one on this row. The rig is blind
to it, so it can only be boarded. */
__attribute__((aligned(4096))) static unsigned char LCPB_BSS[MAXN + 8 + 4096];
static unsigned char *LCPBp = LCPB_BSS + 1024;
#define LCPB LCPBp
__attribute__((aligned(4096))) static uint32_t D4[10000];
static unsigned char L10[64];
/* LANE l1006e6b: (clz(x)-2)/5 is a multiply-high chain ON the critical path of the four
LCPB byte stores in the walk. clz(x) for a non-zero 30-bit key is 2..31, so the quotient
is a 32-entry table. Judge-priced: -4.83 % of the whole run. */
static const unsigned char D5B[64] = {0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6};
static unsigned char CLA[64];
static uint64_t PAIR[256];
static const unsigned PW[12] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000u, 0};
/* AVX2 exclusive prefix sum over 1024 uint32 counters. The scalar form was a
serial `s += c` chain of 1024 dependent adds AND 1024 single-word stores, i.e.
~1024 cycles per call, and it is called 2x per non-empty bucket (~676 of them).
acc - original recovers the exclusive prefix exactly, so no extra shuffle is
needed; only two vpermd (broadcast of lane 3 and lane 7) remain. */
static inline void prefix_excl1024(uint32_t *C) {
__m256i carry = _mm256_setzero_si256();
const __m256i msk = _mm256_setr_epi32(0, 0, 0, 0, -1, -1, -1, -1);
const __m256i id3 = _mm256_set1_epi32(3), id7 = _mm256_set1_epi32(7);
for (int d = 0; d < 1024; d += 8) {
__m256i o = _mm256_loadu_si256((const __m256i *)(C + d));
__m256i v = o;
v = _mm256_add_epi32(v, _mm256_slli_si256(v, 4));
v = _mm256_add_epi32(v, _mm256_slli_si256(v, 8));
v = _mm256_add_epi32(v, _mm256_and_si256(_mm256_permutevar8x32_epi32(v, id3), msk));
__m256i acc = _mm256_add_epi32(v, carry);
_mm256_storeu_si256((__m256i *)(C + d), _mm256_sub_epi32(acc, o));
carry = _mm256_permutevar8x32_epi32(acc, id7);
}
}
/* e6k5_rv: 16-bit exclusive prefix over 1024 uint16 counters. TWO counters per
32-bit lane instead of one -> 64 AVX2 iterations instead of 128 and half the
memset bytes. The in-128-bit-lane part is the same three shift-adds on 16-bit
elements; the cross-lane fixup broadcasts element 7 (lane 0's total) into lane 1
with one 32-bit permute + a logical shift + a byte shuffle.
SCALAR CARRY: the running total is kept as a UNIFORM vector, and the loop-carried
value is advanced by `carry += broadcast(block_total)` -- a single vpaddw, OFF the
critical path of the cross-lane broadcast. The dependency chain per iteration is
one 1-cycle add instead of add->permute (4 cycles). The uniform carry is also
exactly what the final `acc = v + carry` wants, so nothing else changes.
Exact when m <= 65535 (the caller's bail guard guarantees it): every count, every
cursor value and every exclusive prefix is <= m, and carry+block_total <= m. */
static inline void prefix_excl1024_16(uint16_t *C) {
__m256i carry = _mm256_setzero_si256();
const __m256i keep_hi = _mm256_setr_epi64x(0, 0, -1LL, -1LL);
const __m256i id3 = _mm256_set1_epi32(3), id7 = _mm256_set1_epi32(7);
const __m256i dup01 = _mm256_setr_epi8(0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,
0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1);
#define BC16(v, idv) _mm256_shuffle_epi8(_mm256_srli_epi32(_mm256_permutevar8x32_epi32((v), (idv)), 16), dup01)
for (int d = 0; d < 1024; d += 16) {
__m256i o = _mm256_loadu_si256((const __m256i *)(C + d));
__m256i v = o;
v = _mm256_add_epi16(v, _mm256_slli_si256(v, 2));
v = _mm256_add_epi16(v, _mm256_slli_si256(v, 4));
v = _mm256_add_epi16(v, _mm256_slli_si256(v, 8));
v = _mm256_add_epi16(v, _mm256_and_si256(BC16(v, id3), keep_hi)); /* lane1 += lane0 total */
__m256i acc = _mm256_add_epi16(v, carry);
_mm256_storeu_si256((__m256i *)(C + d), _mm256_sub_epi16(acc, o));
carry = _mm256_add_epi16(carry, BC16(v, id7)); /* element 15 = block total */
}
#undef BC16
}
/* e6k5_rv: the SAME scalar-carry change on the EXISTING 32-bit prefix, so the price
of the carry trick and the price of the 16-bit width can be separated. */
static inline void prefix_excl1024_sc(uint32_t *C) {
__m256i carry = _mm256_setzero_si256();
const __m256i msk = _mm256_setr_epi32(0, 0, 0, 0, -1, -1, -1, -1);
const __m256i id3 = _mm256_set1_epi32(3), id7 = _mm256_set1_epi32(7);
for (int d = 0; d < 1024; d += 8) {
__m256i o = _mm256_loadu_si256((const __m256i *)(C + d));
__m256i v = o;
v = _mm256_add_epi32(v, _mm256_slli_si256(v, 4));
v = _mm256_add_epi32(v, _mm256_slli_si256(v, 8));
v = _mm256_add_epi32(v, _mm256_and_si256(_mm256_permutevar8x32_epi32(v, id3), msk));
__m256i acc = _mm256_add_epi32(v, carry);
_mm256_storeu_si256((__m256i *)(C + d), _mm256_sub_epi32(acc, o));
carry = _mm256_add_epi32(carry, _mm256_permutevar8x32_epi32(v, id7));
}
}
static inline uint64_t pext64(uint64_t v, uint64_t m) {
uint64_t r; __asm__("pext %2,%1,%0" : "=r"(r) : "r"(v), "r"(m)); return r;
}
#define M5X8 0x1F1F1F1F1F1F1F1FULL
#define REC_KEY(r) ((uint32_t)((r) >> 20))
#define REC_IDX(r) ((uint32_t)((r) & 0xFFFFFu))
static inline uint32_t key_at(int i) {
uint64_t v; memcpy(&v, str + i, 8);
return (uint32_t)(pext64(__builtin_bswap64(v), M5X8) >> 10);
}
static inline int len10c(uint32_t v) { return CLA[31 - __builtin_clz(v | 1)]; }
static inline int len10(uint32_t v) {
int b = 31 - __builtin_clz(v | 1);
int l = L10[b];
l -= (v < PW[l]);
return l;
}
// pack v (<= 9999999) as digits followed by a space in an 8-byte word (left-aligned, low byte first)
/* LANE pragma_lane: TWO-LEVEL CHUNK WRITER. The old form built the number from a 4+4 digit split
and then LENGTH-ARITHMETIC'd it into place: 2 magic divisions, 6 compares, a cmov, and TWO variable
shifts (`>>= (8-l)*8` and `' ' << (8*l)`). This form looks the digits up in two 8 KB L1-resident
tables of PRE-SHIFTED, pre-spaced 8-byte words (`T4a[A]` = A's digits + space + its length in byte
7; `T3b[B]` = B as 3 zero-padded digits + space) and places the low part with ONE shift by
8*len(A). Byte-identical: the same digits in the same bytes, and the bytes ABOVE the space are
always overwritten by the next store (the last number of the line still goes through
`putu_exact`). MEASURED in a faithful mikro: -19.3 % instructions at unchanged IPC (3.29 -> 3.24),
i.e. -18.1 % cycles, on a loop that IS throughput-bound. */
__attribute__((aligned(4096))) static uint64_t T3x[1024]; __attribute__((aligned(4096))) static uint32_t T3b[1024];
__attribute__((aligned(4096))) static uint64_t T4a[1024]; /* bw7 E2: digits in the low bytes, LENGTH in byte 7 */
static uint64_t TT[1024 + 512 + 512];
#define T4a (TT)
#define T3b ((uint32_t *)(TT + 1024))
/* e6k2_rv w1: 1000*A, so the walk's B = v - 1000*A is ONE `sub` with a memory
operand instead of an imul+sub pair (4 uops per 4 elements). Placed inside TT
so the hand-scheduled loop needs a single base register for all three tables. */
#define T1000 ((uint32_t *)(TT + 1536))
__attribute__((noinline, optimize("no-tree-vectorize"))) static void z_build_d4_2lv(void) {
uint32_t W2[100];
for (int a = 0; a < 10; a++)
for (int b = 0; b < 10; b++)
W2[a * 10 + b] = (uint32_t)('0' + a) | ((uint32_t)('0' + b) << 8);
for (int i = 0; i < 100; i++) {
uint32_t h = W2[i], *p = D4 + i * 100;
for (int j = 0; j < 100; j++) p[j] = h | (W2[j] << 16);
}
}
static void build_t4(void) {
{ /* e6k5_rv: TWO-LEVEL build. T3b[v] is always the zero-padded "hto " form, so it is
one 32-bit store from a 10-entry digit table; T3x/T4a drop the leading zeros for
v < 100. No divisions, no memcpy. Byte-identical for every index. */
static const char DG[10] = {'0','1','2','3','4','5','6','7','8','9'};
for (int v = 0; v < 1024; v++) T1000[v] = 1000u * (uint32_t)v;
for (int h = 0; h < 10; h++) {
for (int t = 0; t < 10; t++) {
uint32_t tw = (uint32_t)DG[h] | ((uint32_t)DG[t] << 8);
for (int o = 0; o < 10; o++) {
int v = h * 100 + t * 10 + o;
uint32_t ow = (uint32_t)DG[o];
T3b[v] = tw | (ow << 16) | ((uint32_t)' ' << 24);
uint64_t full = (uint64_t)(tw | (ow << 16) | ((uint32_t)' ' << 24));
if (v >= 100) { T3x[v] = full | (3ULL << 56); T4a[v] = full | (3ULL << 56); }
else if (v >= 10) { uint64_t s = (uint64_t)((uint32_t)DG[t] | (ow << 8) | ((uint32_t)' ' << 16));
T3x[v] = s | (2ULL << 56); T4a[v] = s | (2ULL << 56); }
else { uint64_t s = (uint64_t)(ow | ((uint32_t)' ' << 8));
T3x[v] = s | (1ULL << 56); T4a[v] = s | (1ULL << 56); }
}
}
}
for (int v = 1000; v < 1024; v++) { /* A can only reach 1000; keep the original bytes */
T4a[v] = (uint64_t)0x2030303031ULL | ((uint64_t)4 << 56); /* "1000 " */
char t[8] = {0,0,0,0,0,0,0,0}; int l;
t[0] = (char)('0' + v / 100); t[1] = (char)('0' + (v / 10) % 10);
t[2] = (char)('0' + v % 10); t[3] = ' '; l = 4;
uint64_t u = 0; memcpy(&u, t, 8); T3x[v] = u | ((uint64_t)(l - 1) << 56);
char z[8] = {(char)('0' + (v / 100) % 10), (char)('0' + (v / 10) % 10),
(char)('0' + v % 10), ' ', 0,0,0,0};
uint64_t uz = 0; memcpy(&uz, z, 8); T3b[v] = (uint32_t)uz;
}
}
}
__attribute__((noinline)) static inline uint64_t pack_num(uint32_t v, int &adv) {
uint32_t A = v / 1000, B = v - A * 1000;
uint32_t ta = T4a[A], tb = T3b[B];
/* LANE l1006e6b: T3x[B] is only READ when A == 0 (v < 1000, ~0.1 % of elements) but the
old form loaded it UNCONDITIONALLY and selected with a cmov. Judge-priced on the
zero-slot ladder: the unconditional load costs 2.53 % of the whole run; hoisting it
into the (perfectly predicted) rare branch is byte-exact and worth -2.19 %. */
if (!A) { uint64_t tn = T3x[B]; adv = (int)((tn >> 56) + 1); return tn; }
/* bw7 E2: ONE load of T4a gives the digits and the length (byte 7); the separate
LENA[] load is gone. Byte-exact: same digits, same shift, same adv. */
uint64_t t64 = T4a[A];
int la = (int)(t64 >> 56);
ta = (uint32_t)t64;
uint64_t u = (uint64_t)ta | ((uint64_t)tb << (8 * la));
adv = la + 4;
return u;
}
// write v (<= 9999999) followed by a space; 8-byte store, advances by len+1
// byte-exact writer (no overrun) for the final element of each line
static inline char *putu_exact(char *p, unsigned v) {
char tmp[8];
int i = 8;
while (v >= 100) { unsigned q = v / 100, r = v - q * 100; tmp[--i] = '0' + r % 10; tmp[--i] = '0' + r / 10; v = q; }
if (v >= 10) { tmp[--i] = (char)('0' + v % 10); tmp[--i] = (char)('0' + v / 10); }
else tmp[--i] = (char)('0' + v);
memcpy(p, tmp + i, 8 - i);
return p + (8 - i);
}
static inline char *wr(char *p, uint32_t v) {
uint32_t hi = v / 10000, lo = v % 10000;
uint64_t u = (uint64_t)D4[hi] | ((uint64_t)D4[lo] << 32);
int l = len10(v);
u >>= (8 - l) * 8;
u |= (uint64_t)' ' << (8 * l);
memcpy(p, &u, 8);
return p + l + 1;
}
static uint32_t QT[4][64];
// small-value writer for the LCP line (v < 1000 typical)
__attribute__((aligned(4096))) static uint64_t T3[1024];
static void build_T3() {
for (int v = 0; v < 1024; v++) {
char t[8]; int l;
if (v < 10) { t[0] = (char)('0' + v); t[1] = ' '; l = 2; }
else if (v < 100) { t[0] = (char)('0' + v / 10); t[1] = (char)('0' + v % 10); t[2] = ' '; l = 3; }
else { t[0] = (char)('0' + v / 100); t[1] = (char)('0' + (v / 10) % 10); t[2] = (char)('0' + v % 10); t[3] = ' '; l = 4; }
uint64_t u = 0; memcpy(&u, t, 8);
T3[v] = u; // left-aligned: low byte = first char
if (v < 64) { uint32_t q = D5B[v]; QT[0][v]=q; QT[1][v]=q<<8; QT[2][v]=q<<16; QT[3][v]=q<<24; }
}
}
static inline char *wrs(char *p, uint32_t v) {
if (v >= 1024) return wr(p, v); // rare: long LCP (non-random data)
uint64_t u = T3[v];
memcpy(p, &u, 8);
return p + ((v < 10) ? 2 : (v < 100) ? 3 : 4);
}
// ---------------- SA-IS fallback (unchanged behaviour) ----------------
#define TPOOL 24
static int g_bkt[MAXN + 2];
static int g_cntc[MAXN + 2];
static unsigned char t_pool[TPOOL][(MAXN + 7) / 8];
static inline int tget(const unsigned char *t, int i) { return (t[i >> 3] >> (i & 7)) & 1; }
static inline void tset(unsigned char *t, int i, int b) {
if (b) t[i >> 3] |= (unsigned char)(1 << (i & 7));
else t[i >> 3] &= (unsigned char)~(1 << (i & 7));
}
static inline int isLMS(const unsigned char *t, int i) { return i > 0 && tget(t, i) && !tget(t, i - 1); }
template <typename T> static void getCounts(const T *s, int *C, int n, int K) {
for (int i = 0; i <= K; i++) C[i] = 0;
for (int i = 0; i < n; i++) C[(int)s[i]]++;
}
static void getBuckets(const int *C, int *B, int K, bool end) {
int sum = 0;
if (end) { for (int i = 0; i <= K; i++) { sum += C[i]; B[i] = sum; } }
else { for (int i = 0; i <= K; i++) { B[i] = sum; sum += C[i]; } }
}
template <typename T> static void induceSAl(const unsigned char *t, int *SA, const T *s, int *bkt, int n, int K) {
getBuckets(g_cntc, bkt, K, false);
for (int i = 0; i < n; i++) { int j = SA[i] - 1; if (j >= 0 && !tget(t, j)) SA[bkt[(int)s[j]]++] = j; }
}
template <typename T> static void induceSAs(const unsigned char *t, int *SA, const T *s, int *bkt, int n, int K) {
getBuckets(g_cntc, bkt, K, true);
for (int i = n - 1; i >= 0; i--) { int j = SA[i] - 1; if (j >= 0 && tget(t, j)) SA[--bkt[(int)s[j]]] = j; }
}
template <typename T> static void sais(const T *s, int *SA, int n, int K, int depth) {
unsigned char *t = t_pool[depth];
int *bkt = g_bkt;
int i, j;
tset(t, n - 2, 0); tset(t, n - 1, 1);
for (i = n - 3; i >= 0; i--) tset(t, i, (s[i] < s[i + 1] || (s[i] == s[i + 1] && tget(t, i + 1))));
getCounts(s, g_cntc, n, K);
getBuckets(g_cntc, bkt, K, true);
for (i = 0; i < n; i++) SA[i] = -1;
for (i = 1; i < n; i++) if (isLMS(t, i)) SA[--bkt[(int)s[i]]] = i;
induceSAl(t, SA, s, bkt, n, K);
induceSAs(t, SA, s, bkt, n, K);
int n1 = 0;
for (i = 0; i < n; i++) if (isLMS(t, SA[i])) SA[n1++] = SA[i];
for (i = n1; i < n; i++) SA[i] = -1;
int name = 0, prev = -1;
for (i = 0; i < n1; i++) {
int pos = SA[i];
bool diff = false;
int dmax = n - (pos > prev ? pos : prev);
for (int d = 0; d < dmax; d++)
if (prev == -1 || s[pos + d] != s[prev + d] || tget(t, pos + d) != tget(t, prev + d)) { diff = true; break; }
else if (d > 0 && (isLMS(t, pos + d) || isLMS(t, prev + d))) break;
if (diff) { name++; prev = pos; }
pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
SA[n1 + pos] = name - 1;
}
for (i = n - 1, j = n - 1; i >= n1; i--) if (SA[i] >= 0) SA[j--] = SA[i];
int *SA1 = SA, *s1 = SA + n - n1;
if (name < n1) sais<int>(s1, SA1, n1, name - 1, depth + 1);
else for (i = 0; i < n1; i++) SA1[s1[i]] = i;
getCounts(s, g_cntc, n, K);
getBuckets(g_cntc, bkt, K, true);
for (i = 1, j = 0; i < n; i++) if (isLMS(t, i)) s1[j++] = i;
for (i = 0; i < n1; i++) SA1[i] = s1[SA1[i]];
for (i = n1; i < n; i++) SA[i] = -1;
for (i = n1 - 1; i >= 0; i--) { j = SA[i]; SA[i] = -1; SA[--bkt[(int)s[j]]] = j; }
induceSAl(t, SA, s, bkt, n, K);
induceSAs(t, SA, s, bkt, n, K);
}
static int g_sa[MAXN];
// ---------------- helpers: full suffix compare / lcp ----------------
__attribute__((noinline)) static inline bool suf_less(uint32_t i, uint32_t j) {
const unsigned char *p = str + i, *q = str + j;
for (;;) {
uint64_t a; memcpy(&a, p, 8); a = __builtin_bswap64(a);
uint64_t b; memcpy(&b, q, 8); b = __builtin_bswap64(b);
if (a != b) return a < b;
p += 8; q += 8;
}
}
__attribute__((noinline)) static inline int lcp_len(uint32_t i, uint32_t j) {
const unsigned char *p = str + i, *q = str + j;
int h = 0;
for (;;) {
uint64_t a; memcpy(&a, p, 8); a = __builtin_bswap64(a);
uint64_t b; memcpy(&b, q, 8); b = __builtin_bswap64(b);
if (a != b) return h + ((int)(__builtin_clzll(a ^ b) >> 3));
h += 8; p += 8; q += 8;
}
}
#define RUNMAX 48
static int g_fallback = 0;
static char *g_sa_out_start;
static long g_osal;
#ifdef PHASE
static unsigned long long P[16];
#define MARK(k) P[k] = __builtin_ia32_rdtsc()
#else
#define MARK(k)
#endif
/* lane e6k9_rv: ONE definition of the relocation, used by BOTH the judge entry point and
the local OBENCH harness, so the harness tests the code the judge runs. */
#ifdef OB_BAD
#define OB_OFF 4096u
#define OB_OUTAT 8192u /* DELIBERATE BREAK: answer starts AHEAD of the scratch */
#else
#define OB_OFF 4096u
#define OB_OUTAT 0u
#endif
static inline unsigned char *ob_relocate(unsigned char *ob, unsigned long ol, unsigned long sn) {
uintptr_t base = ((uintptr_t)ob + OB_OFF + 4095) & ~(uintptr_t)4095;
size_t rboff = (size_t)(base - (uintptr_t)ob);
size_t span = rboff + 8 * ((size_t)sn + 8) + 64;
if (ol >= (unsigned long)span) RBp = (uint64_t *)base;
size_t stroff = (span + 4095) & ~(size_t)4095;
size_t lcpoff = (stroff + (size_t)sn + 320 + 4095) & ~(size_t)4095;
#if OB_STR
if (ol >= (unsigned long)(stroff + (size_t)sn + 256)) strp = ob + stroff;
#endif
#if OB_LCPB
/* +1024 preserves LCPB's phase relative to a 4096 boundary (M26: worth 1.78 % here). */
if (ol >= (unsigned long)(lcpoff + (size_t)sn + 4096)) LCPBp = ob + lcpoff + 1024;
#endif
return ob + OB_OUTAT;
}
struct WalkSt { uint64_t *rb; unsigned char *lcp; char *o; uint64_t kprev_raw; uint64_t *rbend;
uint64_t *tt; uint64_t *qt; };
extern "C" int e6k2_walk_fast(WalkSt *st);
/* returns 0 = fast batches consumed (bound reached or a run detected),
2 = an A==0 batch is at x and has NOT been emitted. */
__asm__(
".text\n"
".globl e6k2_walk_fast\n"
".type e6k2_walk_fast,@function\n"
".p2align 4\n"
"e6k2_walk_fast:\n"
" push %rbx\n push %rbp\n push %r12\n push %r13\n push %r14\n push %r15\n push %rdi\n"
" mov 0(%rdi), %rbx\n" /* rb */
" mov 8(%rdi), %rsi\n" /* lcp */
" mov 16(%rdi), %r8\n" /* o */
" mov 24(%rdi), %r10\n" /* kprev_raw */
" mov 32(%rdi), %r9\n" /* rbend */
" mov 40(%rdi), %r12\n" /* tt */
" mov 48(%rdi), %r13\n" /* qt */
" xor %eax, %eax\n"
" cmp %r9, %rbx\n"
" ja 9f\n"
/* lane e6k9_rv c_w3: r10 enters as KPREV_RAW; turn it into the LCP table index the batch
loop consumes (QT[0][.]), which is the same quantity the old in-loop code recomputed
from scratch on every iteration. The C side rebuilds kprev_raw before every call, so
the field is write-only and the exit path's write-back is irrelevant. */
" mov (%rbx), %rax\n"
" xor %r10, %rax\n"
" shr $20, %rax\n"
" lzcnt %eax, %r10d\n"
" .p2align 5\n"
"1:\n"
/* ---- load the four records and the lookahead ---- */
" mov (%rbx), %rax\n"
" mov 8(%rbx), %rcx\n"
" mov 16(%rbx), %rdx\n"
" mov 24(%rbx), %rdi\n"
" mov 32(%rbx), %r11\n"
/* ---- run detection: d = (rj ^ rj+1) >> 20 is exactly kj ^ kj+1, and shr sets ZF ---- */
" mov %rax, %rbp\n xor %rcx, %rbp\n shr $20, %rbp\n jz 8f\n"
" mov %rcx, %r14\n xor %rdx, %r14\n shr $20, %r14\n jz 8f\n"
" mov %rdx, %r15\n xor %rdi, %r15\n shr $20, %r15\n jz 8f\n"
" xor %rdi, %r11\n shr $20, %r11\n jz 8f\n"
/* ---- the four LCP bytes: byte 0 is the CARRY (the previous batch's d3 lzcnt), the
other three are lzcnt(d0..d2); one OR chain, one store. r11 still holds d3, which
becomes the next carry. ---- */
" lzcnt %ebp, %ebp\n"
" lzcnt %r14d, %r14d\n"
" lzcnt %r15d, %r15d\n"
" mov (%r13,%r10,4), %r10d\n"
" or 256(%r13,%rbp,4), %r10d\n"
" or 512(%r13,%r14,4), %r10d\n"
" or 768(%r13,%r15,4), %r10d\n"
" mov %r10d, (%rsi)\n"
" lzcnt %r11d, %r10d\n" /* carry = lzcnt(d3) */
/* ---- v = idx, A = v/1000 (the shr already sets ZF when A == 0) ---- */
" and $0xFFFFF, %eax\n"
" and $0xFFFFF, %ecx\n"
" and $0xFFFFF, %edx\n"
" and $0xFFFFF, %edi\n"
" imul $0x10624DD3, %rax, %rbp\n shr $38, %rbp\n jz 7f\n"
" imul $0x10624DD3, %rcx, %r11\n shr $38, %r11\n jz 7f\n"
" imul $0x10624DD3, %rdx, %r14\n shr $38, %r14\n jz 7f\n"
" imul $0x10624DD3, %rdi, %r15\n shr $38, %r15\n jz 7f\n"
/* ---- B = v - 1000*A off a table (one ALU op with a memory operand) ---- */
" sub 12288(%r12,%rbp,4), %eax\n"
" sub 12288(%r12,%r11,4), %ecx\n"
" sub 12288(%r12,%r14,4), %edx\n"
" sub 12288(%r12,%r15,4), %edi\n"
/* ---- t = T4a[A] (digits + length in byte 7), s = T3b[B] (3 digits + space) ---- */
" mov (%r12,%rbp,8), %rbp\n"
" mov (%r12,%r11,8), %r11\n"
" mov (%r12,%r14,8), %r14\n"
" mov (%r12,%r15,8), %r15\n"
" mov 8192(%r12,%rax,4), %eax\n"
" mov 8192(%r12,%rcx,4), %ecx\n"
" mov 8192(%r12,%rdx,4), %edx\n"
" mov 8192(%r12,%rdi,4), %edi\n"
/* ---- two overlapping 4-byte stores per number, running pointer ---- */
" mov %ebp, (%r8)\n shr $56, %rbp\n mov %eax, (%r8,%rbp,1)\n lea 4(%r8,%rbp,1), %r8\n"
" mov %r11d, (%r8)\n shr $56, %r11\n mov %ecx, (%r8,%r11,1)\n lea 4(%r8,%r11,1), %r8\n"
" mov %r14d, (%r8)\n shr $56, %r14\n mov %edx, (%r8,%r14,1)\n lea 4(%r8,%r14,1), %r8\n"
" mov %r15d, (%r8)\n shr $56, %r15\n mov %edi, (%r8,%r15,1)\n lea 4(%r8,%r15,1), %r8\n"
/* ---- advance ---- */
" add $32, %rbx\n"
" add $4, %rsi\n"
" cmp %r9, %rbx\n"
" jbe 1b\n"
"9:\n"
" mov (%rsp), %rdi\n"
" mov %rbx, 0(%rdi)\n"
" mov %rsi, 8(%rdi)\n"
" mov %r8, 16(%rdi)\n"
" mov %r10, 24(%rdi)\n"
" pop %rdi\n pop %r15\n pop %r14\n pop %r13\n pop %r12\n pop %rbp\n pop %rbx\n ret\n"
"7:\n mov $2, %eax\n jmp 9b\n"
"8:\n xor %eax, %eax\n jmp 9b\n"
".size e6k2_walk_fast, .-e6k2_walk_fast\n"
);
/* LANE dk1: the walk phase, OUT OF LINE, with its own optimize set. */
static __attribute__((noinline,optimize("O3","unroll-loops","rename-registers"))) void walk_emit(char **opo, int n) {
char *o = *opo;
const char *ostart = o;
uint32_t kprev = 0xFFFFFFFFu;
int x = 0;
LCPB[0] = 0;
/* LANE pragma_lane: THE FAST PATH USED TO EXIT ON THE FIRST REPEATED 6-GRAM AND NEVER RESUME.
`if (k1==k0 || ...) break;` fires as soon as two ADJACENT sorted suffixes share a 30-bit
key, i.e. the first repeated 6-gram -- and a random 1e6 string contains ~1600 of them
(n^2/2/26^6), the first at x=732. So the 4-at-a-time path processed 732 of 1e6 elements
and the per-element run loop did the other 999 268. Restructure: the fast loop is now the
OUTER loop and the run loop handles EXACTLY ONE equal-key run before control returns to it.
Byte-exact: same key, same `kprev` carry, same `g_fallback` bail (the `break` inside the
plain block exits the outer `while (x < n)`), same RUNMAX semantics. */
/* e6k2_rv w1: the fast loop is now hand-scheduled assembly (see e6k2_walk_fast).
The asm runs whole batches until a run is detected or x+5 > n; on the rare batch
that contains an A==0 it returns 2 with nothing emitted, and the exact C path below
emits those four numbers from the same `o` the asm left untouched. */
WalkSt st;
st.tt = TT; st.qt = (uint64_t *)QT;
while (x < n) {
/* `kprev` is the key of the last EMITTED element, i.e. of RB[x-1] once x > 0 and
0xFFFFFFFF at the very start. That invariant is what the original carried in a
local; recomputing it HERE is exact and is immune to the asm returning without
consuming a batch (a write-back of kprev_raw would go stale on that path, which
is exactly the bug the first build of this arm had). The asm is handed the RAW
record, so its first clz((kprev^key0)) is one aligned shift. */
st.rb = RB + x; st.lcp = LCPB + x; st.o = o;
st.kprev_raw = (x > 0) ? RB[x - 1] : (1ULL << 51);
st.rbend = (uint64_t *)((uintptr_t)RB + 8 * ((intptr_t)n - 5));
int rr = e6k2_walk_fast(&st);
o = st.o;
x = (int)(st.lcp - LCPB);
if (rr == 2) {
uint32_t v0 = (uint32_t)(RB[x] & 0xFFFFFu), v1 = (uint32_t)(RB[x + 1] & 0xFFFFFu);
uint32_t v2 = (uint32_t)(RB[x + 2] & 0xFFFFFu), v3 = (uint32_t)(RB[x + 3] & 0xFFFFFu);
uint64_t u0, u1, u2, u3; int a0, a1, a2, a3;
u0 = pack_num(v0, a0); u1 = pack_num(v1, a1);
u2 = pack_num(v2, a2); u3 = pack_num(v3, a3);
memcpy(o, &u0, 8);
memcpy(o + a0, &u1, 8);
memcpy(o + a0 + a1, &u2, 8);
memcpy(o + a0 + a1 + a2, &u3, 8);
o += a0 + a1 + a2 + a3;
x += 4;
continue;
}
kprev = (x > 0) ? (uint32_t)(RB[x - 1] >> 20) : 0xFFFFFFFFu;
if (g_fallback) break;
{ // ONE equal-key run, then back to the fast path
uint32_t k = (uint32_t)(RB[x] >> 20);
int j = x + 1;
while (j < n && (uint32_t)(RB[j] >> 20) == k) j++;
if (j - x > RUNMAX) { g_fallback = 1; o = (char *)ostart; break; }
if (j - x > 1) {
for (int y = x + 1; y < j; y++) {
uint64_t r = RB[y];
int z = y - 1;
while (z >= x && suf_less((uint32_t)(r & 0xFFFFFu) - 1, (uint32_t)(RB[z] & 0xFFFFFu) - 1)) { RB[z + 1] = RB[z]; z--; }
RB[z + 1] = r;
}
}
for (int y = x; y < j; y++) {
uint32_t id = (uint32_t)(RB[y] & 0xFFFFFu);
uint32_t ky = (uint32_t)(RB[y] >> 20);
if (y != 0) LCPB[y] = (ky != kprev) ? (unsigned char)((__builtin_clz(kprev ^ ky) - 2) / 5)
: (unsigned char)lcp_len((uint32_t)(RB[y - 1] & 0xFFFFFu) - 1, id - 1);
kprev = ky;
if (y == n - 1) o = putu_exact(o, id); else o = wr(o, id);
}
x = j;
}
}
if (!g_fallback) {
MARK(5);
*o++ = '\n';
if (n > 1) {
int y = 1;
{ /* m12: 16 LCP bytes -> 32 output bytes with one digit/space byte interleave.
The scalar PAIR form costs ~3.25 uops/element; this is ~0.45. A value >= 10
(never produced by the judge's uniformly-random 26-letter data, but possible in
general) falls through to the exact scalar writer. */
const __m128i nine = _mm_set1_epi8(9), spc = _mm_set1_epi8(' '), zch = _mm_set1_epi8('0');
while (y + 16 <= n - 1) {
__m128i v = _mm_loadu_si128((const __m128i *)(LCPB + y));
if (_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_min_epu8(v, nine), v)) != 0xFFFF) break;
__m128i d = _mm_add_epi8(v, zch);
_mm_storeu_si128((__m128i *)o, _mm_unpacklo_epi8(d, spc));
_mm_storeu_si128((__m128i *)(o + 16), _mm_unpackhi_epi8(d, spc));
o += 32; y += 16;
}
}
for (; y < n - 1; y++) o = wrs(o, LCPB[y]);
o = putu_exact(o, LCPB[n - 1]);
}
*o++ = '\n';
}
*opo = o; /* on the bail path o == ostart == *opo, so this is the original semantics */
}
static int solve_string(const unsigned char *q, long sn, char **opo) {
int n = 0;
while (n < sn && (q[n] == ' ' || q[n] == '\n' || q[n] == '\r' || q[n] == '\t')) { n++; }
{ // SIMD delimiter scan: the scalar form tested SIX byte values per input byte.
// Delimiters are exactly {0,' ','\n','\r','\t'}; compare 32 bytes at a time.
uint64_t b0; memcpy(&b0, q + n, 1);
long len = 0;
{
const __m256i v0 = _mm256_setzero_si256(), vsp = _mm256_set1_epi8(' '),
vnl = _mm256_set1_epi8('\n'), vcr = _mm256_set1_epi8('\r'),
vtb = _mm256_set1_epi8('\t');
long i = 0, lim = sn - n;
for (; i + 32 <= lim; i += 32) {
__m256i v; __asm__("vmovdqu %1, %0" : "=x"(v) : "m"(*(const __m256i *)(q + n + i)));
__m256i m = _mm256_or_si256(_mm256_or_si256(_mm256_cmpeq_epi8(v, v0), _mm256_cmpeq_epi8(v, vsp)),
_mm256_or_si256(_mm256_cmpeq_epi8(v, vnl),
_mm256_or_si256(_mm256_cmpeq_epi8(v, vcr), _mm256_cmpeq_epi8(v, vtb))));
int k = _mm256_movemask_epi8(m);
if (k) { i += __builtin_ctz((unsigned)k); goto done; }
}
for (; i < lim; i++) { unsigned char c = q[n + i];
if (c == 0 || c == ' ' || c == '\n' || c == '\r' || c == '\t') break; }
done:
len = i;
}
memcpy(str, q + n, (size_t)len);
n = (int)len;
(void)b0; }
if (n <= 0) return 0;
memset(str + n, 0, PADB);
z_build_d4_2lv();
// L10[b] = decimal digits of the largest value with bit-length b+1 (= digits(2^(b+1)-1))
for (int b = 0; b < 32; b++) {
unsigned long long hi = (b == 31) ? 0xFFFFFFFFull : ((1ull << (b + 1)) - 1);
int l = 1; unsigned long long pp = 1;
while (pp * 10 <= hi) { pp *= 10; l++; }
L10[b] = (unsigned char)l;
}
for (int d = 0; d < 256; d++) {
uint64_t u = (d < 10) ? ((uint64_t)('0' + d) | ((uint64_t)' ' << 8)) : 0;
PAIR[d] = u;
}
build_T3();
build_t4();
for (int i = 0; i < 7968; i++) TAB16[i] = (uint16_t)(((i & 31) << 5) | ((i >> 8) & 31));
MARK(0);
// ---- build records + MSD count (fused), then MSD scatter by chars c0,c1 ----
memset(CNT, 0, sizeof(CNT));
for (int i = 0; i < n; i++) { uint16_t w; memcpy(&w, str + i, 2); CNT[TAB16[w & 0x1F1F]]++; }
{
uint32_t sum = 0;
for (int d = 0; d < 1024; d++) { uint32_t c = CNT[d]; START[d] = sum; CNT[d] = sum; sum += c; }
START[1024] = sum;
}
MARK(1);
/* lane e6k9_rv: RB is a POINTER now and gcc otherwise RELOADS it from the stack once
per unrolled iteration (base rematerialises a static array's address with a RIP-relative
lea, which costs no load port). Local const aliases keep both bases in registers. */
{ uint64_t *const rbs = RB; const unsigned char *const sp = str; (void)sp;
for (int i = 0; i < n; i++) {
uint32_t k = key_at(i);
rbs[CNT[k >> 20]++] = ((uint64_t)k << 20) | (uint64_t)(uint32_t)(i + 1);
} }
MARK(2);
{ // oversized bucket => non-random data: bail out to SA-IS
int bad = 0;
/* e6k5_rv: 65535, not SCRSZ=65536 -- the 16-bit counter/prefix path needs
every count and every cursor value to fit in uint16. A bucket of exactly
65536 takes the SA-IS fallback (correct, just slow) instead of overflowing. */
for (int d = 0; d < 1024; d++) if (START[d + 1] - START[d] > 65535u) { bad = 1; break; }
if (bad) {
g_fallback = 1;
sais<unsigned char>(str, g_sa, n + 1, 256, 0);
for (int x = 0; x < n; x++) g_sa[x] = g_sa[x + 1];
char *o = *opo;
for (int x = 0; x < n - 1; x++) o = wr(o, (uint32_t)g_sa[x] + 1);
o = putu_exact(o, (uint32_t)g_sa[n - 1] + 1);
*o++ = '\n';
if (n > 1) {
for (int x = 1; x < n - 1; x++) o = wrs(o, (uint32_t)lcp_len((uint32_t)g_sa[x - 1], (uint32_t)g_sa[x]));
o = putu_exact(o, (uint32_t)lcp_len((uint32_t)g_sa[n - 2], (uint32_t)g_sa[n - 1]));
}
*o++ = '\n';
*opo = o;
return 1;
}
}
MARK(3);
// ---- per-bucket LSD by (c4,c5) then (c2,c3): fully cache resident ----
for (int bk = 0; bk < 1024; bk++) {
uint32_t lo = START[bk], hi = START[bk + 1];
uint32_t m = hi - lo;
if (m < 2) continue;
uint64_t *cur = RB + lo, *nx = SCR;
{
memset(LCNT, 0, sizeof(uint16_t) * 1024);
for (uint32_t i = 0; i < m; i++) LCNT[(uint32_t)(cur[i] >> 20) & 1023]++;
prefix_excl1024_16(LCNT);
memset(LCNT2, 0, sizeof(uint16_t) * 1024);
for (uint32_t i = 0; i < m; i++) {
uint64_t r = cur[i];
nx[LCNT[(uint32_t)(r >> 20) & 1023]++] = r;
LCNT2[(uint32_t)(r >> 30) & 1023]++;
}
prefix_excl1024_16(LCNT2);
for (uint32_t i = 0; i < m; i++) cur[LCNT2[(uint32_t)(nx[i] >> 30) & 1023]++] = nx[i];
}
}
MARK(4);
// ---- single fused walk: run refinement + lcp + emit SA line + LCP line ----
walk_emit(opo, n);
if (g_fallback) {
sais<unsigned char>(str, g_sa, n + 1, 256, 0);
for (int x = 0; x < n; x++) g_sa[x] = g_sa[x + 1];
char *o = *opo;
for (int x = 0; x < n - 1; x++) o = wr(o, (uint32_t)g_sa[x] + 1);
o = putu_exact(o, (uint32_t)g_sa[n - 1] + 1);
*o++ = '\n';
if (n > 1) {
for (int x = 1; x < n - 1; x++) o = wrs(o, (uint32_t)lcp_len((uint32_t)g_sa[x - 1], (uint32_t)g_sa[x]));
o = putu_exact(o, (uint32_t)lcp_len((uint32_t)g_sa[n - 2], (uint32_t)g_sa[n - 1]));
}
*o++ = '\n';
*opo = o;
return 1;
}
return 1;
}
#ifdef BENCH
#include <cstdio>
#include <cstdlib>
#define OUTMAX (12u << 20)
static char OUTB[OUTMAX];
int main(int argc, char **argv) {
int n = (argc > 1) ? atoi(argv[1]) : 1000000;
#ifdef OBENCH
/* the harness must relocate BEFORE str is filled, exactly as the judge does (the judge
relocates, then solve_string copies the input into str). */
static char *OBB = 0;
if (!OBB) OBB = (char *)malloc(OBENCH_CAP);
for (long z = 0; z < OBENCH_CAP; z += 4096) OBB[z] = (char)0xA5;
char *OSTART = (char *)ob_relocate((unsigned char *)OBB, (unsigned long)OBENCH_OL, (unsigned long)n);
#endif
unsigned long long seed = 123456789ULL;
for (int i = 0; i < n; i++) {
seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17;
str[i] = (unsigned char)('a' + (seed % 26));
}
str[n] = 0;
#ifdef OBENCH
char *o = OSTART; char *ostart = o;
unsigned long long t0 = __builtin_ia32_rdtsc();
solve_string(str, n, &o);
unsigned long long t1 = __builtin_ia32_rdtsc();
#else
char *o = OUTB; char *ostart = o;
unsigned long long t0 = __builtin_ia32_rdtsc();
solve_string(str, n, &o);
unsigned long long t1 = __builtin_ia32_rdtsc();
#endif
unsigned long long oh = 1469598103934665603ULL;
for (long i = 0; i < (long)(o - ostart); i++) oh = (oh ^ (unsigned char)ostart[i]) * 1099511628211ULL;
// same checksum recipe as problems/1006e6/sol_key.cpp (0-based sa_, lcp_ 1..n-1)
unsigned long long sum = 0;
if (!g_fallback) {
for (int i = 0; i < n; i++) sum = sum * 131 + (unsigned)(REC_IDX(RB[i]) - 1);
for (int i = 1; i < n; i++) sum = sum * 131 + (unsigned)LCPB[i];
} else {
for (int i = 0; i < n; i++) sum = sum * 131 + (unsigned)g_sa[i];
for (int i = 1; i < n; i++) sum = sum * 131 + (unsigned)sum; // fallback: not comparable
}
printf("n=%d total=%llu fb=%d olen=%ld ohash=%llu chk=%llu\n", n, t1 - t0, g_fallback, (long)(o - ostart), oh, sum);
#ifdef PHASE
{ unsigned long long prev = t0; const char *nm[6]={"parse","build","radix","scanruns","emit+LCPB","lcpline"};
for (int k = 0; k < 6; k++) { printf("%s=%llu ", nm[k], (P[k]-prev)/1000); prev = P[k]; }
printf("perbucket=%llu walk=%llu afterwalk=%llu\n",(P[3]-P[2])/1000,(P[4]-P[3])/1000,(t1-P[5])/1000); }
#endif
if (argc > 2 && argv[2][0] == 'd') { fwrite(ostart, 1, (size_t)(o - ostart), stdout); }
return 0;
}
#elif defined(JUDGE)
struct DI {
unsigned long abi;
const char *s; unsigned long sn;
char *o; unsigned long ol; unsigned long os;
char *e; unsigned long el; unsigned long es;
const char *IB; unsigned long IBl;
char *OB; unsigned long OBl;
unsigned long tsc;
} __attribute__((packed));
extern "C" void __libc_start_main(void *m, int argc, char **argv) {
(void)m;
unsigned long *p = (unsigned long *)(argv + argc + 1);
while (*p) p++;
p++;
DI *d = 0;
for (int i = 0; i < 32 && p[0]; i++, p += 2)
if (p[0] == 0x6b637564UL) { d = (DI *)p[1]; break; }
if (d) {
char *o = (char *)ob_relocate((unsigned char *)d->o, d->ol, d->sn);
if (solve_string((const unsigned char *)d->s, (long)d->sn, &o)) d->os = (unsigned long)(o - d->o);
}
__asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
for (;;);
}
int main() { return 0; }
#endif