QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#611531#7030. Ultraman vs. Aodzilla and Bodzillaucup-team4906#WA 216ms3784kbC++202.7kb2024-10-04 21:21:582024-10-04 21:21:59

Judging History

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

  • [2024-10-04 21:21:59]
  • 评测
  • 测评结果:WA
  • 用时:216ms
  • 内存:3784kb
  • [2024-10-04 21:21:58]
  • 提交

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.