結果

問題 No.3054 Modulo Inequalities
コンテスト
ユーザー suisen
提出日時 2025-01-18 16:19:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,455 bytes
コンパイル時間 1,334 ms
コンパイル使用メモリ 98,600 KB
実行使用メモリ 18,284 KB
最終ジャッジ日時 2025-02-02 13:30:00
合計ジャッジ時間 52,085 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 TLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

// TLE

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>

constexpr int M = 1000010;

struct constant_quotient_ranges {
    // 分子
    int n, m;
    // 商
    int qn, qm;
    // 商の組が等しい分母の区間 (l<=i<=r なる全ての i について floor(n/i)=qn かつ floor(m/i)=qm)
    int l = 1, r = 1;
    // 同じ商を持つ分母の最大値 (rn=max{i|floor(n/i)=qn}, rm=max{i|floor(m/i)=qm})
    // r=min(rn,rm) の関係
    int rn = 1, rm = 1;
    // 分母の上限値
    int max_value;
    constant_quotient_ranges(int n, int m, int max_value) : n(n), m(m), qn(n), qm(m), max_value(max_value) {}

    // 値
    std::tuple<int, int, int, int> operator*() const { return { qn, qm, l, r }; }
    // 継続条件
    bool operator!=(std::nullptr_t) const { return r <= max_value; }
    // 次の値の取得
    constant_quotient_ranges& operator++() {
        if (r == rn) {
            if (rn < n) {
                qn = n / (rn + 1);
                rn = n / qn;
            } else if (rn == n) {
                qn = 0;
                rn = max_value;
            } else {
                rn = max_value + 1;
            }
        }
        if (r == rm) {
            if (rm < m) {
                qm = m / (rm + 1);
                rm = m / qm;
            } else if (rm == m) {
                qm = 0;
                rm = max_value;
            } else {
                rm = max_value + 1;
            }
        }
        l = r + 1, r = std::min(rn, rm);
        return *this;
    }

    constant_quotient_ranges& begin() { return *this; }
    std::nullptr_t end() const { return nullptr; }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> ps(n);
    for (auto& [a, b] : ps) {
        std::cin >> a >> b;
    }

    std::vector<int> imos(M + 10);
    for (const auto& [a, b] : ps) if (a != b) {
        if (a > b) {
            for (const auto& [qa, qb, l, r] : constant_quotient_ranges(a, b, M)) {
                int m;
                if (qa == qb) {
                    m = r + 1;
                } else {
                    m = std::clamp((a - b) / (qa - qb) + 1, l, r + 1);
                }
                ++imos[m], --imos[r + 1];
            }
        } else {
            for (const auto& [qa, qb, l, r] : constant_quotient_ranges(a, b, M)) {
                int m;
                if (qa == qb) {
                    m = r + 1;
                } else {
                    m = std::clamp((b - a - 1) / (qb - qa) + 1, l, r + 1);
                }
                ++imos[l], --imos[m];
            }
        }
    }

    int max_num = -1, argmax = 0;
    for (int i = 1; i < M + 10; ++i) {
        imos[i] += imos[i - 1];
        if (imos[i] > max_num) {
            max_num = imos[i];
            argmax = i;
        }
    }
    std::cout << argmax << '\n';

    {
        int num = 0;
        for (const auto& [a, b] : ps) {
            if (a % argmax < b % argmax) {
                ++num;
                // std::cerr << "o " << a << ' ' << b << '\n';
            } else {
                // std::cerr << "x " << a << ' ' << b << '\n';
            }
        }
        assert(num == max_num);
        std::cerr << "Max Num: " << max_num << '\n';
        std::cerr << "Argmax Num: " << std::count(imos.begin(), imos.end(), max_num) << '\n';
    }
}
0