编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#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];
^~~~