Submission #66832635

---

Source Code Expand

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <source_location>
#include <stack>
#include <tuple>
#include <unordered_set>
#include <utility>

constexpr auto makePair(const auto& x1, const auto& x2) {
    return std::make_pair(x1, x2);
}
constexpr auto makeTup(const auto&... xs) {
    return std::make_tuple(xs...);
}


using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;
using f128 = __float128;
constexpr i32 operator"" _i32(u64 v) {
    return v;
}
constexpr u32 operator"" _u32(u64 v) {
    return v;
}
constexpr i64 operator"" _i64(u64 v) {
    return v;
}
constexpr u64 operator"" _u64(u64 v) {
    return v;
}
constexpr f64 operator"" _f64(f80 v) {
    return v;
}
constexpr f80 operator"" _f80(f80 v) {
    return v;
}
using Istream = std::istream;
using Ostream = std::ostream;
using Str = std::string;
template <typename T> using Lt = std::less<T>;
template <typename T> using Gt = std::greater<T>;
template <int n> using BSet = std::bitset<n>;
template <typename T1, typename T2> using Pair = std::pair<T1, T2>;
template <typename... Ts> using Tup = std::tuple<Ts...>;
template <typename T, int N> using Arr = std::array<T, N>;
template <typename... Ts> using Deq = std::deque<Ts...>;
template <typename... Ts> using Set = std::set<Ts...>;
template <typename... Ts> using MSet = std::multiset<Ts...>;
template <typename... Ts> using USet = std::unordered_set<Ts...>;
template <typename... Ts> using UMSet = std::unordered_multiset<Ts...>;
template <typename... Ts> using Map = std::map<Ts...>;
template <typename... Ts> using MMap = std::multimap<Ts...>;
template <typename... Ts> using UMap = std::unordered_map<Ts...>;
template <typename... Ts> using UMMap = std::unordered_multimap<Ts...>;
template <typename... Ts> using Vec = std::vector<Ts...>;
template <typename... Ts> using Stack = std::stack<Ts...>;
template <typename... Ts> using Queue = std::queue<Ts...>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::priority_queue<T, Vec<T>, Gt<T>>;
template <typename T> using Opt = std::optional<T>;
constexpr auto isBitOn(u64 x, int i) -> bool {
    return assert(0 <= i and i < 64), ((x >> i) & 1_u64);
}
constexpr auto isBitOff(u64 x, int i) -> bool {
    return assert(0 <= i and i < 64), (not isBitOn(x, i));
}
constexpr auto bitMask(int w) -> u64 {
    return assert(0 <= w and w <= 64), (w == 64 ? ~0_u64 : (1_u64 << w) - 1);
}
constexpr auto bitMask(int s, int e) -> u64 {
    return assert(0 <= s and s <= e and e <= 64), (bitMask(e - s) << s);
}
constexpr auto floorLog2(u64 x) -> int {
    return 63 - std::countl_zero(x);
}
constexpr auto ceilLog2(u64 x) -> int {
    return x == 0 ? -1 : std::bit_width(x - 1);
}
constexpr auto order2(u64 x) -> int {
    return std::countr_zero(x);
}
template <typename T> constexpr auto chmin(T& x, const T& y, auto comp) -> bool {
    return (comp(y, x) ? (x = y, true) : false);
}
template <typename T> constexpr auto chmin(T& x, const T& y) -> bool {
    return chmin(x, y, Lt<T>{});
}
template <typename T> constexpr auto chmax(T& x, const T& y, auto comp) -> bool {
    return (comp(x, y) ? (x = y, true) : false);
}
template <typename T> constexpr auto chmax(T& x, const T& y) -> bool {
    return chmax(x, y, Lt<T>{});
}

template <typename T> constexpr T LIMMIN = std::numeric_limits<T>::min();
template <typename T> constexpr T LIMMAX = std::numeric_limits<T>::max();
template <typename T> constexpr T INF = (LIMMAX<T> - 1) / 2;
template <typename T = i64> constexpr auto TEN(int N) -> T {
    return N == 0 ? T{1} : TEN<T>(N - 1) * T{10};
}
constexpr bool LOCAL = false;
template <typename T> constexpr auto OjLocal(T oj, T local) -> T {
    return LOCAL ? local : oj;
}

template <typename F> struct Fix : F {
    constexpr Fix(F&& f)
        : F{std::forward<F>(f)} {
    }
    template <typename... Args> constexpr auto operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <typename T> struct FMin {
    constexpr FMin() = default;
    constexpr auto operator()(const T& x, const T& y) const -> const T& {
        return std::ranges::min(x, y);
    }
};
template <typename T> struct FMax {
    constexpr FMax() = default;
    constexpr auto operator()(const T& x, const T& y) const -> const T& {
        return std::ranges::max(x, y);
    }
};
template <typename T> struct FSum {
    constexpr FSum() = default;
    constexpr auto operator()(const T& x, const T& y) const -> const T& {
        return x + y;
    }
};

constexpr auto floorDiv(i64 x, i64 y) -> i64 {
    assert(y != 0);
    if (y < 0) {
        x = -x, y = -y;
    }
    return x >= 0 ? x / y : (x - y + 1) / y;
}
constexpr auto ceilDiv(i64 x, i64 y) -> i64 {
    assert(y != 0);
    if (y < 0) {
        x = -x, y = -y;
    }
    return x >= 0 ? (x + y - 1) / y : x / y;
}

class irange {
private:
    struct itr {
        constexpr itr(i64 start, i64 end, i64 step)
            : m_cnt{start}, m_step{step}, m_end{end} {
        }
        constexpr auto operator!=(const itr&) const -> bool {
            return (m_step > 0 ? m_cnt < m_end : m_end < m_cnt);
        }
        constexpr auto operator*() const -> i64 {
            return m_cnt;
        }
        constexpr auto operator++() -> itr& {
            return m_cnt += m_step, *this;
        }
        i64 m_cnt, m_step, m_end;
    };
    i64 m_start, m_end, m_step;
public:
    constexpr irange(i64 start, i64 end, i64 step = 1)
        : m_start{start}, m_end{end}, m_step{step} {
        assert(step != 0);
    }
    constexpr auto begin() const -> itr {
        return itr{m_start, m_end, m_step};
    }
    constexpr auto end() const -> itr {
        return itr{m_start, m_end, m_step};
    }
};
constexpr auto rep(i64 end) -> irange {
    return irange(0, end, 1);
}
constexpr auto per(i64 rend) -> irange {
    return irange(rend - 1, -1, -1);
}


auto mdSeqAct(auto& xs, auto f) -> void {
    if constexpr (requires(const decltype(xs) xs) { std::ranges::begin(xs); }) {
        for (auto& x : xs) {
            mdSeqAct(x, f);
        }
    } else {
        f(xs);
    }
}
auto mdSeqFold(const auto& xs, auto op) {
    if constexpr (requires(const decltype(xs) xs) { std::ranges::begin(xs); }) {
        assert(std::size(xs) > 0);
        auto ans = mdSeqFold(xs[0], op);
        for (int i = 1; i < std::ssize(xs); i++) {
            ans = op(ans, mdSeqFold(xs[i], op));
        }
        return ans;
    } else {
        return xs;
    }
}
auto mdSeqFill(auto& xs, auto x) -> void {
    mdSeqAct(xs, [&x](auto& v) {
        v = x;
    });
}
auto mdSeqPlus(auto& xs, auto x) -> void {
    mdSeqAct(xs, [&x](auto& v) {
        v += x;
    });
}
auto mdSeqSum(const auto& xs) {
    return mdSeqFold(xs, [](auto x, auto y) {
        return x + y;
    });
}
auto mdSeqMin(const auto& xs, auto... args) {
    return mdSeqFold(xs, [&args...](auto x, auto y) {
        return std::ranges::min(x, y, args...);
    });
}
auto mdSeqMax(const auto& xs, auto... args) {
    return mdSeqFold(xs, [&args...](auto x, auto y) {
        return std::ranges::max(x, y, args...);
    });
}

template <typename T> constexpr auto powerMonoid(const T& x, i64 N, const T& e, auto mul) -> T {
    assert(N >= 0);
    if (N == 0) {
        return e;
    }
    if (N == 1) {
        return x;
    }
    return (N % 2 == 1 ? mul(x, powerMonoid(x, N - 1, e, mul)) : powerMonoid(mul(x, x), N / 2, e, mul));
}
template <typename T> constexpr auto powerMonoid(const T& x, i64 N, const T& e) -> T {
    return powerMonoid(x, N, e, std::multiplies<T>{});
}
template <typename T> constexpr auto powerInt(const T& x, i64 N) -> T {
    return powerMonoid(x, N, T{1});
}
constexpr auto powerMod(u64 x, i64 N, u64 mod) -> u64 {
    assert(0 < mod);
    return powerMonoid(x, N, u64{1}, [&](u64 x, u64 y) {
        if (mod <= (u64)LIMMAX<u32>) {
            return x * y % mod;
        } else {
            return (u64)((u128)x * y % mod);
        }
    });
}

template <std::move_constructible T>
requires(std::is_object_v<T> && std::same_as<T, std::remove_cv_t<T>>)
class repeat_view : public std::ranges::view_interface<repeat_view<T>> {
public:
    struct Itr {
        const T& operator*() const {
            return *x;
        }
        Itr& operator++() {
            return (cnt++), *this;
        }
        Itr operator++(int) {
            return {cnt++, *x};
        }
        bool operator==(const Itr& itr) const {
            return cnt == itr.cnt;
        }
        using difference_type = i64;
        using value_type = T;
        using iterator_concept = std::input_iterator_tag;
        i64 cnt;
        const T* x;
    };
    repeat_view() = default;
    repeat_view(const T& x, i64 N)
        : m_x{x}, m_N{N} {
    }
    Itr begin() const {
        return {0, &m_x};
    }
    Itr end() const {
        return {m_N, &m_x};
    }
    i64 size() const {
        return m_N;
    }
private:
    T m_x;
    i64 m_N;
};

auto seqConcat(auto& xs1, const auto& xs2) -> void {
    std::ranges::copy(xs2, std::back_inserter(xs1));
}
auto seqConcatCopy(const auto& xs1, const auto& xs2) {
    auto Ans = xs1;
    return seqConcat(Ans, xs2), Ans;
}
auto seqMinInd(const auto& xs, auto... args) -> int {
    return std::ranges::min_element(xs, args...) - std::ranges::begin(xs);
}
auto seqMaxInd(const auto& xs, auto... args) -> int {
    return std::ranges::max_element(xs, args...) - std::ranges::begin(xs);
}
auto seqReverse(auto& xs) -> void {
    std::ranges::reverse(xs);
}
auto seqSort(auto& xs, auto... args) -> void {
    std::ranges::sort(xs, args...);
}
template <typename T> auto genVec(int N, auto gen) -> Vec<T> {
    Vec<T> ans;
    std::ranges::generate_n(std::back_inserter(ans), N, gen);
    return ans;
}
template <typename T = int> auto iotaVec(int N, T offset = 0) -> Vec<T> {
    Vec<T> ans(N);
    std::iota(std::ranges::begin(ans), std::ranges::end(ans), offset);
    return ans;
}
auto seqRleVec(const auto& xs) {
    using T = std::remove_cvref_t<decltype(xs[0])>;
    Vec<Pair<T, int>> Ans;
    auto [l, px] = makePair(0, T{});
    for (const T& x : xs) {
        if (l == 0 or x != px) {
            if (l > 0) {
                Ans.push_back({px, l});
            }
            l = 1, px = x;
        } else {
            l++;
        }
    }
    if (l > 0) {
        Ans.push_back({px, l});
    }
    return Ans;
}



inline Ostream& operator<<(Ostream& os, u128 v) {
    Str ans;
    if (v == 0) {
        ans = "0";
    }
    while (v) {
        ans.push_back('0' + v % 10), v /= 10;
    }
    std::reverse(ans.begin(), ans.end());
    return os << ans;
}
inline Ostream& operator<<(Ostream& os, i128 v) {
    bool minus = false;
    if (v < 0) {
        minus = true, v = -v;
    }
    return os << (minus ? "-" : "") << (u128)v;
}

auto sortedLbInd(const auto& xs, const auto& x, auto... args) -> int {
    return std::ranges::lower_bound(xs, x, args...) - std::ranges::begin(xs);
}
auto sortedUbInd(const auto& xs, const auto& x, auto... args) -> int {
    return std::ranges::upper_bound(xs, x, args...) - std::ranges::begin(xs);
}
auto sortedFind(const auto& xs, const auto& x, auto... args) -> int {
    const int i = sortedLbInd(xs, x, args...);
    if (i < std::ranges::ssize(xs) and xs[i] == x) {
        return i;
    }
    return std::ranges::ssize(xs);
}


constexpr auto extgcd(i64 a, i64 b) -> Pair<i64, i64> {
    assert(a != 0 or b != 0);
    const i64 A = (((a) < 0) ? -(a) : (a)), B = (((b) < 0) ? -(b) : (b));
    if (A == B) {
        return {0, (b < 0 ? -1 : 1)};
    }
    auto [x, y, g] = Fix([&](auto self, i64 a, i64 b) -> Tup<i64, i64, i64> {
        assert(0 <= a and a < b);
        if (a == 0) {
            return {0, 1, b};
        }
        const auto [px, py, pg] = self(b % a, a);
        return {py - (b / a) * px, px, pg};
    })(std::ranges::min(A, B), std::ranges::max(A, B));
    if (A > B) {
        std::ranges::swap(x, y);
    }
    if (a < 0) {
        x = -x;
    }
    if (b < 0) {
        y = -y;
    }
    if (x < 0) {
        x += B / g, y -= (b > 0 ? a / g : -a / g);
    }
    return {x, y};
}
constexpr auto inverseMod(i64 a, i64 mod) -> i64 {
    return assert(mod > 0 and a % mod != 0), extgcd(a % mod, mod).first;
}
template <u64 Mod, bool dynamic = false>
requires(dynamic or (0 < Mod and Mod <= (u64)LIMMAX<i64>))
class modint {
public:
    static constexpr auto isDynamic() -> bool {
        return dynamic;
    }
    static constexpr auto mod() -> u64 {
        if constexpr (dynamic) {
            return modRef();
        } else {
            return Mod;
        }
    }
    static constexpr auto setMod(u64 m) -> void
        requires dynamic
    {
        assert(0 < m and m <= LIMMAX<i64>);
        modRef() = m, sinvRef() = factRef() = ifactRef() = {1, 1};
    }
    constexpr modint()
        : m_val{0} {
    }
    constexpr modint(i64 v)
        : m_val{normll(v)} {
    }
    constexpr friend auto operator-(const modint& x) -> modint {
        return modint{0} - x;
    }
    constexpr friend auto operator+=(modint& x1, const modint& x2) -> modint& {
        return x1.m_val = norm(x1.m_val + x2.m_val), x1;
    }
    constexpr friend auto operator-=(modint& x1, const modint& x2) -> modint& {
        return x1.m_val = norm(x1.m_val + mod() - x2.m_val), x1;
    }
    constexpr friend auto operator*=(modint& x1, const modint& x2) -> modint& {
        if constexpr (dynamic) {
            if (mod() <= (u64)LIMMAX<u32>) {
                return (x1.m_val *= x2.m_val) %= mod(), x1;
            } else {
                return x1.m_val = (u64)((u128)x1.m_val * (u128)x2.m_val % (u128)mod()), x1;
            }
        } else {
            if constexpr (Mod <= (u64)LIMMAX<u32>) {
                return (x1.m_val *= x2.m_val) %= mod(), x1;
            } else {
                return x1.m_val = (u64)((u128)x1.m_val * (u128)x2.m_val % (u128)mod()), x1;
            }
        }
    }
    constexpr friend auto operator/=(modint& x1, const modint& x2) -> modint& {
        return x1 *= x2.inv();
    }
    constexpr friend auto operator+(const modint& x1, const modint& x2) -> modint {
        auto ans = x1;
        return ans += x2;
    }
    constexpr friend auto operator-(const modint& x1, const modint& x2) -> modint {
        auto ans = x1;
        return ans -= x2;
    }
    constexpr friend auto operator*(const modint& x1, const modint& x2) -> modint {
        auto ans = x1;
        return ans *= x2;
    }
    constexpr friend auto operator/(const modint& x1, const modint& x2) -> modint {
        auto ans = x1;
        return ans /= x2;
    }
    constexpr friend auto operator<=>(const modint& x1, const modint& x2) = default;
    friend auto operator>>(Istream& is, modint& x) -> Istream& {
        i64 v;
        return is >> v, x = v, is;
    }
    friend auto operator<<(Ostream& os, const modint& x) -> Ostream& {
        return os << x.m_val;
    }
    constexpr auto val() const -> u64 {
        return m_val;
    }
    constexpr auto pow(i64 n) const -> modint {
        return powerInt(*this, n);
    }
    constexpr auto inv() const -> modint {
        return inverseMod(m_val, mod());
    }
    static auto sinv(int n) -> modint {
        assert(1 <= n);
        auto& is = sinvRef();
        for (int i : irange((int)is.size(), n + 1)) {
            is.push_back(-is[mod() % i] * (mod() / i));
        }
        return is[n];
    }
    static auto fact(int n) -> modint {
        assert(0 <= n);
        auto& fs = factRef();
        for (int i : irange((int)fs.size(), n + 1)) {
            fs.push_back(fs.back() * i);
        }
        return fs[n];
    }
    static auto ifact(int n) -> modint {
        auto& ifs = ifactRef();
        for (int i : irange((int)ifs.size(), n + 1)) {
            ifs.push_back(ifs.back() * sinv(i));
        }
        return ifs[n];
    }
    static auto perm(int n, int k) -> modint {
        return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k);
    }
    static auto comb(int n, int k) -> modint {
        return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k) * ifact(k);
    }
private:
    static auto modRef() -> u64& requires dynamic
    {
        static u64 mod_ = 0;
        return mod_;
    }
    static auto sinvRef() -> Vec<modint>& {
        static Vec<modint> is{1, 1};
        return is;
    }
    static auto factRef() -> Vec<modint>& {
        static Vec<modint> fs{1, 1};
        return fs;
    }
    static auto ifactRef() -> Vec<modint>& {
        static Vec<modint> ifs{1, 1};
        return ifs;
    }
    static constexpr auto norm(u64 x) -> u64 {
        return x < mod() ? x : x - mod();
    }
    static constexpr auto normll(i64 x) -> u64 {
        x %= (i64)mod();
        return norm(u64(x < 0 ? x + (i64)mod() : x));
    }
    u64 m_val;
};
using modint_1000000007 = modint<1000000007, false>;
using modint_998244353 = modint<998244353, false>;
template <u64 id>
requires(id < (u64)LIMMAX<i64>)
using modint_dynamic = modint<id, true>;
template <u64 id>
requires(id < (u64)LIMMAX<i64>)
using modint_dynamic_reserved = modint<id | (1_u64 << 63), true>;

class Printer {
public:
    Printer(Ostream& os = std::cout)
        : m_os{os} {
        m_os << std::fixed << std::setprecision(15);
    }
    int operator()(const auto&... args) {
        return dump(args...), 0;
    }
    int ln(const auto&... args) {
        return dump(args...), m_os << '\n', 0;
    }
    int el(const auto&... args) {
        return dump(args...), m_os << std::endl, 0;
    }
private:
    void dump(const auto& v) {
        m_os << v;
    }
    int dump(const auto& v, const auto&... args) {
        return dump(v), m_os << ' ', dump(args...), 0;
    }
    template <typename... Args> void dump(const Vec<Args...>& vs) {
        for (Str delim = ""; const auto& v : vs) {
            m_os << std::exchange(delim, " "), dump(v);
        }
    }
    Ostream& m_os;
};
inline Printer out;

template <typename Engine> class RNG {
public:
    using result_type = typename Engine::result_type;
    using U = result_type;
    static constexpr auto min() -> U {
        return Engine::min();
    }
    static constexpr auto max() -> U {
        return Engine::max();
    }
    RNG()
        : RNG(std::random_device{}()) {
    }
    RNG(U seed)
        : m_rng(seed) {
    }
    auto operator()() -> U {
        return m_rng();
    }
    template <typename T>
    requires std::is_integral_v<T>
    auto val(T min, T max) -> T {
        return std::uniform_int_distribution<T>(min, max)(m_rng);
    }
    template <typename T> auto vec(int N, T min, T max) -> Vec<T> {
        return genVec<T>(N, [&]() {
            return val<T>(min, max);
        });
    }
private:
    Engine m_rng;
};
inline RNG<std::mt19937> rng;
inline RNG<std::mt19937_64> rng64;

class Scanner {
public:
    Scanner(Istream& is = std::cin)
        : m_is{is} {
        m_is.tie(nullptr)->sync_with_stdio(false);
    }
    template <typename T> auto val() -> T {
        T v;
        return m_is >> v, v;
    }
    template <typename T> auto val(T offset) -> T {
        return val<T>() - offset;
    }
    template <typename T> auto vec(int N) -> Vec<T> {
        return genVec<T>(N, [&]() {
            return val<T>();
        });
    }
    template <typename T> auto vec(int N, T offset) -> Vec<T> {
        return genVec<T>(N, [&]() {
            return val<T>(offset);
        });
    }
    template <typename T> auto vvec(int n, int m) -> Vec<Vec<T>> {
        return genVec<Vec<T>>(n, [&]() {
            return vec<T>(m);
        });
    }
    template <typename T> auto vvec(int n, int m, const T offset) -> Vec<Vec<T>> {
        return genVec<Vec<T>>(n, [&]() {
            return vec<T>(m, offset);
        });
    }
    template <typename... Args> auto tup() {
        return Tup<Args...>{val<Args>()...};
    }
    template <typename... Args> auto tup(Args... offsets) {
        return Tup<Args...>{val<Args>(offsets)...};
    }
private:
    Istream& m_is;
};
inline Scanner in;

int main() {
    auto solve = [&]() {
        const auto N = in.val<int>();
        const auto As = in.vec<i64>(N);
        const auto Bs = in.vec<i64>(N);
        for (int i : irange(1, N)) {
            i64 C0 = As[1], Ci = -As[0];
            i64 D = As[0] * Bs[1] - As[1] * Bs[0];
            if (D == 0) {
                continue;
            }
            if (D < 0) {
                C0 = -C0, Ci = -Ci;
                D = -D;
            }
            const i64 C = (Bs[0] + D - 1) / D;
            Vec<i64> Xs(N, 0);
            Xs[0] = 1 + C * C0, Xs[i] = C * Ci;
            out.ln("Yes");
            out.ln(Xs);
            return 0;
        }
        out.ln("No");
        return 0;
    };
    const auto T = in.val<int>();
    for (auto _temp_name_0 [[maybe_unused]] : rep(T)) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result