QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #590258 | #9381. 502 Bad Gateway | daniel14311531 | WA | 185ms | 3644kb | C++20 | 719b | 2024-09-25 22:58:32 | 2024-09-25 22:58:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<ll, ll> calc(ll n, ll l) {
ll x = 1ll * (l + 1) * l + n * 2ll - 2ll * l, y = 2ll * l;
ll d = __gcd(x, y);
return {x / d, y / d};
}
int main() {
ios::sync_with_stdio(0); cin.tie(nullptr);
int T; cin >> T;
for(; T; --T) {
int n; cin >> n;
int l = 0, r = n, mid;
for(; l < r;) {
mid = (l + r + 1) >> 1;
if(1ll * mid * mid <= 2ll * n) l = mid;
else r = mid - 1;
}
pair<ll, ll> x = calc(n, l);
pair<ll, ll> y = calc(n, l < n ? l + 1 : l);
pair<ll, ll> ans;
if(x.first * y.second > y.first * x.second) ans = x;
else ans = y;
cout << ans.first << " " << ans.second << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
3 1 2 3
output:
1 1 3 2 2 1
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 185ms
memory: 3644kb
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'