QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#580456#9381. 502 Bad Gatewaykur222WA 182ms3696kbC++232.7kb2024-09-21 21:58:092024-09-21 21:58:10

Judging History

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

  • [2024-09-24 14:55:37]
  • hack成功,自动添加数据
  • (/hack/886)
  • [2024-09-21 21:58:10]
  • 评测
  • 测评结果:WA
  • 用时:182ms
  • 内存:3696kb
  • [2024-09-21 21:58:09]
  • 提交

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'