QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #239732 | #7688. Alea Iacta Est | ucup-team197# | TL | 192ms | 112060kb | C++20 | 18.7kb | 2023-11-04 22:49:08 | 2023-11-04 22:49:08 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2")
// <io.hpp>
#include <array>
#include <limits>
// <local_assertion.hpp>
#include <iostream>
#ifdef ENABLE_DEBUG
#define LOCAL_ASSERT(condition, message) \
do { \
if (!(condition)) { \
std::cerr << "Assertion (" << #condition << ") failed\non line " \
<< __LINE__ << " in " << __FILE__ << '#' << __FUNCTION__ \
<< "()\n"; \
std::cerr << message << '\n'; \
abort(); \
} \
} while (0)
#else
#define LOCAL_ASSERT(...) \
do { \
} while (0)
#endif
#define LOCAL_ASSERT_IN_RANGE(variable, low, high) \
LOCAL_ASSERT(low <= variable && variable <= high, \
#variable << '=' << variable << " is out of the range " \
<< '[' << low << ", " << high << ']')
// </local_assertion.hpp>
#include <variant>
// <io/BufferedInput.hpp>
#ifdef _WIN32
#include <windows.h>
#else
#include <fcntl.h>
#include <unistd.h>
#endif
#include <cstdio>
#include <cstring>
#include <memory>
// <ints.hpp>
#include <cstddef>
#include <cstdint>
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
#ifdef __SIZEOF_INT128__
using i128 = __int128_t;
using u128 = __uint128_t;
#endif
using isize = std::ptrdiff_t;
using usize = std::size_t;
// </ints.hpp>
template <usize buffer_size>
struct BufferedInput {
std::unique_ptr<char[]> buffer;
const char *cursor;
usize len;
BufferedInput() : buffer(std::make_unique<char[]>(buffer_size)), cursor(buffer.get()), len(0) {
#ifdef _WIN32
HANDLE stdin_handle = GetStdHandle(STD_INPUT_HANDLE);
DWORD mode;
if (GetConsoleMode(stdin_handle, &mode)) {
if (!SetConsoleMode(stdin_handle, mode & ~ENABLE_LINE_INPUT & ~ENABLE_ECHO_INPUT)) {
std::cerr << "failed setting console mode: " << GetLastError() << '\n';
}
} else {
std::cerr << "failed getting current console mode: " << GetLastError() << '\n';
}
#else
int flags = fcntl(STDIN_FILENO, F_GETFL, 0);
fcntl(STDIN_FILENO, F_SETFL, flags | O_NONBLOCK);
#endif
refill();
}
BufferedInput(const BufferedInput &) = delete;
BufferedInput(BufferedInput &&other) : buffer(std::move(other.buffer)), cursor(other.cursor), len(other.len) {
other.cursor = nullptr;
other.len = 0;
}
auto operator=(const BufferedInput &) -> BufferedInput & = delete;
auto operator=(BufferedInput &&other) -> BufferedInput & = delete;
~BufferedInput() {
if (buffer) {
#ifdef ENABLE_DEBUG
refill();
#endif
LOCAL_ASSERT(cursor == buffer.get() + len || (cursor + 1 == buffer.get() + len && *cursor == '\n'),
"Input buffer not fully consumed");
}
}
enum class RefillState { OK, WAITING, AT_EOF };
RefillState refill() {
std::memmove(buffer.get(), cursor, buffer.get() + len - cursor);
len -= cursor - buffer.get();
cursor = buffer.get();
std::size_t amt = std::fread(buffer.get() + len, 1, buffer_size - len, stdin);
if (amt) {
len += amt;
return RefillState::OK;
} else if (std::feof(stdin)) {
return RefillState::AT_EOF;
} else {
return RefillState::WAITING;
}
}
auto get_buffer(usize n) -> std::pair<const char *, usize> {
if (cursor + n > buffer.get() + len) {
RefillState state;
do {
state = refill();
} while (cursor == buffer.get() + len && state == RefillState::WAITING);
LOCAL_ASSERT(cursor != buffer.get() + len, "requested input beyond EOF");
}
auto remain_len = buffer.get() + len - cursor;
return {cursor, remain_len};
}
auto consume(usize n) -> void {
LOCAL_ASSERT(cursor + n <= buffer.get() + len, "Input buffer overflow");
cursor += n;
}
};
// </io/BufferedInput.hpp>
// <io/BufferedOutput.hpp>
#include <cstdio>
#include <cstring>
template <usize buffer_size>
struct BufferedOutput {
char buffer[buffer_size];
char *cursor;
BufferedOutput() : cursor(buffer) {}
~BufferedOutput() { flush(); }
BufferedOutput(const BufferedOutput &) = delete;
BufferedOutput(BufferedOutput &&other) {
setvbuf(stdout, NULL, _IONBF, 0);
std::memcpy(buffer, other.buffer, other.cursor - other.buffer);
cursor = buffer + (other.cursor - other.buffer);
}
BufferedOutput &operator=(const BufferedOutput &) = delete;
BufferedOutput &operator=(BufferedOutput &&other) = delete;
void flush() {
LOCAL_ASSERT_IN_RANGE(cursor - buffer, 0, buffer_size);
std::fwrite(buffer, 1, cursor - buffer, stdout);
cursor = buffer;
}
void write(const char *s, usize len) {
if (cursor + len > buffer + buffer_size) {
flush();
if (len > buffer_size) {
std::fwrite(s, 1, len, stdout);
return;
}
}
std::memcpy(cursor, s, len);
cursor += len;
}
void write(char c) {
if (cursor == buffer + buffer_size) flush();
*cursor++ = c;
}
};
// </io/BufferedOutput.hpp>
// <io/MemoryMappedInput.hpp>
#include <cerrno>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <optional>
#include <utility>
#ifdef _WIN32
#include <Windows.h>
#else
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#endif
struct MemoryMappedInput {
const char *stdin_buffer;
const char *cursor;
usize len;
#ifdef _WIN32
HANDLE stdin_mapping;
#endif
static auto create() -> std::optional<MemoryMappedInput> {
auto fail = [](auto... args) -> std::optional<MemoryMappedInput> {
std::fprintf(stderr, args...);
std::fflush(stderr);
return std::nullopt;
};
#ifdef _WIN32
HANDLE stdin_handle = GetStdHandle(STD_INPUT_HANDLE);
if (stdin_handle == INVALID_HANDLE_VALUE) {
return fail("Error: GetStdHandle failed: %d\n", GetLastError());
}
DWORD dwFileSizeHigh = 0;
DWORD dwFileSizeLow = GetFileSize(stdin_handle, &dwFileSizeHigh);
if (dwFileSizeLow == INVALID_FILE_SIZE) {
return fail("Error: GetFileSize failed: %d\n", GetLastError());
}
usize len = usize(dwFileSizeLow + (u64(dwFileSizeHigh) << 32));
HANDLE stdin_mapping =
CreateFileMapping(stdin_handle, nullptr, PAGE_READONLY,
dwFileSizeHigh, dwFileSizeLow, nullptr);
if (stdin_mapping == nullptr) {
return fail("Error: CreateFileMapping failed: %d\n",
GetLastError());
}
const char *stdin_buffer = static_cast<const char *>(
MapViewOfFile(stdin_mapping, FILE_MAP_READ, 0, 0, len));
if (stdin_buffer == nullptr) {
auto err = GetLastError();
CloseHandle(stdin_mapping);
return fail("Error: MapViewOfFile failed: %d\n", err);
}
#else
u32 stat_err;
struct stat stat;
stat_err = fstat(STDIN_FILENO, &stat);
if (stat_err != 0) {
return fail("Error: fstat failed: %d\n", stat_err);
}
usize len = usize(stat.st_size);
const char *stdin_buffer = static_cast<const char *>(
mmap(nullptr, len, PROT_READ, MAP_PRIVATE, 0, 0));
if (stdin_buffer == MAP_FAILED) {
return fail("Error: mmap failed: %d\n", errno);
}
#endif
return MemoryMappedInput{stdin_buffer, len};
}
MemoryMappedInput(const char *stdin_buffer, usize len)
: stdin_buffer(stdin_buffer), cursor(stdin_buffer), len(len) {}
MemoryMappedInput(const MemoryMappedInput &) = delete;
MemoryMappedInput(MemoryMappedInput &&other)
: stdin_buffer(other.stdin_buffer),
cursor(other.cursor),
len(other.len) {
other.stdin_buffer = nullptr;
other.cursor = nullptr;
other.len = 0;
#ifdef _WIN32
other.stdin_mapping = nullptr;
#endif
}
auto operator=(const MemoryMappedInput &) -> MemoryMappedInput & = delete;
auto operator=(MemoryMappedInput &&other) -> MemoryMappedInput & = delete;
~MemoryMappedInput() {
if (stdin_buffer != nullptr) {
/*
LOCAL_ASSERT(cursor == stdin_buffer + len ||
(cursor + 1 == stdin_buffer + len && *cursor ==
'\n'), "Input not fully consumed");
*/
#ifdef _WIN32
UnmapViewOfFile(stdin_buffer);
CloseHandle(stdin_mapping);
#else
munmap(const_cast<char *>(stdin_buffer), len);
#endif
}
}
auto get_buffer([[maybe_unused]] usize n) const
-> std::pair<const char *, usize> {
auto remain_len = static_cast<usize>(stdin_buffer + len - cursor);
LOCAL_ASSERT(remain_len != 0, "Input buffer empty");
return {cursor, remain_len};
}
auto consume(usize n) -> void {
LOCAL_ASSERT(cursor + n <= stdin_buffer + len, "Input buffer overflow");
cursor += n;
}
};
// </io/MemoryMappedInput.hpp>
template <class T>
static constexpr auto base10_max_len() {
static_assert(std::is_integral_v<T>);
return usize(sizeof(T) * 8 * .302 + 2);
}
template <class Reader, class T, class = void>
struct InputImpl {};
template <class Writer, class T, class = void>
struct OutputImpl {};
struct IO {
static constexpr usize buffer_size = 1 << 17;
using Input = std::variant<MemoryMappedInput, BufferedInput<buffer_size>>;
using Output = std::variant<BufferedOutput<buffer_size>>;
Input input;
Output output;
static auto init_input() -> Input {
auto out = MemoryMappedInput::create();
if (out) return std::move(*out);
return BufferedInput<buffer_size>();
}
static auto init_output() -> Output { return BufferedOutput<buffer_size>(); }
IO() : input(init_input()), output(init_output()) {}
template <class T>
auto operator>>(T &rhs) -> IO & {
std::visit([&](auto &input) { InputImpl<decltype(input), T>{}.read(input, rhs); }, input);
return *this;
}
template <class T>
auto operator<<(const T &rhs) -> IO & {
std::visit([&](auto &output) { OutputImpl<decltype(output), T>{}.write(output, rhs); }, output);
return *this;
}
template <class InputType, class OutputType>
struct TypedIO {
InputType &input;
OutputType &output;
TypedIO(InputType &input_, OutputType &output_) : input(input_), output(output_) {}
template <class T>
auto operator>>(T &rhs) -> TypedIO & {
InputImpl<decltype(input), T>{}.read(input, rhs);
return *this;
}
template <class T>
auto operator<<(const T &rhs) -> TypedIO & {
OutputImpl<decltype(output), T>{}.write(output, rhs);
return *this;
}
auto flush() { return output.flush(); }
};
template <class F>
void run(F f) {
std::visit([&](auto &input, auto &output) { f(TypedIO(input, output)); }, input, output);
}
};
template <class Reader>
auto skip_whitespace(Reader &reader, usize n) -> std::tuple<const char *, usize, usize> {
auto [buf, buf_len] = reader.get_buffer(n);
usize buf_idx = 0;
while (1) {
while (buf_idx != buf_len) {
if (buf[buf_idx] > ' ') return {buf, buf_len, buf_idx};
++buf_idx;
}
reader.consume(buf_idx);
buf_idx = 0;
std::tie(buf, buf_len) = reader.get_buffer(n);
}
}
template <class Reader, class T>
struct InputImpl<Reader, T, std::enable_if_t<std::is_integral_v<T>>> {
void read(Reader &reader, T &rhs) {
constexpr auto max_len = base10_max_len<T>();
auto [buf, buf_len, buf_idx] = skip_whitespace(reader, max_len);
auto inner = [&]() {
rhs = 0;
while (1) {
while (buf_idx != buf_len) {
if (buf[buf_idx] <= ' ') {
reader.consume(buf_idx);
return;
}
rhs = rhs * 10 + buf[buf_idx] - '0';
++buf_idx;
}
reader.consume(buf_idx);
buf_idx = 0;
std::tie(buf, buf_len) = reader.get_buffer(max_len);
}
};
if constexpr (std::is_signed_v<T>) {
if (buf[buf_idx] == '-') {
++buf_idx;
inner();
rhs = -rhs;
} else {
inner();
}
} else {
inner();
}
}
};
template <class Reader>
struct InputImpl<Reader, char> {
void read(Reader &reader, char &rhs) {
auto [buf, buf_len, buf_idx] = skip_whitespace(reader, 1);
rhs = buf[buf_idx++];
reader.consume(buf_idx);
}
};
template <class Reader>
struct InputImpl<Reader, std::string> {
void read(Reader &reader, std::string &rhs) {
rhs.clear();
auto [buf, buf_len, buf_idx] = skip_whitespace(reader, 1);
while (1) {
u32 p = buf_idx;
while (p != buf_len) {
if (buf[p] <= ' ') break;
++p;
}
rhs += std::string_view(buf + buf_idx, buf + p);
reader.consume(p);
if (p != buf_len) return;
buf_idx = 0;
std::tie(buf, buf_len) = reader.get_buffer(1);
}
}
};
static constexpr auto digits_10k = []() {
auto res = std::array<char, 10'000 * 4>{};
for (u32 i = 0; i != 10'000; ++i) {
u32 p = 4 * (i + 1);
u32 rem = i;
for (int rep = 0; rep != 4; ++rep) {
res[--p] = char('0' + rem % 10);
rem /= 10;
}
}
return res;
}();
template <class Writer, class T>
struct OutputImpl<Writer, T, std::enable_if_t<std::is_integral_v<T>>> {
void write(Writer &writer, T rhs) {
if (rhs == 0) {
writer.write('0');
return;
}
constexpr auto max_len = base10_max_len<T>();
char buf[max_len];
usize buf_idx = max_len;
if constexpr (std::is_signed_v<T>) {
if (rhs < 0) {
writer.write('-');
if (rhs == std::numeric_limits<T>::min()) {
buf[--buf_idx] = char('0' - std::numeric_limits<T>::min() % 10);
rhs = std::numeric_limits<T>::min() / 10;
}
rhs = -rhs;
}
}
while (rhs >= 1000) {
buf_idx -= 4;
std::memcpy(buf + buf_idx, digits_10k.data() + rhs % 10'000 * 4, 4);
rhs /= 10'000;
}
if (rhs <= 9) {
if (rhs != 0) {
buf[--buf_idx] = char('0' + rhs);
}
} else if (rhs <= 99) {
u32 hi = (u32(rhs) * 205) >> 11;
u32 lo = u32(rhs) - 10 * hi;
buf[--buf_idx] = char('0' + lo);
buf[--buf_idx] = char('0' + hi);
} else {
buf_idx -= 3;
std::memcpy(buf + buf_idx, digits_10k.data() + rhs * 4 + 1, 3);
}
writer.write(buf + buf_idx, max_len - buf_idx);
}
};
template <class Writer>
struct OutputImpl<Writer, char> {
void write(Writer &writer, char rhs) { writer.write(rhs); }
};
template <class Writer, usize n>
struct OutputImpl<Writer, char[n]> {
void write(Writer &writer, const char *rhs) { writer.write(rhs, std::strlen(rhs)); }
};
// </io.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3e6+5;
const int iu=1e6;
vector<int>pf[N];
ll n,m;
int sz=0;
ll v[N];
void gen(vector<pair<ll,ll> >&g,int id,ll cur){
if(id==g.size()){
v[++sz]=cur;
return;
}
for(int i=0; i<g[id].fi ;i++){
ll dx=i*g[id].se;
gen(g,id+1,cur+dx);
}
}
ll gcd(ll x,ll y){
if(y==0) return x;
return gcd(y,x%y);
}
void solve(auto &&io){
io >> n >> m;
if(n>m) swap(n,m);
if(n==1 && pf[m].size()<=1){
io << "0\n0\n";
return;
}
ll xs=n;
for(ll s=n+1; s<=m ;s++){
if(s*s>n*m) break;
if(n*m%s==0) xs=s;
}
ll g=gcd(n,m);
if(n==m && pf[n].size()==1) g=1;
vector<pair<ll,ll> >gl,gr;
if(xs==n && g!=1){
ll p=pf[g][0];
for(int i=0; i<pf[n].size() ;i++){
if(pf[n][i]==p){
swap(pf[n][0],pf[n][i]);
break;
}
}
{
ll step=1;
for(auto c:pf[n]){
gl.push_back({c,step});
step*=c;
}
}
for(int i=0; i<pf[m].size() ;i++){
if(pf[m][i]==p){
swap(pf[m][0],pf[m][i]);
break;
}
}
swap(pf[m][0],pf[m].back());
{
ll step=1;
for(auto c:pf[m]){
gr.push_back({c,step});
step*=c;
}
}
swap(gl[0],gr.back());
}
else{
if(xs==n){
xs--;
while(n*m%xs!=0) --xs;
}
vector<pair<ll,ll> >gn;
{
ll step=1;
for(auto c:pf[n]){
gn.push_back({c,step});
step*=c;
}
}
{
ll step=1;
for(auto c:pf[m]){
gn.push_back({c,step});
step*=c;
}
}
for(auto c:gn){
if(xs%c.fi==0){
xs/=c.fi;
gl.push_back(c);
}
else gr.push_back(c);
}
}
sz=0;
gen(gl,0,0);
io << sz << ' ';
for(int i=1; i<=sz ;i++) io << v[i]+1 << ' ';
io << '\n';
sz=0;
gen(gr,0,0);
io << sz << ' ';
for(int i=1; i<=sz ;i++) io << v[i]+1 << ' ';
io << '\n';
}
auto io_main = [](auto &&io) -> void {
for(int i=2; i<=iu ;i++){
if(!pf[i].empty()) continue;
for(int j=i; j<=iu ;j+=i){
int z=j;
while(z%i==0){
z/=i;
pf[j].push_back(i);
}
}
}
int t;io >> t;
while(t--) solve(io);
/*u32 n;
io >> n;
i64 s = 0;
while (n--) {
i64 x;
io >> x;
s ^= x;
io << s << ' ';
}
io << '\n';*/
};
auto main() -> int {
auto io = IO();
io.run(io_main);
}
详细
Test #1:
score: 100
Accepted
time: 192ms
memory: 112060kb
input:
3 2 8 1 9 2 9
output:
4 1 2 2 3 4 1 5 3 7 3 1 2 3 3 1 4 7 3 1 2 3 6 1 4 7 2 5 8
result:
ok Correct. (3 test cases)
Test #2:
score: -100
Time Limit Exceeded
input:
1 40013 40013