编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#46407 #1001. A. 神秘谜题 Compile Error 0 0 ms 0 K C++ 17 / 3.9 K 自动化钱001-徐启航 2020-09-20 21:26:40
显示原始代码
#include <iostream>

using namespace std;

struct Node {
    union {
        Node *s[2];
        struct {
            Node *l, *r;
        };
    };
    uint64_t v, len, n;
} * ROOT, data[100000];
int ptr = 0;

Node *alloc() { return &data[ptr++]; }

inline uint64_t get_len(uint64_t x) {
    uint64_t ret;
    asm("bsr %0, %1" : "=r"(ret) : "r"(x));
    return ret + 1;
}

inline uint64_t bsf(uint64_t x) {
    uint64_t ret;
    asm("bsf %0, %1" : "=r"(ret) : "r"(x));
    return ret;
}

void inc(Node *n) {
    uint64_t len = get_len(++n->v);
    if (len > n->len) {
        if (n->l || n->r)
            n->v = 0;
        if (n->l && n->r) {
            inc(n->l), inc(n->r);
        } else if (n->l) {
            inc(n->l);
            n->r = alloc();
            n->r->l = n->r->r = nullptr;
            n->r->v = n->r->len = 1;
            n->r->n = 1;
        } else if (n->r) {
            inc(n->r);
            n->l = alloc();
            n->l->l = n->l->r = nullptr;
            n->l->v = n->l->len = 1;
            n->l->n = 1;
        }
    }
}

uint64_t get_v(Node *n) {
    uint64_t vl = n->l ? get_v(n->l) : 0;
    uint64_t vr = n->r ? get_v(n->r) : 0;
    return ((vl ^ vr) << n->len) | ((n->n & 1) ? n->v : 0);
}

void insert_node(Node *n, uint64_t x) {
    if (n->v == x) {
        n->n++;
    } else {
        auto mlen = min(bsf(x ^ n->v), n->len);
        auto mix = n->v & ((1 << mlen) - 1);
        auto x2 = x >> mlen, v2 = n->v >> mlen;

        if (v2) {
            Node *n2 = alloc();
            n2->l = n->l, n2->r = n->r;
            n2->v = v2, n2->len = get_len(v2);
            n2->n = n->n;

            n->v = mix, n->len = mlen;
            n->s[v2 & 1] = n2, n->s[!(v2 & 1)] = nullptr;
            n->n++;

            if (x2) {
                Node *nx = alloc();
                nx->l = nx->r = nullptr;
                nx->v = x2, nx->len = get_len(x2);
                nx->n = 1;
                n->s[x2 & 1] = nx;
            }
        } else if (n->s[x2 & 1]) {
            insert_node(n->s[x2 & 1], x2);
        } else {
            Node *nx = alloc();
            nx->l = nx->r = nullptr;
            nx->v = x2, nx->len = get_len(x2);
            nx->n = 1;
            n->s[x2 & 1] = nx;
        }
    }
}

void insert(uint64_t x) {
    if (ROOT)
        insert_node(ROOT, x);
    else {
        ROOT = alloc();
        ROOT->l = ROOT->r = nullptr;
        ROOT->v = x, ROOT->len = get_len(x);
        ROOT->n = 1;
    }
}

// void trav(Node *n)
// {
//       cout << hex << n->v << dec << " (" << n->len << ", " << n->n << ") <" << endl;
//       if (n->l)
//             trav(n->l);
//       if (n->r)
//             trav(n->r);
//       cout << ">\n";
// }

int main() {
    int n;
    cin >> n;
    for (int _ = 0; _ < n; _++) {
        int op;
        uint64_t x;
        cin >> op;
        switch (op) {
            case 1:
                inc(ROOT);
                break;
            case 2:
                cin >> x;
                if (x != 0)
                    insert(x);
                break;
            default:
                break;
        }
        // trav(ROOT);
        cout << get_v(ROOT) << endl;
    }
}

编译信息

/sandbox/1/a.cpp: In function 'Node* alloc()':
/sandbox/1/a.cpp:21:15: error: reference to 'data' is ambiguous
       return &data[ptr++];
               ^~~~
In file included from /usr/include/c++/8/string:51,
                 from /usr/include/c++/8/bits/locale_classes.h:40,
                 from /usr/include/c++/8/bits/ios_base.h:41,
                 from /usr/include/c++/8/ios:42,
                 from /usr/include/c++/8/ostream:38,
                 from /usr/include/c++/8/iostream:39,
                 from /sandbox/1/a.cpp:1:
/usr/include/c++/8/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/8/bits/range_access.h:309:5: note:                 'template<class _Tp, unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/8/bits/range_access.h:299:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/8/bits/range_access.h:289:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/sandbox/1/a.cpp:16:11: note:                 'Node data [100000]'
 } * ROOT, data[100000];
           ^~~~