QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#584433 | #9381. 502 Bad Gateway | Jiyeon | TL | 0ms | 3628kb | C++20 | 3.0kb | 2024-09-23 14:12:46 | 2024-09-23 14:12:48 |
Judging History
answer
#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e6 + 5, mod = 998244353;
struct fac {
int x, y;
fac(int numerator = 0, int denominator = 1) {
x = numerator;
y = denominator;
simplify();
}
void simplify() {
int g = __gcd(x, y);
x /= g;
y /= g;
if (y < 0) {
x = -x;
y = -y;
}
}
bool operator<(const fac& other) const {
return x * other.y < other.x * y;
}
fac operator+(const fac& other) const {
int newX = x * other.y + other.x * y;
int newY = y * other.y;
return fac(newX, newY);
}
fac operator-(const fac& other) const {
int newX = x * other.y - other.x * y;
int newY = y * other.y;
return fac(newX, newY);
}
fac operator*(const fac& other) const {
int newX = x * other.x;
int newY = y * other.y;
return fac(newX, newY);
}
fac operator/(const fac& other) const {
int newX = x * other.y;
int newY = y * other.x;
return fac(newX, newY);
}
void print() const {
cout << (long long)x << "/" << (long long)y << std::endl;
}
};
int n;
fac calc(int end)
{
fac old = fac(n+1, 2);
fac first = old - (fac(end * (end + 1) / 2, n) + fac((n - end) * (n * (n + 1) / 2 + n), n * n));
// (fac(end * (end + 1) / 2, n)).print();
// fac((n - end) * (n * (n + 1) / 2 + n), n * n).print();
// cout << n * (n + 1) / 2 + n << endl;
// ((fac(end * (end + 1) / 2, n) + fac((n - end) * (n * (n + 1) / 2 + n), n * n))).print();
// first.print();
fac q = fac(n - end , n);
// q.print();
fac ans = fac(n + 1, 2) - first / (fac(1, 1) - q);
// cout << ans.x << " " << ans.y << " " << ans.x * 1.0 / ans.y << endl;
return ans;
}
void solve()
{
long long nn;
cin >> nn;
n = nn;
// cin >> n;
// int end = (n+2)/2;
int l = sqrt(nn), r = sqrt(nn) * 3;
while(r - l > 2) {
int midl = l + (r - l) / 3;
int midr = r - (r - l) / 3;
fac f1 = calc(midl);
fac f2 = calc(midr);
if (f1 < f2) { // 如果 f(m1) < f(m2),说明最小值在 [l, m2] 区间
r = midr - 1;
} else { // 如果 f(m1) >= f(m2),说明最小值在 [m1, r] 区间
l = midl + 1;
}
}
// cout << (long long) l << " " << (long long) r << "\n";
fac min_value = calc(l);
int min_pos = l;
for (int i = l + 1; i <= r; i++) {
if (calc(i) < min_value) {
min_value = calc(i);
min_pos = i;
}
}
cout << (long long)min_value.x << " " << (long long)min_value.y << "\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
long long tt = 1;
cin >> tt;
while (tt--) solve();
return 0;
}
// g++ -o c++ c++.cpp -O2 -std=c++20 && ./c++
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
3 1 2 3
output:
1 1 3 2 2 1
result:
ok 3 lines
Test #2:
score: -100
Time Limit Exceeded
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...