QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#325774#6961. XOR SubsequencegeorgeyucjrAC ✓76ms22196kbC++2017.9kb2024-02-11 22:25:492024-02-11 22:25:49

Judging History

你现在查看的是最新测评结果

  • [2024-02-11 22:25:49]
  • 评测
  • 测评结果：AC
  • 用时：76ms
  • 内存：22196kb
查看
  • [2024-02-11 22:25:49]
  • 提交

answer


# include <bits/stdc++.h>
# ifndef ONLINE_JUDGE
# define LOCAL
# endif
# if __cplusplus >= 201100LL
# else
# error Please use C++11 Or Higher CPP version
# endif
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using arr3 = std :: array < int, 3 >;
using arr4 = std :: array < int, 4 >;
using pii = std :: pair < int, int >;
# define rep(i, f, t, ...) for ( std :: decay < decltype ( f + t ) > :: type i = f, _END_##i = t, ##__VA_ARGS__; i <= _END_##i; ++i )
# define per(i, f, t, ...) for ( std :: decay < decltype ( f + t ) > :: type i = f, _END_##i = t, ##__VA_ARGS__; i >= _END_##i; --i )
# define emb emplace_back
# define pb push_back
# define mkp make_pair
# define FILEIO(filename) freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout)

# define INLINE_V inline
# define EXPR constexpr

template < class T, class U >
inline constexpr auto ceil ( T && x, U && y ) {
	return ( x > 0 ? ( x + y - 1 ) / y : x / y );
}

template < class T, class U >
inline constexpr auto floor ( T && x, U && y ) {
	return ( x > 0 ? x / y : ( x - y + 1 ) / y );
}

template < class T, class U >
inline constexpr auto divmod ( T && x, U && y ) {
	auto && q = floor ( x, y );
	return std :: pair { q, x - q * y };
}

# define ALL( vc ) std :: begin ( vc ), std :: end ( vc )

template < class T >
requires ( std :: is_signed_v < T > && std :: is_integral_v < T > )
INLINE_V constexpr static T inf = std :: numeric_limits < T > :: max ( ) >> 1;

template <std :: ranges :: forward_range R>
inline constexpr auto Sum ( R && r ) {
	return std :: accumulate ( std :: ranges :: begin ( r ), std :: ranges :: end ( r ), 0 );
}

template < std :: ranges :: forward_range R, typename T >
inline constexpr auto Sum ( R && r, T init) {
	return std :: accumulate ( std :: ranges :: begin ( r ), std :: ranges :: end ( r ), init );
}

template < std :: ranges :: forward_range R >
inline constexpr int SZ ( R && x ) { return std :: size ( x ); }

template < class Os, class T >
inline Os & operator << ( Os & os, T & t ) {
	for ( auto ele : t )
		os << ele << " ";
	os << "\n";
	return os;
}

# ifndef __GEORGEYUCJR_READ__
# define __GEORGEYUCJR_READ__

# define CHECK_EOF 0
# if CHECK_EOF
# define ECHK0 *ptr ? *ptr++ : -1
# define ECHK1                                                                                                                                        \
  if (ch == -1)                                                                                                                                      \
    return set(false), *this;
# define ECHK2                                                                                                                                        \
  if (!*ptr)                                                                                                                                         \
    return set(false), *this;
# define ECHK3 and ch != -1
# define ECHK4 and*ptr
# else
# define ECHK0 *ptr++
# define ECHK1
# define ECHK2
# define ECHK3
# define ECHK4
# endif

# if !defined(MACOS) && !defined(LOCAL)
# define USE_MMAP
# include <sys/mman.h>
# include <sys/stat.h>
# endif

# if CHECK_EOF || !defined(USE_MMAP)
# define EV -1
# else
# define EV 0
# endif

namespace FastIO {
template <typename T> struct make_unsigned : public std :: make_unsigned<T> {};
template <> struct make_unsigned<i128> {
	using type = u128;
};
template <typename T>
concept tupleLike = requires(T t) { std :: tuple_size_v<decltype(std :: tuple_cat(t))>; };

constexpr ull pw10(int t) { return t == 0 ? 1 : pw10(t - 1) * 10; }

std :: mt19937 mrand(std :: random_device{}());
std :: mt19937_64 mrand64(std :: random_device{}());

constexpr std :: size_t bufSize = 1 << 20;

class IO;
class In {
	friend class IO;

private:
	FILE *inFile;
	bool status = true;
# ifdef USE_MMAP
	struct stat st;
	char *ptr;
	int fd;
# elif !defined(LOCAL)
	char buf[bufSize], *p1, *p2;
# endif

public:
# ifdef LOCAL
	// inline int getch() { return fgetc_unlocked(inFile); }
	inline int getch ( ) {
		return _getchar_nolock();
	}
	inline void input(FILE *f) { inFile = f, set(); }
# elif defined(USE_MMAP)
	inline int getch() { return ECHK0; }
	inline void input(FILE *f) {
		inFile = f;
		if (inFile)
			fd = fileno(inFile), fstat(fd, &st), ptr = (char *)mmap(nullptr, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0), set();
	}
	static constexpr auto n = []() {
		std :: array<uint32_t, 0x10000> n{};
		for (int i = 0; i != 0x10000; ++i)
			n[i] = -1;
		constexpr uint32_t e0 = 0x01, e1 = 0x100;
		int x = 0;
		for (uint32_t i = 0, c0 = 0x3030; i != 10; i++, c0 += e0)
			for (uint32_t j = 0, c1 = c0; j != 10; j++, c1 += e1)
				n[c1] = x++;
		return n;
	}();
# else
	inline int getch() { return (p1 == p2 ? (p2 = (p1 = buf) + fread(buf, 1, bufSize, inFile)) : 0), p1 == p2 ? -1 : *p1++; }
	inline void input(FILE *f) { inFile = f, p1 = p2 = buf, set(); }
# endif
	inline void input(const char *s) { input(fopen(s, "rb")); }
	inline void set(bool s = true) { status = s; }
	inline bool get() const { return status; }
};
class Out {
	friend class IO;

public:
	FILE *outFile;
# ifndef LOCAL
	char pbuf[bufSize], *pp;
# endif

public:
# ifdef LOCAL
	inline void flush() { outFile ? fflush(outFile) : 0; }
	// inline void putch(char c) { fputc_unlocked(c, outFile); }
	inline void putch(const char&c) {
		_putchar_nolock(c);
	}
# else
	inline void flush() { (outFile ? fwrite(pbuf, 1, pp - pbuf, outFile), fflush(outFile) : 0), pp = pbuf; }
	inline void putch(char c) { ((pp - pbuf == bufSize) ? fwrite(pbuf, 1, bufSize, outFile), pp = pbuf : 0), *pp++ = c; }
# endif
	inline void output(const char *s) { flush(), outFile = fopen(s, "wb"); }
	inline void output(FILE *f) { flush(), outFile = f; }
};
class IO : public In, public Out {
private:
	std :: size_t precision = 12;

public:
	IO(FILE * = nullptr, FILE * = nullptr);
	~IO() { flush(); }
	static constexpr bool blank(char);
	template <typename... Args>
	requires(sizeof...(Args) > 1)
	IO &read(Args &...);
	template <typename T>
	requires(std :: is_signed_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, i128>
	IO &read(T &);
	template <typename T>
	requires(std :: is_unsigned_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, u128>
	IO &read(T &);
	template <typename T>
	requires std :: is_floating_point_v<T>
	IO &read(T &);
	template <typename T> T read();
	IO &read(char &);
	IO &read(char *);
	IO &read(std :: string &);
	IO &readline(char *);
	IO &readline(std :: string &);
	template <tupleLike T> IO &read(T &&);
	template <std :: ranges::input_range R> IO &read(R &&r) { return readArray(std :: forward<R>(r)); }
	void setprecision(std :: size_t n = 6u) { precision = n; }
	template <typename... Args>
	requires(sizeof...(Args) > 1)
	void write(Args &&...);
	inline void write() const {}
	template <typename T>
	requires(std :: is_signed_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, i128>
	void write(T);
	template <typename T>
	requires(std :: is_unsigned_v<T> && std :: is_integral_v<T>)
	void write(T);
	void write(u128);
	inline void write(char);
	template <typename T>
	requires std :: is_floating_point_v<T>
	void write(T);
	inline void write(bool);
	void write(char *);
	void write(const char *);
	void write(const std :: string &);
	template <typename T> void write(std :: initializer_list<T>);
	template <tupleLike T> void write(T &&);
	template <std :: ranges::input_range R> void write(R &&);
	template <typename... Args> void writeln(Args &&...);
	template <typename T> inline void writespc(T && x);
	operator bool() const { return get(); }
} io(stdin, stdout);
template <typename... Args> inline void writeln(Args &&...x) { io.writeln(std :: forward<Args>(x)...); }
template <typename T> inline void writeln(std :: initializer_list<T> x) { io.writeln(x); }
#pragma endregion

# define isdigit(x) ((x) >= '0' && (x) <= '9')
IO::IO(FILE *in, FILE *out) { input(in), output(out); }
constexpr bool IO::blank(char c) { return c == ' ' || c == '\n' || c == '\r'; }
template <typename... Args>
requires(sizeof...(Args) > 1)
IO &IO::read(Args &...args) {
	if constexpr (CHECK_EOF)
		(read(args) && ...);
	else
		(read(args), ...);
	return *this;
}
template <typename T>
requires(std :: is_signed_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, i128>
IO &IO::read(T &x) {
	x = 0;
	static typename make_unsigned<T>::type t;
	bool sign = false;
# ifndef USE_MMAP
	int ch = getch();
	while (!isdigit(ch) ECHK3)
		sign = (ch == '-'), ch = getch();
	ECHK1
	t = 0;
	while (isdigit(ch))
		t = t * 10 + (ch ^ 48), ch = getch();
# else
	while (!isdigit(*ptr) ECHK4)
		sign = *ptr++ == '-';
	ECHK2
	t = *ptr++ ^ 48;
	while (~n[*reinterpret_cast<std :: uint16_t *&>(ptr)])
		t = t * 100 + n[*reinterpret_cast<std :: uint16_t *&>(ptr)++];
	if (isdigit(*ptr))
		t = t * 10 + (*ptr++ ^ 48);
# endif
	x = sign ? (~t + 1) : t;
	return *this;
}
template <typename T>
requires(std :: is_unsigned_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, u128>
IO &IO::read(T &x) {
	x = 0;
# ifndef USE_MMAP
	int ch = getch();
	while (!isdigit(ch) ECHK3)
		ch = getch();
	ECHK1
	while (isdigit(ch))
		x = (x << 1) + (x << 3) + (ch ^ 48), ch = getch();
# else
	while (!isdigit(*ptr) ECHK4)
		ptr++;
	ECHK2
	x = *ptr++ ^ 48;
	while (~n[*reinterpret_cast<std :: uint16_t *&>(ptr)])
		x = x * 100 + n[*reinterpret_cast<std :: uint16_t *&>(ptr)++];
	if (isdigit(*ptr))
		x = x * 10 + (*ptr++ ^ 48);
# endif
	return *this;
}
template <typename T>
requires std :: is_floating_point_v<T>
IO &IO::read(T &x) {
	x = 0;
	T t = 1;
	bool sign = false;
	int ch = getch();
	while (!isdigit(ch) ECHK3)
		sign = (ch == '-'), ch = getch();
	ECHK1
	while (isdigit(ch))
		x = x * 10 + (ch ^ 48), ch = getch();
	if (ch == '.')
		for (ch = getch(); isdigit(ch); ch = getch())
			x += (t /= 10) * (ch ^ 48);
	x = sign ? -x : x;
	return *this;
}
template <typename T> T IO::read() {
	static std :: decay_t<T> x;
	return read(x), x;
}
IO &IO::read(char &ch) {
	do
		ch = getch();
	while (blank(ch));
	ECHK1
	return *this;
}
IO &IO::read(char *s) {
	int ch = getch();
	while (blank(ch))
		ch = getch();
	ECHK1
	while (!blank(ch) && ch != EV)
		*s++ = ch, ch = getch();
	*s = 0;
	return *this;
}
IO &IO::read(std :: string &s) {
	int ch = getch();
	while (blank(ch))
		ch = getch();
	ECHK1
	s.erase();
	while (!blank(ch) && ch != EV)
		s.append(1, ch), ch = getch();
	return *this;
}
IO &IO::readline(char *s) {
	char *t = s;
	int ch = getch();
	while (ch != '\n' && ch != EV)
		*s++ = ch, ch = getch();
	*s = 0;
	if (s == t && ch != '\n')
		set(false);
	return *this;
}
IO &IO::readline(std :: string &s) {
	s.erase();
	int ch = getch();
	while (ch != '\n' && ch != EV)
		s.append(1, ch), ch = getch();
	if (s.empty() && ch != '\n')
		set(false);
	return *this;
}
template <tupleLike T> IO &IO::read(T &&t) {
	std :: apply([&](auto & ...t) { (read(t), ...); }, t);
	return *this;
}
template <typename... Args>
requires(sizeof...(Args) > 1)
void IO::write(Args &&...args) {
	(write(std :: forward<Args>(args)), ...);
}
template <typename T>
requires(std :: is_signed_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, i128>
void IO::write(T x) {
	static typename make_unsigned<T>::type y;
	y = x;
	if (x < 0)
		putch('-'), write(~y + 1);
	else
		write(y);
}
constexpr auto D = []() {
	constexpr uint32_t e0 = 0x1, e1 = 0x100, e2 = 0x10000, e3 = 0x1000000;
	std :: array<uint32_t, 10000> m{};
	int x = 0;
	for (uint32_t i = 0, c0 = 0x30303030; i != 10; i++, c0 += e0)
		for (uint32_t j = 0, c1 = c0; j != 10; j++, c1 += e1)
			for (uint32_t k = 0, c2 = c1; k != 10; k++, c2 += e2)
				for (uint32_t l = 0, c3 = c2; l != 10; l++, c3 += e3)
					m[x++] = c3;
	return m;
}();
template <typename T>
requires(std :: is_unsigned_v<T> && std :: is_integral_v<T>)
void IO::write(T x) {
# ifndef LOCAL
	if (std :: end(pbuf) - pp < 64)
		flush();

	auto L = [&](int x) { return x == 1 ? 0 : pw10(x - 1); };
	auto R = [&](int x) { return pw10(x) - 1; };

# define de(t)                                                                                                                                        \
  case L(t)... R(t):                                                                                                                                 \
    *reinterpret_cast<uint32_t *>(pp) = D[x / pw10((t)-4)];                                                                                          \
    pp += 4;                                                                                                                                         \
    x %= pw10((t)-4);

	ull y = x;
	switch (y) {
		de(18);
		de(14);
		de(10);
		de(6);
	case L(2)... R(2):
		*reinterpret_cast<uint32_t *>(pp) = D[x * 100];
		pp += 2;
		break;

		de(17);
		de(13);
		de(9);
		de(5);
	case L(1)... R(1):
		*pp = static_cast<char>('0' + x);
		pp += 1;
		break;

	default:
		*reinterpret_cast<uint32_t *>(pp) = D[x / pw10(16)];
		pp += 4;
		x %= pw10(16);
		de(16);
		de(12);
		de(8);
	case L(4)... R(4):
		*reinterpret_cast<uint32_t *>(pp) = D[x];
		pp += 4;
		break;

		de(19);
		de(15);
		de(11);
		de(7);
	case L(3)... R(3):
		*reinterpret_cast<uint32_t *>(pp) = D[x * 10];
		pp += 3;
		break;
	}
# else
	write(u128(x));
# endif
}
constexpr u128 _pw10(int x) { return x == 0 ? 1 : _pw10(x - 1) * 10; }
void IO::write(u128 x) {
# ifndef LOCAL
	if (std :: end(pbuf) - pp < 64)
		flush();
	constexpr auto pw10 = _pw10;
	auto L = [&](int x) { return x == 1 ? 0 : pw10(x - 1); };
	auto R = [&](int x) { return pw10(x) - 1; };

# define de(t)                                                                                                                                        \
  case L(t)... R(t):                                                                                                                                 \
    *reinterpret_cast<uint32_t *>(pp) = D[x / pw10((t)-4)];                                                                                          \
    pp += 4;                                                                                                                                         \
    x %= pw10((t)-4);

	switch (x) {
		de(38);
		de(34);
		de(30);
		de(26);
		de(22);
		de(18);
		de(14);
		de(10);
		de(6);
	case L(2)... R(2):
		*reinterpret_cast<uint32_t *>(pp) = D[x * 100];
		pp += 2;
		break;

		de(37);
		de(33);
		de(29);
		de(25);
		de(21);
		de(17);
		de(13);
		de(9);
		de(5);
	case L(1)... R(1):
		*pp = static_cast<char>('0' + x);
		pp += 1;
		break;

		de(36);
		de(32);
		de(28);
		de(24);
		de(20);
		de(16);
		de(12);
		de(8);
	case L(4)... R(4):
		*reinterpret_cast<uint32_t *>(pp) = D[x];
		pp += 4;
		break;

	default:
		*reinterpret_cast<uint32_t *>(pp) = D[x / pw10(35)];
		pp += 4;
		x %= pw10(35);
		de(35);
		de(31);
		de(27);
		de(23);
		de(19);
		de(15);
		de(11);
		de(7);
	case L(3)... R(3):
		*reinterpret_cast<uint32_t *>(pp) = D[x * 10];
		pp += 3;
		break;
	}
# else
	auto _ = x;
	uint8_t cnt = 0;
	static char stk[45];
	while (_) {
		stk[cnt++] = '0' + _ % 10;
		_ /= 10;
	}
	for (int i = cnt - 1; ~i; --i) putch(stk[i]);
# endif
}
void IO::write(bool x) { putch(x ^ 48); }
void IO::write(char c) { putch(c); }
template <typename T>
requires std :: is_floating_point_v<T>
void IO::write(T x) {
	static char buf[512];
	*std :: to_chars(buf, buf + 512, x, std :: chars_format::fixed, precision).ptr = 0;
	write(buf);
}
void IO::write(char *s) {
	while (*s)
		putch(*s++);
}
void IO::write(const char *s) {
	while (*s)
		putch(*s++);
}
void IO::write(const std :: string &s) { write(s.data()); }
template <typename T> void IO::write(std :: initializer_list<T> t) {
	auto first = std :: begin(t), last = std :: end(t);
	if (first != last)
		for (write(*first++); first != last; ++first) {
			putch(' ');
			write(*first);
		}
}
template <tupleLike T> void IO::write(T &&t) {
	[&]<std :: size_t... I>(std :: index_sequence<I...>) {
		(..., (I == 0 ? void(0) : putch(' '), write(std :: get<I>(t))));
	}(std :: make_index_sequence<std :: tuple_size_v<std :: remove_reference_t<T>>>());
}
template <std :: ranges::input_range R> void IO::write(R &&r) {
	if constexpr (std :: is_same_v<std :: decay_t<R>, std :: string>)
		return write(r.data());
	auto first = std :: ranges::begin(r), last = std :: ranges::end(r);
	if (first != last)
		for (write(*first++); first != last; ++first) {
			putch(' ');
			write(*first);
		}
}
template <typename... Args> void IO::writeln(Args &&...x) { write(std :: forward<Args>(x)...), putch('\n'); }
template <typename T> inline void IO::writespc(T && x) { write(x), putch(' '); }
} // namespace FastIO
using namespace FastIO;
# endif
using namespace std;

# warning Do not use debug.hpp.

INLINE_V constexpr static int N = 1e6 + 5;

int n, a[N], ans[33], num = 0, s[N];
bool st[33];

signed main() {
	int T; io.read (T); auto slv = [&]() {
		io.read(n);
		rep (i, 1, (1 << n) - 1) io.read(a[i]);
		sort (a + 1, a + (1 << n));
		num = 0;
		for (int i = 1; i < (1 << n); i <<= 1) ans[num++] = a[i];
		auto chk = [&]() -> bool {
			int len = 1;
			rep (i, 1, (1 << n) - 1) {
				auto f = [&](int x) {
					int res = 0;
					rep (i, 0, n - 1) if (x & (1 << i)) res ^= ans[i];
					return res;
				};
				s[len++] = f(i);
			}
			sort (s + 1, s + len);
			rep (i, 1, (1 << n) - 1) if (s[i] != a[i]) return false;
			return true;
		};
		if (chk()) {
			rep (i, 0, n - 1) io.writespc(ans[i]);
			io.writeln("");
		} else io.writeln("-1");
	}; while (T--) slv ();

# ifdef LOCAL
	cerr << format ( "Spend Time : {} ms \n", clock ( ) * 1. );
# endif
	return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 76ms
memory: 22196kb

input:

4115
1
220426753
2
75752216 139004411 214624995
3
425320853 659634699 1040767902 61426054 620262285 1033998872 451979283
4
289669156 16842978 272957638 16779852 289737354 21236708 4456872 268501358 285213068 272894568 4524806 21299530 68270 285281058 268438464
5
288507119 704365180 764545802 9869220...

output:

220426753 
75752216 139004411 
61426054 425320853 620262285 
68270 4456872 16779852 268438464 
25699612 34220493 74041718 280650227 678684512 
-1
0 0 0 67108864 134217728 268435456 536870912 
136604 6052763 27897018 37591031 75573769 136661209 279830679 547648454 
2026397 2791316 8827893 17803262 38...

result:

ok 4115 lines
English 繁體中文 简体中文

伺服器時間: 2024-11-30 18:52:40 | 開源專案