QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#580663#9381. 502 Bad GatewayLyniaAC ✓213ms3812kbC++205.4kb2024-09-21 22:59:042024-09-24 14:56:06

Judging History

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

  • [2024-09-24 14:56:06]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:213ms
  • 内存:3812kb
  • [2024-09-24 14:55:37]
  • hack成功,自动添加数据
  • (/hack/886)
  • [2024-09-21 22:59:05]
  • 评测
  • 测评结果:100
  • 用时:205ms
  • 内存:3792kb
  • [2024-09-21 22:59:04]
  • 提交

answer

///////////        
//                   //      //
//              ////////////////////
//                   //      //
//                 
///////////

//          
//          
//           //     //    ////////     /\     /////////
//           //     //   //      //          //       //
//            ////////   //      //    //    //       //
//                  //   //      //    //    //       //
//////////   ////////    //      //    //     /////////////

#pragma GCC optimize(2)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>

using namespace std;

#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define all(i) i.begin(), i.end()
#define endl '\n'
#define px first
#define py second
#define DEBUG cout<<-1<<endl;

using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
	out << '(' << p.first << ", " << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
	for (T i : ve)
		out << i << ' ';
	return out;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
	for (auto i : mp)
		out << i << '\n';
	return out;
}

const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

//#include "Lynia.h"

const int mod = 998244353;
const int N = 5e5 + 10;

struct node {
	ostream& print(ostream& out) const {
		return out;
	}
};

ostream& operator<<(ostream& out, const node& a) {
	return a.print(out);
}

template<typename ll = long long>
class Frac
{
private:
	ll abs(const ll& x)const { return x < 0 ? -x : x; }
	ll gcd(const ll& x, const ll& y)const { return y ? gcd(y, x % y) : x; }
	Frac reduce()
	{
		bool flag = 0;
		if (a < 0 && b < 0) a = -a, b = -b;
		if (a < 0) a = -a, flag = 1;
		if (b < 0) b = -b, flag = 1;
		ll ggcd = gcd(a, b);
		a /= ggcd;
		b /= ggcd;
		if (flag) a = -a;
		return *this;
	}
	void swap() { std::swap(a, b); }
	Frac _swap(const Frac& t)const { return Frac(t.b, t.a); }
	ll FastPow(ll x, ll p, ll mod)const
	{
		ll ans = 1, bas = x;
		for (; p; bas = bas * bas % mod, p >>= 1)
			if (p & 1) ans = ans * bas % mod;
		return ans;
	}
public:
	ll a, b;
	Frac(ll A = 0, ll B = 1) { a = A, b = B; }
	void show()const { std::cout << a << ' ' << b << "\n"; }
	ll to_int(const ll& mod = 1e9 + 7)const { return a * FastPow(b, mod - 2, mod) % mod; }
	Frac abs()const { return Frac(abs(a), abs(b)); }
	Frac operator =(const Frac& t) { return a = t.a, b = t.b, t; }
	bool operator ==(const Frac& t)const { Frac A(*this), B(t); return (A.reduce().a == B.reduce().a) && (A.b == B.b); }
	bool operator !=(const Frac& t)const { Frac A(*this), B(t); return (A.a != B.a) || (A.b != B.b); }
	bool operator >(const Frac& t)const { Frac A(*this), B(t); ll ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a > A.b / ggcd * B.a; }
	bool operator <(const Frac& t)const { Frac A(*this), B(t); ll ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a < A.b / ggcd * B.a; }
	bool operator >=(const Frac& t)const { Frac A(*this), B(t); ll ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a >= A.b / ggcd * B.a; }
	bool operator <=(const Frac& t)const { Frac A(*this), B(t); ll ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a <= A.b / ggcd * B.a; }
	Frac operator +(const Frac& t)const { ll ggcd = gcd(b, t.b); return Frac(b / ggcd * t.a + t.b / ggcd * a, b / ggcd * t.b).reduce(); }
	Frac operator +=(const Frac& t) { return *this = *this + t; }
	Frac operator *(const Frac& t)const { return Frac(a * t.a, b * t.b).reduce(); }
	Frac operator *=(const Frac& t) { return *this = *this * t; }
	Frac operator -(const Frac& t)const { return (*this + Frac(-t.a, t.b)).reduce(); }
	Frac operator -=(const Frac& t) { return *this = *this - t; }
	Frac operator /(const Frac& t)const { return (t._swap(t) * (*this)).reduce(); }
	Frac operator /=(const Frac& t) { return *this = *this / t; }
	Frac operator -()const { return Frac(-a, b); }
};

void solve(int CASE)
{
	ll t; cin >> t;
	ll c1 = (ll)sqrt(2 * t);
	ll c2 = (ll)ceil(sqrt(2 * t));
	db res1 = (c1 - 1.0) / 2.0 + t * 1.0 / c1;
	db res2 = (c2 - 1.0) / 2.0 + t * 1.0 / c2;
	ll x, y;
	if (res1 < res2) {
		x = c1 * (c1 - 1) + 2 * t;
		y = 2 * c1;
		ll gg = __gcd(x, y);
		x /= gg, y /= gg;
	}
	else {
		x = c2 * (c2 - 1) + 2 * t;
		y = 2 * c2;
		ll gg = __gcd(x, y);
		x /= gg, y /= gg;
	}
	cout << x << ' ' << y << endl;
	return;
}
int main()
{
	//SetConsoleOutputCP(CP_UTF8);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	fa(i, 1, _)solve(i);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3676kb

input:

3
1
2
3

output:

1 1
3 2
2 1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 139ms
memory: 3812kb

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
1999961560 44721
1 1
1 1
1999961560 44721
1 1
1999961560 44721
1 1
1 1
1 1
1999961560 44721
1 1
1 1
1999961560 44721
1 1
1999961560 44721
1999961560 44721
1 1
1999961560 44721
1 1
1 1
1999961560 44721
1 1
1999961560 44721
1999961560 44721
1 1
1999961560 44721
1999961560 44721
1999961560 44721
19...

result:

ok 1000000 lines

Test #3:

score: 0
Accepted
time: 213ms
memory: 3644kb

input:

1000000
158260522
877914575
602436426
24979445
861648772
623690081
433933447
476190629
262703497
211047202
971407775
628894325
731963982
822804784
450968417
430302156
982631932
161735902
880895728
923078537
707723857
189330739
910286918
802329211
404539679
303238506
317063340
492686568
773361868
125...

output:

316511467 17791
1755824328 41903
1204845831 34711
49954223 7068
1723292600 41513
623676492 17659
867864517 29460
952375859 30861
262700539 11461
422085442 20545
1942776701 44077
251551941 7093
1463896912 38261
1645584679 40566
901913913 30032
107573492 3667
1965228547 44331
323457022 17985
176178307...

result:

ok 1000000 lines

Extra Test:

score: 0
Extra Test Passed