QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #449132 | #6. 玛里苟斯 | NOI_AK_ME | Compile Error | / | / | C++23 | 11.8kb | 2024-06-20 18:31:18 | 2024-06-20 18:31:19 |
Judging History
answer
#include <algorithm>
#include <bit>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#ifndef __OY_HAMELXORBASE__
#define __OY_HAMELXORBASE__
namespace OY {
namespace HAMEL {
template <typename Tp, uint32_t MAX_WIDTH>
struct MaskNodes {
Tp m_val[MAX_WIDTH];
Tp &operator[](uint32_t index) { return m_val[index]; }
Tp operator[](uint32_t index) const { return m_val[index]; }
uint32_t count() const {
return std::count_if(m_val, m_val + MAX_WIDTH, [&](Tp x) { return x; });
}
};
template <typename Tp>
struct MaskNodes<Tp, 0> {
static uint32_t s_width;
std::vector<Tp> m_val = std::vector<Tp>(s_width);
Tp &operator[](uint32_t index) { return m_val[index]; }
Tp operator[](uint32_t index) const { return m_val[index]; }
uint32_t count() const {
return std::count_if(m_val.begin(), m_val.end(), [&](Tp x) { return x; });
}
};
template <typename Tp>
uint32_t MaskNodes<Tp, 0>::s_width = sizeof(Tp) << 3;
template <typename Tp, uint32_t MAX_WIDTH>
struct HamelXorBase {
MaskNodes<Tp, MAX_WIDTH> m_masks;
static void set_width(uint32_t w) {
static_assert(!MAX_WIDTH, "MAX_WIDTH Must Be 0");
MaskNodes<Tp, MAX_WIDTH>::s_width = w;
}
static constexpr uint32_t width() {
if constexpr (MAX_WIDTH)
return MAX_WIDTH;
else
return MaskNodes<Tp, MAX_WIDTH>::s_width;
}
template <typename Callback>
void _dfs(uint32_t index, Tp mask, const std::vector<uint32_t> &next, Callback &&call) const {
uint32_t i = next[index];
if (~i)
_dfs(i, mask, next, call), _dfs(i, mask ^ m_masks[i], next, call);
else
call(mask);
}
HamelXorBase() = default;
HamelXorBase(Tp mask) : m_masks{} { insert(mask); }
uint32_t insert(Tp mask) {
for (uint32_t i = std::bit_width(mask) - 1; mask && ~i; i--)
if (mask >> i & 1)
if (!m_masks[i]) {
m_masks[i] = mask;
return i;
} else
mask ^= m_masks[i];
return -1;
}
bool contains(Tp mask) const {
for (uint32_t i = std::bit_width(mask) - 1; mask && ~i; i--)
if (m_masks[i] && (mask >> i & 1)) mask ^= m_masks[i];
return !mask;
}
uint32_t base_count() const { return m_masks.count(); }
Tp total_count() const { return Tp(1) << base_count(); }
Tp kth(Tp k, Tp base = 0) const {
Tp cnt = total_count(), ans = base;
for (uint32_t i = width() - 1; cnt > 1 && ~i; i--)
if (m_masks[i]) {
cnt >>= 1;
if (k >= cnt) {
if ((ans ^ m_masks[i]) > ans) ans ^= m_masks[i];
k -= cnt;
} else if ((ans ^ m_masks[i]) < ans)
ans ^= m_masks[i];
}
return ans;
}
Tp kth_in_total(Tp k, const Tp &total, Tp base = 0) const {
Tp cnt = total, ans = base;
for (uint32_t i = width() - 1; cnt > 1 && ~i; i--)
if (m_masks[i]) {
cnt >>= 1;
if (k >= cnt) {
if ((ans ^ m_masks[i]) > ans) ans ^= m_masks[i];
k -= cnt;
} else if ((ans ^ m_masks[i]) < ans)
ans ^= m_masks[i];
}
return ans;
}
Tp rank(Tp mask) const {
Tp cnt = total_count(), ans = 0;
for (uint32_t i = width() - 1; ~i; i--)
if (m_masks[i]) {
cnt >>= 1;
if (mask >> i & 1) ans += cnt;
}
return ans;
}
Tp rank_in_total(Tp mask, const Tp &total) const {
Tp cnt = total, ans = 0;
for (uint32_t i = width() - 1; ~i; i--)
if (m_masks[i]) {
cnt >>= 1;
if (mask >> i & 1) ans += cnt;
}
return ans;
}
template <typename Callback>
void enumerate(Callback &&call) const {
std::vector<uint32_t> next(width() + 1, -1);
for (uint32_t lst = width(), i = width() - 1; ~i; i--)
if (m_masks[i]) next[lst] = i, lst = i;
_dfs(width(), 0, next, call);
}
bool is_bonded(uint32_t k1, uint32_t k2) const {
for (uint32_t i = std::min(k1, k2); i != width(); i++)
if ((m_masks[i] >> k1 & 1) != (m_masks[i] >> k2 & 1)) return false;
return true;
}
Tp query_max_bitxor(Tp base = 0) const {
Tp ans = base;
for (uint32_t i = width() - 1; ~i; i--)
if ((ans ^ m_masks[i]) > ans) ans ^= m_masks[i];
return ans;
}
HamelXorBase<Tp, MAX_WIDTH> &operator+=(const HamelXorBase<Tp, MAX_WIDTH> &rhs) {
for (uint32_t i = 0; i != width(); i++)
if (rhs.m_masks[i]) insert(rhs.m_masks[i]);
return *this;
}
friend HamelXorBase<Tp, MAX_WIDTH> operator+(const HamelXorBase<Tp, MAX_WIDTH> &a, const HamelXorBase<Tp, MAX_WIDTH> &b) { return HamelXorBase<Tp, MAX_WIDTH>(a) += b; }
};
}
template <uint32_t MAX_WIDTH, typename = typename std::enable_if<MAX_WIDTH>::type>
using StaticHamelXorBase32 = HAMEL::HamelXorBase<uint32_t, MAX_WIDTH>;
template <uint32_t MAX_WIDTH, typename = typename std::enable_if<MAX_WIDTH>::type>
using StaticHamelXorBase64 = HAMEL::HamelXorBase<uint64_t, MAX_WIDTH>;
using DynamicHamelXorBase32 = HAMEL::HamelXorBase<uint32_t, 0>;
using DynamicHamelXorBase64 = HAMEL::HamelXorBase<uint64_t, 0>;
}
#endif
using u8 = unsigned char;
using u16 = unsigned short;
constexpr std::size_t buf_def_size = 262144;
constexpr std::size_t buf_flush_threshold = 32;
constexpr std::size_t string_copy_threshold = 512;
constexpr u64 E16 = 1e16, E12 = 1e12, E8 = 1e8, E4 = 1e4;
struct _io_t {
int t_o[10000];
constexpr _io_t() {
for (int e0 = (48 << 0), j = 0; e0 < (58 << 0); e0 += (1 << 0)) {
for (int e1 = (48 << 8); e1 < (58 << 8); e1 += (1 << 8)) {
for (int e2 = (48 << 16); e2 < (58 << 16); e2 += (1 << 16)) {
for (int e3 = (48 << 24); e3 < (58 << 24); e3 += (1 << 24)) {
t_o[j++] = e0 ^ e1 ^ e2 ^ e3;
}
}
}
}
}
void get(char *s, u32 p)const {
*((int *)s) = t_o[p];
}
};
constexpr _io_t _iot = {};
struct Qinf {
explicit Qinf(FILE *fi): f(fi) {
auto fd = fileno(f);
fstat(fd, &Fl);
bg = (char *)mmap(0, Fl.st_size + 1, PROT_READ, MAP_PRIVATE, fd, 0);
p = bg, ed = bg + Fl.st_size;
madvise(bg, Fl.st_size + 1, MADV_SEQUENTIAL);
}
~Qinf() {
munmap(bg, Fl.st_size + 1);
}
template<std::unsigned_integral T>Qinf &operator>>(T &x) {
skip_space(), x = 0;
for (; *p > ' '; ++p) {
x = x * 10 + (*p & 15);
}
return *this;
}
u32 rgc() {
skip_space();
return *p++ -'0';
}
private:
void skip_space() {
while (*p <= ' ') {
++p;
}
}
FILE *f;
char *bg, *ed, *p;
struct stat Fl;
} qin(stdin);
struct Qoutf {
explicit Qoutf(FILE *fi, std::size_t sz = buf_def_size): f(fi), bg(new char[sz]),
ed(bg + sz - buf_flush_threshold), p(bg) {}
~Qoutf() {
flush();
delete[] bg;
}
void flush() {
fwrite_unlocked(bg, 1, p - bg, f), p = bg;
}
Qoutf &operator<<(u32 x) {
if (x >= E8) {
put2(x / E8), x %= E8, putb(x / E4), putb(x % E4);
} else if (x >= E4) {
put4(x / E4), putb(x % E4);
} else {
put4(x);
}
chk();
return *this;
}
Qoutf &operator<<(u64 x) {
if (x >= E8) {
u64 q0 = x / E8, r0 = x % E8;
if (x >= E16) {
u64 q1 = q0 / E8, r1 = q0 % E8;
put4(q1), putb(r1 / E4), putb(r1 % E4);
} else if (x >= E12) {
put4(q0 / E4), putb(q0 % E4);
} else {
put4(q0);
}
putb(r0 / E4), putb(r0 % E4);
} else {
if (x >= E4) {
put4(x / E4), putb(x % E4);
} else {
put4(x);
}
}
chk();
return *this;
}
Qoutf &operator<<(char ch) {
*p++ = ch;
return *this;
}
private:
void putb(u32 x) {
_iot.get(p, x), p += 4;
}
void put4(u32 x) {
if (x > 99) {
if (x > 999) {
putb(x);
} else {
_iot.get(p, x * 10), p += 3;
}
} else {
put2(x);
}
}
void put2(u32 x) {
if (x > 9) {
_iot.get(p, x * 100), p += 2;
} else {
*p++ = x + '0';
}
}
void chk() {
if (p > ed)
[[unlikely]] {
flush();
}
}
FILE *f;
char *bg, *ed, *p;
} qout(stdout);
#define endl '\n'
#define cin qin
#define cout qout
static constexpr uint32_t N = 100000;
int main() {
uint64_t n, K;
cin >> n >> K;
if (K == 1) {
uint64_t sum = 0;
for (uint32_t i = 0; i < n; i++) {
uint64_t x;
cin >> x;
sum |= x;
}
cout << sum / 2;
if (sum & 1) cout << ".5";
} else if (K == 2) {
OY::StaticHamelXorBase32<32> hxb{};
uint32_t sum = 0;
for (uint32_t i = 0; i < n; i++) {
uint32_t x;
cin >> x;
hxb.insert(x);
sum |= x;
}
uint64_t ans = 0;
for (uint32_t j1 = 0; j1 < 32; j1++)
if (sum >> j1 & 1)
for (uint32_t j2 = 0; j2 < 32; j2++)
if (sum >> j2 & 1)
if (hxb.is_bonded(j1, j2))
ans += uint64_t(1) << (j1 + j2);
else
ans += uint64_t(1) << (j1 + j2 - 1);
cout << ans / 2;
if (ans & 1) cout << ".5";
} else {
OY::StaticHamelXorBase32<21> hxb{};
for (uint32_t i = 0; i < n; i++) {
uint32_t x;
cin >> x;
hxb.insert(x);
}
uint32_t tot = hxb.total_count();
__uint128_t ans = 0;
hxb.enumerate([&](uint32_t mask) {
__uint128_t prod = 1;
for (uint32_t j = 0; j < K; j++) prod *= mask;
ans += prod;
});
cout << uint64_t(ans / tot);
if (ans % tot) cout << ".5";
}
}
詳細信息
answer.code:161:11: error: ‘u64’ does not name a type
161 | constexpr u64 E16 = 1e16, E12 = 1e12, E8 = 1e8, E4 = 1e4;
| ^~~
answer.code:175:23: error: ‘u32’ has not been declared
175 | void get(char *s, u32 p)const {
| ^~~
answer.code:200:5: error: ‘u32’ does not name a type
200 | u32 rgc() {
| ^~~
answer.code:212:17: error: field ‘Fl’ has incomplete type ‘stat’
212 | struct stat Fl;
| ^~
answer.code:212:12: note: forward declaration of ‘struct stat’
212 | struct stat Fl;
| ^~~~
answer.code: In constructor ‘Qinf::Qinf(FILE*)’:
answer.code:183:9: error: ‘fstat’ was not declared in this scope; did you mean ‘stat’?
183 | fstat(fd, &Fl);
| ^~~~~
| stat
answer.code:184:46: error: ‘PROT_READ’ was not declared in this scope
184 | bg = (char *)mmap(0, Fl.st_size + 1, PROT_READ, MAP_PRIVATE, fd, 0);
| ^~~~~~~~~
answer.code:184:57: error: ‘MAP_PRIVATE’ was not declared in this scope
184 | bg = (char *)mmap(0, Fl.st_size + 1, PROT_READ, MAP_PRIVATE, fd, 0);
| ^~~~~~~~~~~
answer.code:184:22: error: ‘mmap’ was not declared in this scope
184 | bg = (char *)mmap(0, Fl.st_size + 1, PROT_READ, MAP_PRIVATE, fd, 0);
| ^~~~
answer.code:186:37: error: ‘MADV_SEQUENTIAL’ was not declared in this scope
186 | madvise(bg, Fl.st_size + 1, MADV_SEQUENTIAL);
| ^~~~~~~~~~~~~~~
answer.code:186:9: error: ‘madvise’ was not declared in this scope
186 | madvise(bg, Fl.st_size + 1, MADV_SEQUENTIAL);
| ^~~~~~~
answer.code: In destructor ‘Qinf::~Qinf()’:
answer.code:189:9: error: ‘munmap’ was not declared in this scope
189 | munmap(bg, Fl.st_size + 1);
| ^~~~~~
answer.code: At global scope:
answer.code:224:23: error: ‘u32’ has not been declared
224 | Qoutf &operator<<(u32 x) {
| ^~~
answer.code:236:23: error: ‘u64’ has not been declared
236 | Qoutf &operator<<(u64 x) {
| ^~~
answer.code:236:12: error: ‘Qoutf& Qoutf::operator<<(int)’ cannot be overloaded with ‘Qoutf& Qoutf::operator<<(int)’
236 | Qoutf &operator<<(u64 x) {
| ^~~~~~~~
answer.code:224:12: note: previous declaration ‘Qoutf& Qoutf::operator<<(int)’
224 | Qoutf &operator<<(u32 x) {
| ^~~~~~~~
answer.code:266:15: error: ‘u32’ has not been declared
266 | void putb(u32 x) {
| ^~~
answer.code:269:15: error: ‘u32’ has not been declared
269 | void put4(u32 x) {
| ^~~
answer.code:280:15: error: ‘u32’ has not been declared
280 | void put2(u32 x) {
| ^~~
answer.code: In member function ‘Qoutf& Qoutf::operator<<(int)’:
answer.code:225:18: error: ‘E8’ was not declared in this scope; did you mean ‘u8’?
225 | if (x >= E8) {
| ^~
| u8
answer.code:226:45: error: ‘E4’ was not declared in this scope
226 | put2(x / E8), x %= E8, putb(x / E4), putb(x % E4);
| ^~
answer.code:227:25: error: ‘E4’ was not declared in this scope
227 | } else if (x >= E4) {
| ^~
answer.code: In member function ‘Qoutf& Qoutf::operator<<(int)’:
answer.code:237:18: error: ‘E8’ was not declared in this scope; did you mean ‘u8’?
237 | if (x >= E8) {
| ^~
| u8
answer.code:238:13: error: ‘u64’ was not declared in this scope
238 | u64 q0 = x / E8, r0 = x % E8;
| ^~~
answer.code:240:22: error: ‘E16’ was not declared in this scope; did you mean ‘u16’?
240 | if (x >= E16) {
| ^~~
| u16
answer.code:241:21: error: expected ‘;’ before ‘q1’
241 | u64 q1 = q0 / E8, r1 = q0 % E8;
| ^~
answer.code:242:22: error: ‘q1’ was not declared in this scope; did you mean ‘y1’?
242 | put4(q1), putb(r1 / E4), putb(r1 % E4);
| ^~
| y1
answer.code:242:32: error: ‘r1’ was not declared in this scope; did you mean ‘y1’?
242 | put4(q1), putb(r1 / E4), putb(r1 % E4);
| ^~
| y1
answer.code:242:37: error: ‘E4’ was not declared in this scope
242 | put4(q1), putb(r1 / E4), putb(r1 % E4);
| ^~
answer.code:243:29: error: ‘E12’ was not declared in this scope
243 | } else if (x >= E12) {
| ^~~
answer.code:244:22: error: ‘q0’ was not declared ...