代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned int u32;
typedef int i32;
typedef unsigned long u64;
typedef long i64;

enum { MAXN = 1000, HASH_SIZE = 4096, HASH_MASK = HASH_SIZE - 1 };

typedef struct {
    i32 x, y, z;
} Point;

static Point point[MAXN];
static short parent_node[MAXN + 2];
static short chain_next[MAXN];
static i32 key_x[HASH_SIZE], key_y[HASH_SIZE], key_z[HASH_SIZE];
static short cell_head[HASH_SIZE];
static unsigned cell_stamp[HASH_SIZE];
static unsigned epoch;

static __attribute__((always_inline)) inline unsigned find_root(unsigned x) {
    unsigned root = x;
    while ((unsigned)parent_node[root] != root) root = (unsigned)parent_node[root];
    while (x != root) {
        unsigned next = (unsigned)parent_node[x];
        parent_node[x] = (short)root;
        x = next;
    }
    return root;
}

static __attribute__((always_inline)) inline void join(unsigned a, unsigned b) {
    a = find_root(a);
    b = find_root(b);
    if (a != b) parent_node[a] = (short)b;
}

static __attribute__((always_inline)) inline i32 cell_coord(i64 value, i64 width) {
    i64 q = value / width;
    if (value < 0 && q * width != value) --q;
    return (i32)q;
}

static __attribute__((always_inline)) inline unsigned hash_cell(i32 x, i32 y, i32 z) {
    u32 h = (u32)x * 0x9e3779b1u;
    h ^= (u32)y * 0x85ebca6bu;
    h ^= (u32)z * 0xc2b2ae35u;
    h ^= h >> 16;
    return h & HASH_MASK;
}

static __attribute__((always_inline)) inline int lookup(i32 x, i32 y, i32 z) {
    unsigned slot = hash_cell(x, y, z);
    while (cell_stamp[slot] == epoch) {
        if (key_x[slot] == x && key_y[slot] == y && key_z[slot] == z)
            return cell_head[slot];
        slot = (slot + 1) & HASH_MASK;
    }
    return -1;
}

static __attribute__((always_inline)) inline void insert_point(i32 x, i32 y, i32 z,
                                                               unsigned index) {
    unsigned slot = hash_cell(x, y, z);
    while (cell_stamp[slot] == epoch) {
        if (key_x[slot] == x && key_y[slot] == y && key_z[slot] == z) {
            chain_next[index] = cell_head[slot];
            cell_head[slot] = (short)index;
            return;
        }
        slot = (slot + 1) & HASH_MASK;
    }
    cell_stamp[slot] = epoch;
    key_x[slot] = x;
    key_y[slot] = y;
    key_z[slot] = z;
    chain_next[index] = -1;
    cell_head[slot] = (short)index;
}

static __attribute__((always_inline)) inline int touches(unsigned a, unsigned b, u64 limit2) {
    i64 dx = (i64)point[a].x - point[b].x;
    u64 sum = (u64)(dx * dx);
    if (sum > limit2) return 0;
    i64 dy = (i64)point[a].y - point[b].y;
    u64 part = (u64)(dy * dy);
    if (part > limit2 - sum) return 0;
    sum += part;
    i64 dz = (i64)point[a].z - point[b].z;
    part = (u64)(dz * dz);
    return part <= limit2 - sum;
}

__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    const char *input = info->stdin_ptr;
    char *out = info->stdout_ptr;
    unsigned tests = (unsigned)duck_read_u64(&input);

    while (tests--) {
        unsigned n = (unsigned)duck_read_u64(&input);
        i64 height = (i64)duck_read_u64(&input);
        i64 radius = (i64)duck_read_u64(&input);
        i64 width = radius + radius;
        u64 limit2 = (u64)width * (u64)width;
        unsigned bottom = n, top = n + 1;
        int yes = 0;
        ++epoch;
        for (unsigned i = 0; i < n + 2; ++i) parent_node[i] = (short)i;

        for (unsigned i = 0; i < n; ++i) {
            i32 x = (i32)duck_read_i64(&input);
            i32 y = (i32)duck_read_i64(&input);
            i32 z = (i32)duck_read_i64(&input);
            if (yes) continue;
            point[i].x = x;
            point[i].y = y;
            point[i].z = z;
            if ((i64)z <= radius) join(i, bottom);
            if ((i64)z + radius >= height) join(i, top);

            i32 cx = cell_coord(x, width);
            i32 cy = cell_coord(y, width);
            i32 cz = cell_coord(z, width);
            for (i32 dz = -1; dz <= 1; ++dz)
                for (i32 dy = -1; dy <= 1; ++dy)
                    for (i32 dx = -1; dx <= 1; ++dx) {
                        int j = lookup(cx + dx, cy + dy, cz + dz);
                        while (j >= 0) {
                            if (touches(i, (unsigned)j, limit2)) join(i, (unsigned)j);
                            j = chain_next[j];
                        }
                    }
            insert_point(cx, cy, cz, i);
            yes = find_root(bottom) == find_root(top);
        }

        if (yes) {
            __builtin_memcpy(out, "Yes\n", 4);
            out += 4;
        } else {
            __builtin_memcpy(out, "No\n", 3);
            out += 3;
        }
    }

    info->stdout_size = (u64)(out - info->stdout_ptr);
    duck_exit();
}

int main(void) {}

评测结果