QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#584429#9381. 502 Bad GatewayJiyeonTL 0ms3476kbC++203.1kb2024-09-23 14:10:472024-09-23 14:10:48

Judging History

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

  • [2024-09-24 14:55:37]
  • hack成功,自动添加数据
  • (/hack/886)
  • [2024-09-23 14:10:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3476kb
  • [2024-09-23 14:10:47]
  • 提交

answer

#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e6 + 5, mod = 998244353;
int my_gcd(int a, int b) {
    return b == 0 ? a : my_gcd(b, a % b);
}
struct fac {
    int x, y; 
    fac(int numerator = 0, int denominator = 1) {
        x = numerator;
        y = denominator;
        simplify();
    }
    void simplify() {
        int g = my_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 = sqrt(nn), r = sqrt(nn) * 5;
    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 << (long long) l << " " << (long long) 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++

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3476kb

input:

3
1
2
3

output:

1 1
3 2
2 1

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

1000000
1
1000000000
1
1
1000000000
1
1000000000
1
1
1
1000000000
1
1
1000000000
1
1000000000
1000000000
1
1000000000
1
1
1000000000
1
1000000000
1000000000
1
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1
1
1000000000
1
1000000000
1000000000
1000000000
1000000000
1
1
1
10000000...

output:

1 1
1999961560 44721
1 1
1 1
1999961560 44721
1 1
1999961560 44721
1 1
1 1
1 1
1999961560 44721
1 1
1 1
1999961560 44721
1 1
1999961560 44721
1999961560 44721
1 1
1999961560 44721
1 1
1 1
1999961560 44721
1 1
1999961560 44721
1999961560 44721
1 1
1999961560 44721
1999961560 44721
1999961560 44721
19...

result: