QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#817136 | #7030. Ultraman vs. Aodzilla and Bodzilla | SGColin | AC ✓ | 99ms | 3684kb | C++17 | 1.8kb | 2024-12-16 20:36:06 | 2024-12-16 20:36:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define N 400007
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
inline void work() {
int ha = rd(), hb = rd(), a = rd(), b = rd();
// A B
ll wab = 0, tab = 0, sum = 0, dltab = -1;
for (int i = 1; ; ++i) {
if (sum < ha) wab += a;
else if (dltab < 0) dltab = sum - ha;
if (sum < ha + hb) wab += b;
sum += i;
if (sum >= ha + hb) {tab = i; break;}
}
ll dltab2 = sum - ha - hb;
// B A
ll wba = 0, tba = 0, dltba = -1; sum = 0;
for (int i = 1; ; ++i) {
if (sum < hb) wba += b;
else if (dltba < 0) dltba = sum - hb;
if (sum < ha + hb) wba += a;
sum += i;
if (sum >= ha + hb) {tba = i; break;}
}
ll dltba2 = sum - ha - hb;
string s1 = "", s2 = "";
int tmpa = ha, tmpb = hb;
if (dltab <= dltab2) {
for (int i = 1; hb > 0; ++i) {
if (ha > 0) {s1 += 'A'; ha -= i;}
else {s1 += 'B'; hb -= i;}
}
} else {
for (int i = 1; hb > 0; ++i) {
if (ha > 0 && i != dltab) {s1 += 'A'; ha -= i;}
else {s1 += 'B'; hb -= i;}
}
}
ha = tmpa; hb = tmpb;
ll L = dltba - dltba2, R = dltba, nw = 0;
for (int i = 1; ha > 0; ++i) {
if (nw + i <= R && (nw + i >= L || nw + i + i + 1 <= R)) {
s2 += 'A'; ha -= i; nw += i;
} else if (hb > 0) {s2 += 'B'; hb -= i;}
else {s2 += 'A'; ha -= i;}
}
cout << min(wab, wba) << " ";
if (wab == wba) cout << min(s1, s2) << endl;
else cout << (wab < wba ? s1 : s2) << endl;
}
int main() {
int t = rd();
while (t--) work();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
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: 99ms
memory: 3684kb
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