QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#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;
}

詳細信息

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'