QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#580663 | #9381. 502 Bad Gateway | Lynia | AC ✓ | 213ms | 3812kb | C++20 | 5.4kb | 2024-09-21 22:59:04 | 2024-09-24 14:56:06 |
Judging History
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