QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584349#9381. 502 Bad GatewayJiyeonCompile Error//C++173.0kb2024-09-23 12:58:132024-09-23 12:58:14

Judging History

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

  • [2024-09-24 14:55:37]
  • hack成功,自动添加数据
  • (/hack/886)
  • [2024-09-23 12:58:14]
  • 评测
  • [2024-09-23 12:58:13]
  • 提交

answer

#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e6 + 5, mod = 998244353;
struct fac {
    int x, y; 
    fac(int numerator = 0, int denominator = 1) {
        x = numerator;
        y = denominator;
        simplify();
    }
    void simplify() {
        int g = gcd(x, y); 
        x /= g;
        y /= g;
        if (y < 0) { 
            x = -x;
            y = -y;
        }
    }
    bool operator<(const fac& other) const {
        return x * other.y < other.x * y;
    }
    fac operator+(const fac& other) const {
        int newX = x * other.y + other.x * y;
        int newY = y * other.y;              
        return fac(newX, newY);              
    }

    fac operator-(const fac& other) const {
        int newX = x * other.y - other.x * y;
        int newY = y * other.y;              
        return fac(newX, newY);              
    }

    fac operator*(const fac& other) const {
        int newX = x * other.x;
        int newY = y * other.y;
        return fac(newX, newY);
    }

    fac operator/(const fac& other) const {
        int newX = x * other.y;
        int newY = y * other.x;
        return fac(newX, newY);
    }

    void print() const {
        cout << (long long)x << "/" << (long long)y << std::endl;
    }
};
int n;
fac calc(int end)
{
    fac old = fac(n+1, 2);
    fac first = old - (fac(end * (end + 1) / 2, n) + fac((n - end) * (n * (n + 1) / 2 + n), n * n));
    // (fac(end * (end + 1) / 2, n)).print();
    //  fac((n - end) * (n * (n + 1) / 2 + n), n * n).print();
    // cout << n * (n + 1) / 2 + n << endl;
    // ((fac(end * (end + 1) / 2, n) + fac((n - end) * (n * (n + 1) / 2 + n), n * n))).print();
    // first.print();
    fac q = fac(n - end , n);
    // q.print();
    fac ans = fac(n + 1, 2) - first / (fac(1, 1) - q);
    // cout << ans.x << " " << ans.y << " " << ans.x * 1.0 / ans.y << endl;
    return ans;
}
void solve()
{
    long long nn;
    cin >> nn;
    n = nn;
    // cin >> n;
    // int end = (n+2)/2;
    int l = 1, r = n;
    while(r - l > 2) {
        int midl = l + (r - l) / 3;
        int midr = r - (r - l) / 3;
        fac f1 = calc(midl);
        fac f2 = calc(midr);

        if (f1 < f2) { // 如果 f(m1) < f(m2),说明最小值在 [l, m2] 区间
            r = midr - 1;
        } else {       // 如果 f(m1) >= f(m2),说明最小值在 [m1, r] 区间
            l = midl + 1;
        }
    }
    // cout << l << " " << r << "\n";
    fac min_value = calc(l);
    int min_pos = l;
    for (int i = l + 1; i <= r; i++) {
        if (calc(i) < min_value) {
            min_value = calc(i);
            min_pos = i;
        }
    }
    cout << (long long)min_value.x << " " << (long long)min_value.y << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}
// g++ -o c++ c++.cpp -O2 -std=c++20 && ./c++

Details

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:58,
                 from answer.code:1:
/usr/include/c++/13/numeric: In instantiation of ‘constexpr std::common_type_t<_Mn, _Nn> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; common_type_t<_Mn, _Nn> = __int128]’:
answer.code:13:20:   required from here
/usr/include/c++/13/numeric:166:21: error: static assertion failed: std::gcd arguments must be integers
  166 |       static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
      |                     ^~~~~~~~~~~~~~~~~~
/usr/include/c++/13/numeric:166:21: note: ‘std::is_integral_v<__int128>’ evaluates to false
In file included from /usr/include/c++/13/bits/stl_pair.h:60,
                 from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/type_traits: In instantiation of ‘struct std::make_unsigned<__int128>’:
/usr/include/c++/13/type_traits:1983:11:   required by substitution of ‘template<class _Tp> using std::make_unsigned_t = typename std::make_unsigned::type [with _Tp = __int128]’
/usr/include/c++/13/numeric:173:24:   required from ‘constexpr std::common_type_t<_Mn, _Nn> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; common_type_t<_Mn, _Nn> = __int128]’
answer.code:13:20:   required from here
/usr/include/c++/13/type_traits:1836:62: error: invalid use of incomplete type ‘class std::__make_unsigned_selector<__int128, false, false>’
 1836 |     { typedef typename __make_unsigned_selector<_Tp>::__type type; };
      |                                                              ^~~~
/usr/include/c++/13/type_traits:1744:11: note: declaration of ‘class std::__make_unsigned_selector<__int128, false, false>’
 1744 |     class __make_unsigned_selector;
      |           ^~~~~~~~~~~~~~~~~~~~~~~~