#909754 (C++17) No.2453 Seat Allocation

• 問題: No.2453 Seat Allocation
• ユーザー: rniya
• 提出日時: 2023-09-01 21:52:10
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 65 ms / 2,000 ms
• コード長: 6,246 bytes
• コンパイル時間: 2,038 ms
• コンパイル使用メモリ: 203,168 KB
• 実行使用メモリ: 8,584 KB
• 最終ジャッジ日時: 2025-06-20 01:44:15
• 合計ジャッジ時間: 3,927 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 23

ソースコード

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <typename T, bool Reduce = false> class Rational {
    T num, den;

    static T my_gcd(T x_, T y_) {
        unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
        if (!x or !y) return x + y;
        int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
        x >>= n, y >>= m;
        while (x != y) {
            if (x > y)
                x = (x - y) >> __builtin_ctzll(x - y);
            else
                y = (y - x) >> __builtin_ctzll(y - x);
        }
        return x << (n > m ? m : n);
    }

    void normalize() {
        if (den < 0) num = -num, den = -den;
        if (den == 0) num = (num > 0 ? 1 : num < 0 ? -1 : 0);
        if constexpr (Reduce) {
            T g = my_gcd(num, den);
            if (g > 0) num /= g, den /= g;
        }
    }

  public:
    Rational() {}
    Rational(T num) : num(num), den(T(1)) {}
    Rational(T num, T den) : num(num), den(den) { normalize(); }

    Rational operator+(const Rational& r) const { return Rational(num * r.den + den * r.num, den * r.den); }
    Rational operator-(const Rational& r) const { return Rational(num * r.den - den * r.num, den * r.den); }
    Rational operator*(const Rational& r) const { return Rational(num * r.num, den * r.den); }
    Rational operator/(const Rational& r) const { return Rational(num * r.den, den * r.num); }
    Rational& operator+=(const Rational& r) { return *this = *this + r; }
    Rational& operator-=(const Rational& r) { return *this = *this - r; }
    Rational& operator*=(const Rational& r) { return *this = *this * r; }
    Rational& operator/=(const Rational& r) { return *this = *this / r; }

    Rational operator+(const T& val) const { return *this + Rational(val); }
    Rational operator-(const T& val) const { return *this - Rational(val); }
    Rational operator*(const T& val) const { return *this * Rational(val); }
    Rational operator/(const T& val) const { return *this / Rational(val); }
    Rational& operator+=(const T& val) { return *this = *this + val; }
    Rational& operator-=(const T& val) { return *this = *this - val; }
    Rational& operator*=(const T& val) { return *this = *this * val; }
    Rational& operator/=(const T& val) { return *this = *this / val; }
    friend Rational operator+(const T& val, const Rational& r) { return r + val; }
    friend Rational operator-(const T& val, const Rational& r) { return r - val; }
    friend Rational operator*(const T& val, const Rational& r) { return r * val; }
    friend Rational operator/(const T& val, const Rational& r) { return r / val; }

    Rational operator-() const { return Rational(-num, den); }
    Rational abs() const { return Rational(num < 0 ? -num : num, den); }

    bool operator==(const Rational& r) const {
        if (den == 0 and r.den == 0) return num == r.num;
        if (den == 0 or r.den == 0) return false;
        return num * r.den == den * r.num;
    }
    bool operator!=(const Rational& r) const { return !(*this == r); }
    bool operator<(const Rational& r) const {
        if (den == 0 and r.den == 0) return num < r.num;
        if (den == 0) return num < 0;
        if (r.den == 0) return r.num > 0;
        return num * r.den < den * r.num;
    }
    bool operator<=(const Rational& r) const { return (*this == r) or (*this < r); }
    bool operator>(const Rational& r) const { return r < *this; }
    bool operator>=(const Rational& r) const { return (*this == r) or (*this > r); }

    bool operator==(const T& val) const { return *this == Rational(val); }
    bool operator!=(const T& val) const { return *this != Rational(val); }
    bool operator<(const T& val) const { return *this < Rational(val); }
    bool operator<=(const T& val) const { return *this <= Rational(val); }
    bool operator>(const T& val) const { return *this > Rational(val); }
    bool operator>=(const T& val) const { return *this >= Rational(val); }
    friend bool operator==(const T& val, const Rational& r) { return r == val; }
    friend bool operator!=(const T& val, const Rational& r) { return r != val; }
    friend bool operator<(const T& val, const Rational& r) { return r > val; }
    friend bool operator<=(const T& val, const Rational& r) { return r >= val; }
    friend bool operator>(const T& val, const Rational& r) { return r < val; }
    friend bool operator>=(const T& val, const Rational& r) { return r <= val; }

    explicit operator double() const { return (double)num / (double)den; }
    explicit operator long double() const { return (long double)num / (long double)den; }
    friend std::ostream& operator<<(std::ostream& os, const Rational& r) { return os << r.num << '/' << r.den; }
};

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

using R = Rational<ll>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    cin >> A >> B;

    priority_queue<pair<R, int>> pq;
    vector<int> cur(N, 0);
    for (int i = 0; i < N; i++) pq.emplace(R(A[i], B[cur[i]++]), -i);
    for (int i = 0; i < M; i++) {
        auto [val, idx] = pq.top();
        pq.pop();
        idx *= -1;
        cout << idx + 1 << '\n';
        if (cur[idx] < M) pq.emplace(R(A[idx], B[cur[idx]++]), -idx);
    }
    return 0;
}