提交记录 162342
| 提交时间 |
评测时间 |
| 2026-11-17 00:57:29 |
2026-11-17 00:57:38 |
#include <cstddef>
#include <cstdint>
#pragma GCC optimize("O3")
// Begin pure solver dependency: kernel.hpp
#pragma once
#include <cstddef>
#include <cstdint>
#include <cstring>
namespace debruijn_packed {
// Most-significant bit first. FKM/Lyndon concatenation, cyclic output.
// The output needs exactly 2^(N-3) bytes and no trailing linearization bits.
template<unsigned N> size_t generate(unsigned char*out) {
static_assert(N>=3 && N<=33,"supported order");
constexpr size_t bytes=size_t(1)<<(N-3);
unsigned char*dst=out; const unsigned char*end=out+bytes;
uint64_t word=0,reservoir=0;
unsigned pending=1; // The first Lyndon word is 0.
for(;;) {
unsigned trailing=__builtin_ctzll(~word),p=N-trailing;
if(!p)break;
++word;
for(unsigned shift=p;shift<N;shift*=2)word|=word>>shift;
if(p==N || N%p==0) {
uint64_t chunk=word>>(N-p);
// N=33 uses at most 40 significant bits in this accumulator.
// Other orders are intended only for the correctness tests <=33.
reservoir=(reservoir<<p)|chunk;
unsigned total=pending+p,q=total>>3;
pending=total&7;
if(q) {
uint64_t packed=__builtin_bswap64(reservoir<<(64-total));
if(size_t(end-dst)>=8)memcpy(dst,&packed,8);
else memcpy(dst,&packed,q);
dst+=q;
}
}
}
return size_t(dst-out);
}
}
// End pure solver dependency: kernel.hpp
static_assert(sizeof(unsigned)==4,"32-bit unsigned required");
static_assert(__BYTE_ORDER__==__ORDER_LITTLE_ENDIAN__,"Duck target is little endian");
void debruijn(unsigned n,char*s) {
if(n!=27u)__builtin_trap();
if(debruijn_packed::generate<27>((unsigned char*)s)!=16777216ULL)__builtin_trap();
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 34.572 ms | 16 MB + 8 KB | Accepted | Score: 100 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2026-11-21 00:40:36 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠