QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#582061#9381. 502 Bad GatewayKULIANLEN#WA 157ms3700kbC++172.0kb2024-09-22 15:12:152024-09-22 15:12:15

Judging History

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

  • [2024-09-24 14:55:37]
  • hack成功,自动添加数据
  • (/hack/886)
  • [2024-09-22 15:12:15]
  • 评测
  • 测评结果:WA
  • 用时:157ms
  • 内存:3700kb
  • [2024-09-22 15:12:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
using ld = long double;
using pii = pair<int,int>;

pii add(pii a, pii b) {
    int x = a.first * b.second + a.second * b.first;
    int y = a.second * b.second;
    int d = gcd(x, y);
    return {x / d, y / d};
}   

pii mul(pii a, int k) {
    int x = a.first * k;
    int y = a.second;
    int d = gcd(x, y);
    return {x / d, y / d}; 
}

void solve()
{
    int t;cin >> t;
    // int delta = 1 + 8 * t;
    // ld sq = sqrtl(d elta);
    // int x = ceill((1 + sq) / 2);
    // int res = 0;
    // x = min(x, t + 1);
    // int len = x - 1;
    // res += (1 + len) * len / 2;
    // pii ans = {res, t};
    // // cout << len << endl;
    // int d = gcd(ans.first, ans.second);
    // ans = {ans.first / d, ans.second / d};
    // if(t - x + 1 > 0)
    // {
    //     pii tmp = mul(add({t, x - 1}, {x, 2}), t - x + 1);
    //     // cout << tmp.first <<" " << tmp.second << endl;
    //     tmp = {tmp.first, tmp.second * t};
    //     int d = gcd(tmp.first, tmp.second);
    //     tmp.first /= d;tmp.second /= d;
    //     // cout << ans.first <<" " << ans.second <<" " << tmp.first <<" " << tmp.second << endl;
    //     ans = add(ans, tmp);
    // }


    int x = sqrtl(2 * t);
    x = min(x, t + 1);
    pii ans;
    if(x >= t)
    {
        ans = {t + 1, 2};
        if((t + 1) % 2 == 0)ans = {(t + 1) / 2, 1};
    }
    else 
    {
        ans = add({t, x}, {x - 1, 2});
        x++;
        pii ans1;
        if(x >= t)
        {
            ans1 = {t + 1, 2};
            if((t + 1) % 2 == 0)ans = {(t + 1) / 2, 1};
        }
        else ans1 = add({t, x}, {x - 1, 2});
        // cout << t <<" " << x << endl;
        if(ans.first * ans1.second < ans1.first * ans.second)
        {
            ans = ans1;
        }

    }
    
    cout << ans.first <<" " << ans.second << endl;


}


signed main() 
{
    ios::sync_with_stdio(false);cin.tie(0);
    int T;cin >> T;
    while(T--)
    solve();
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1
2
3

output:

1 1
3 2
2 1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 157ms
memory: 3700kb

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
2000006281 44722
1 1
1 1
2000006281 44722
1 1
2000006281 44722
1 1
1 1
1 1
2000006281 44722
1 1
1 1
2000006281 44722
1 1
2000006281 44722
2000006281 44722
1 1
2000006281 44722
1 1
1 1
2000006281 44722
1 1
2000006281 44722
2000006281 44722
1 1
2000006281 44722
2000006281 44722
2000006281 44722
20...

result:

wrong answer 2nd lines differ - expected: '1999961560 44721', found: '2000006281 44722'