QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #601858 | #9381. 502 Bad Gateway | Zpair# | WA | 1475ms | 4092kb | C++20 | 878b | 2024-09-30 14:45:33 | 2024-09-30 14:45:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
i128 T,S;
struct frac{
i128 x,y;
bool operator <(const frac &ret)const{
return x*1.0/y<ret.x*1.0/ret.y;
}
};
frac ans;
frac get(i128 L){
frac now={L*L*T-T*T*L+S,L};
ans=min(ans,now);
return now;
}
void solve(){
ll _T;
scanf("%lld",&_T);
T=_T;
S=T*(T+1)/2*T;
ans.x=1e27,ans.y=1;
i128 l=1,r=T,sz=(r-l)/3,m1=l+sz,m2=r-sz;
while(l+10<=r){
if(get(m1)<get(m2))
r=m2-1;
else l=m1+1;
sz=(r-l)/3,m1=l+sz,m2=r-sz;
}
for(int i=l;i<=r;++i)
get(i);
ans.y*=T;
i128 g=__gcd(ans.x,ans.y);
ans.x/=g,ans.y/=g;
ll x=ans.x,y=ans.y;
printf("%lld %lld\n",x,y);
// for(int L=1;L<=T;++L){
// mn=min(mn,(L*L*T-T*T*L+S)*1.0/L);
// }
// printf("%.6lf",mn*1.0/T);
}
int main(){
int T;cin>>T;
while(T--)solve();
}
/*
1
1000000000
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
3 1 2 3
output:
1 1 3 2 2 1
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 1475ms
memory: 4092kb
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 292893219236181961 707106781 1 1 1 1 292893219236181961 707106781 1 1 292893219236181961 707106781 1 1 1 1 1 1 292893219236181961 707106781 1 1 1 1 292893219236181961 707106781 1 1 292893219236181961 707106781 292893219236181961 707106781 1 1 292893219236181961 707106781 1 1 1 1 2928932192361819...
result:
wrong answer 2nd lines differ - expected: '1999961560 44721', found: '292893219236181961 707106781'