QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#257681 | #7030. Ultraman vs. Aodzilla and Bodzilla | supepapupu | AC ✓ | 73ms | 3528kb | C++17 | 2.6kb | 2023-11-19 11:46:00 | 2023-11-19 11:46:01 |
Judging History
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