QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#817136#7030. Ultraman vs. Aodzilla and BodzillaSGColinAC ✓99ms3684kbC++171.8kb2024-12-16 20:36:062024-12-16 20:36:13

Judging History

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

  • [2024-12-16 20:36:13]
  • 评测
  • 测评结果:AC
  • 用时:99ms
  • 内存:3684kb
  • [2024-12-16 20:36:06]
  • 提交

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