QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#257681#7030. Ultraman vs. Aodzilla and BodzillasupepapupuAC ✓73ms3528kbC++172.6kb2023-11-19 11:46:002023-11-19 11:46:01

Judging History

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

  • [2023-11-19 11:46:01]
  • 评测
  • 测评结果:AC
  • 用时:73ms
  • 内存:3528kb
  • [2023-11-19 11:46:00]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cout << #x << ": " << x << el
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

int calc(int s, int h) {
    if (h < 0) return 0;
    for (int i = s;; ++i) {
        h -= i;
        if (h <= 0) return i - s + 1;
    } 
}

void solve() {
    ll ha, hb, da, db; cin >> ha >> hb >> da >> db;
    ll ta = calc(1, ha), tb = calc(1, hb);
    ll r1 = (1 + ta) * ta / 2 - ha, r2 = (1 + tb) * tb / 2 - hb;
    ll tab = calc(ta + 1, hb - r1), tba = calc(tb + 1, ha - r2);
    ll ans1 = ta * (da + db) + tab * db, ans2 = tb * (da + db) + tba * da;
    // cout << ans1 << ' ' << ans2 << el;
    cout << min(ans1, ans2) << ' ';
    // first A
    string way = "Z";
    if (ans1 <= ans2) {
        if (r1 == 0) {
            for (int i = 0; i < ta; ++i) cout << 'A';
            while (tab--) cout << 'B';
            cout << el;
            return;
        } else {
            if (calc(ta + 1, hb) == tab) {
                for (int i = 0; i < ta; ++i) cout << 'A';
                while (tab--) cout << 'B';
                cout << el;
                return;
            } else {
                string s;
                for (int i = 1; i <= ta; ++i) {
                    if (i != r1) s += 'A';
                    else s += 'B';
                }
                for (int i = 0; i < tab; ++i) s += 'B';
                way = min(way, s);
            }
        }
    } 
    if (ans2 <= ans1) {
        if (r2 == 0) {
            string s;
            for (int i = 0; i < tb; ++i) s += 'B';
            for (int i = 0; i < tba; ++i) s += 'A';
            way = min(way, s);
        } else {
            ll d = ha - (tb + 1 + tb + tba) * tba / 2;
            string s(tb + 1, 'B');
            int last = 0;
            for (int i = 1; i <= tb; ++i) {
                if (r2 - i < 0) break;
                s[i] = 'A', r2 -= i, d -= i;
                last = i;
            }
            if (d > 0) {
                for (int i = last; i; --i) {
                    int j = min(d, tb - i);
                    d -= j;
                    swap(s[i], s[i + j]);
                    if (!d) break;
                }
            }
            s.erase(s.begin());
            for (int i = 1; i <= tba; ++i) s += 'A';
            way = min(way, s);
        }
    }
    cout << way << el;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3428kb

input:

2
5 15 5 25
5 15 25 5

output:

155 BBBBBA
105 AAABBB

result:

ok 2 cases

Test #2:

score: 0
Accepted
time: 73ms
memory: 3528kb

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:

ok 100000 cases