提交记录 162342


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex_maker 1021b. 测测你的德布莱英序列3 Accepted 100 34.572 ms 16392 KB C++17 1.66 KB
提交时间 评测时间
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();
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #134.572 ms16 MB + 8 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-11-21 00:40:36 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠