QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611531 | #7030. Ultraman vs. Aodzilla and Bodzilla | ucup-team4906# | WA | 216ms | 3784kb | C++20 | 2.7kb | 2024-10-04 21:21:58 | 2024-10-04 21:21:59 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
using namespace std;
typedef long long ll;
ll hp1, hp2, atk1, atk2;
bool ck(ll l1, ll r1, ll l, ll r)
{
assert(l <= r);
if (l <= 0 && 0 <= r) return 1;
ll L = 0, R = r1 - l1 + 1, pos = 0;
while (L <= R)
{
ll Mid = (L + R) >> 1;
ll l0 = pos * (l1 + l1 + pos - 1) / 2;
if (l0 <= l)pos = Mid, L = Mid + 1;
else R = Mid - 1;
}
// cout << "??:" << l1 << ' ' << r1 << ' ' << l << ' ' << r << " " << pos << endl;
if (pos > 0)
{
ll tr = (r1 - pos + 1 + r1) * pos / 2;
if (tr >= l) return 1;
}
if (pos < r1 - l1 + 1)
{
ll tl = (l1 + pos + l1) * (pos + 1) / 2;
// cout << "EMM:" << tl << endl;
if (tl <= r) return 1;
}
return 0;
}
pair<ll, string>sol1()
{
ll n, m;
for (n = 1; n * (n + 1) / 2 < hp1 + hp2; n ++);
for (m = 1; m * (m + 1) / 2 < hp1; m ++);
ll ans1 = n * atk2 + m * atk1;
string ans2 = "";
ll t1 = hp1, t2 = hp2, sum = n * (n + 1) / 2;
for (int i = 1; i <= m; i ++)
{
// cout << "EE:" << i << ' ' << t1 << ' ' << t2 << ' ' << sum << endl;
if (ck(i + 1, m, t1 - i, (sum - i) - t2))
{
t1 -= i, sum -= i;
ans2 += 'A';
}
else
{
t2 -= i, sum -= i;
ans2 += 'B';
}
}
for (int i = m + 1; i <= n; i ++)ans2 += 'B';
return {ans1, ans2};
}
pair<ll, string>sol2()
{
ll n, m;
for (n = 1; n * (n + 1) / 2 < hp1 + hp2; n ++);
for (m = 1; m * (m + 1) / 2 < hp2; m ++);
ll ans1 = n * atk1 + m * atk2;
string ans2 = "";
ll t1 = hp1, t2 = hp2, sum = n * (n + 1) / 2;
for (int i = 1; i <= m; i ++)
{
// cout << "EE:" << i << ' ' << t1 << ' ' << t2 << ' ' << sum << endl;
if (ck(i + 1, m, t2, (sum - i) - (t1 - i)))
{
t1 -= i, sum -= i;
ans2 += 'A';
}
else
{
t2 -= i, sum -= i;
ans2 += 'B';
}
}
for (int i = m + 1; i <= n; i ++)ans2 += 'A';
return {ans1, ans2};
}
void sol()
{
cin >> hp1 >> hp2 >> atk1 >> atk2;
auto p = sol1(), q = sol2();
// cout << "EE:" << p.first << ' ' << p.second << ' ' << q.first << ' ' << q.second << endl;
if (p < q) cout << p.first << ' ' << p.second << '\n';
else cout << q.first << ' ' << q.second << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
F(i, 1, t) sol();
return 0;
}
/*
1
5 15 25 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
2 5 15 5 25 5 15 25 5
output:
155 BBBBBA 105 AAABBB
result:
ok 2 cases
Test #2:
score: -100
Wrong Answer
time: 216ms
memory: 3756kb
input:
100000 1 1 1 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 1 5 1 1 1 6 1 1 1 7 1 1 1 8 1 1 1 9 1 1 1 10 1 1 2 1 1 1 2 2 1 1 2 3 1 1 2 4 1 1 2 5 1 1 2 6 1 1 2 7 1 1 2 8 1 1 2 9 1 1 2 10 1 1 3 1 1 1 3 2 1 1 3 3 1 1 3 4 1 1 3 5 1 1 3 6 1 1 3 7 1 1 3 8 1 1 3 9 1 1 3 10 1 1 4 1 1 1 4 2 1 1 4 3 1 1 4 4 1 1 4 5 1 1 4 6 1 ...
output:
3 AB 4 BA 5 BA 6 BA 7 BA 8 BA 9 BA 10 BA 11 BA 12 BA 4 AB 6 AB 7 BA 8 BA 9 BA 10 BA 11 BA 12 BA 13 BA 14 BA 5 AB 7 AB 9 AB 10 BA 11 BA 12 BA 13 BA 14 BA 15 BA 16 BA 6 AB 8 AB 10 AB 12 AB 13 BA 14 BA 15 BA 16 BA 17 BA 18 BA 7 AB 9 AB 11 AB 13 AB 15 AB 16 BA 17 BA 18 BA 19 BA 20 BA 8 AB 10 AB 12 AB 14...
result:
wrong answer In case 1301, the monster A is still alive.