QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584372#9381. 502 Bad GatewayJiyeonWA 819ms3740kbC++203.2kb2024-09-23 13:21:422024-09-23 13:21:43

Judging History

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

  • [2024-09-24 14:55:37]
  • hack成功,自动添加数据
  • (/hack/886)
  • [2024-09-23 13:21:43]
  • 评测
  • 测评结果:WA
  • 用时:819ms
  • 内存:3740kb
  • [2024-09-23 13:21:42]
  • 提交

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 end = sqrt(2 * nn);
    // 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 << (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";
    auto ans = calc(end);
    cout << (long long)ans.x << " " << (long long)ans.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

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1
2
3

output:

1 1
3 2
2 1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 474ms
memory: 3524kb

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:

ok 1000000 lines

Test #3:

score: -100
Wrong Answer
time: 819ms
memory: 3740kb

input:

1000000
158260522
877914575
602436426
24979445
861648772
623690081
433933447
476190629
262703497
211047202
971407775
628894325
731963982
822804784
450968417
430302156
982631932
161735902
880895728
923078537
707723857
189330739
910286918
802329211
404539679
303238506
317063340
492686568
773361868
125...

output:

316511467 17791
877891213 20951
1204845831 34711
49954223 7068
215406386 5189
623676492 17659
867835058 29459
952344999 30860
525378157 22921
211032449 10272
1942776701 44077
251551941 7093
1463896912 38261
1645584679 40566
901913913 30032
107573492 3667
1965228547 44331
323457022 17985
1761741106 4...

result:

wrong answer 2nd lines differ - expected: '1755824328 41903', found: '877891213 20951'