QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#580456 | #9381. 502 Bad Gateway | kur222 | WA | 182ms | 3696kb | C++23 | 2.7kb | 2024-09-21 21:58:09 | 2024-09-21 21:58:10 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pi=pair<int,int>;
const ll mod=998244353;
template<class T>
struct Frac{
T num;
T den;
Frac(T num_,T den_):num(num_),den(den_){
if(den<0){
den=-den;
num=-num;
}
}
Frac():Frac(0,1){}
Frac(T num_):Frac(num_,1){}
void dd()
{
ll gg=gcd(num,den);
num/=gg;
den/=gg;
};
explicit operator double() const{
return 1.*num/den;
}
Frac &operator+=(const Frac &rhs){
num=num*rhs.den+rhs.num*den;
den*=rhs.den;
return *this;
}
Frac &operator-=(const Frac &rhs){
num=num*rhs.den-rhs.num*den;
den*=rhs.den;
return *this;
}
Frac &operator*=(const Frac &rhs){
num*=rhs.num;
den*=rhs.den;
return *this;
}
Frac &operator/=(const Frac &rhs){
num*=rhs.den;
den*=rhs.num;
if(den<0){
num=-num;
den=-den;
}
return *this;
}
friend Frac operator+(Frac lhs,const Frac &rhs){
return lhs+=rhs;
}
friend Frac operator-(Frac lhs,const Frac &rhs){
return lhs-=rhs;
}
friend Frac operator*(Frac lhs,const Frac &rhs){
return lhs*=rhs;
}
friend Frac operator/(Frac lhs,const Frac &rhs){
return lhs/=rhs;
}
friend Frac operator-(const Frac &a){
return Frac(-a.num,a.den);
}
friend bool operator==(const Frac &lhs,const Frac &rhs){
return lhs.num*lhs.den==rhs.num*rhs.den;
}
friend bool operator!=(const Frac &lhs,const Frac &rhs){
return lhs.num*lhs.den!=rhs.num*rhs.den;
}
friend bool operator<(const Frac &lhs,const Frac &rhs){
return lhs.num*rhs.den<rhs.num*lhs.den;
}
friend bool operator>(const Frac &lhs,const Frac &rhs){
return lhs.num*rhs.den>rhs.num*lhs.den;
}
friend bool operator<=(const Frac &lhs,const Frac &rhs){
return lhs.num*rhs.den<=rhs.num*lhs.den;
}
friend bool operator>=(const Frac &lhs,const Frac &rhs){
return lhs.num*rhs.den>=rhs.num*lhs.den;
}
};
using fr=Frac<ll>;
void solve()
{
ll T;
// cin >> T;
T=1e9;
fr ans = fr(T + 1, 2);
fr now;
auto check = [&](ll m) {
ll num_low = m - 1;
ll num_great = T - m + 1;
ll total = (num_low + 1) * num_low / 2 + num_great;
if(T == num_great) {
now = fr((T + 1), 2);
} else now = fr(total, T - num_great);
// cerr << m << " " << now.num << " " << now.den << "\n";
return now + fr(1, 1) <= fr(m, 1);
};
ll lo = 1, hi = T + 1;
while(lo < hi) {
ll m = (lo + hi) / 2;
if(check(m)){
hi = m;
ans = min(ans, now);
}
else lo = m + 1;
}
ans.dd();
cout << ans.num << " " << ans.den << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int __=1e6;
// cin>>__;
while(__--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 182ms
memory: 3696kb
input:
3 1 2 3
output:
1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 44721 1999961560 ...
result:
wrong answer 1st lines differ - expected: '1 1', found: '1999961560 44721'