QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276409#7030. Ultraman vs. Aodzilla and Bodzillazzuqy#TL 1ms3724kbC++141.4kb2023-12-05 20:54:492023-12-05 20:54:51

Judging History

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

  • [2023-12-05 20:54:51]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3724kb
  • [2023-12-05 20:54:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
	ll x;scanf("%lld",&x);return x;
}
ll Aa,Ab;
ll ask(ll beg,ll H)//询问天数
{
	ll l=beg,r=1e9,mid;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if( (beg+mid)*(mid-beg+1)/2>=H)
			r=mid;
		else
			l=mid;
	}
	if( (beg+l)*(l-beg+1)/2>=H)
		return l;
	return r;
}
ll ask(ll beg,ll Ha,ll Hb)//受伤多少
{
	if(Ha<=0&&Hb<=0)
		return 0;
	if(Ha<=0)
	{
		ll t=ask(beg,Hb);
		return (t-beg+1)*Ab;
	}
	if(Hb<=0)
	{
		ll t=ask(beg,Ha);
		return (t-beg+1)*Aa;
	}
	ll ans=1e18;
	ll ta=ask(beg,Ha);
	ll tb;
	if(Hb>Ha-(ta-beg+1)*(beg+ta)/2)
		tb=ask(ta+1,Hb+Ha-(ta-beg+1)*(beg+ta)/2);
	else
		tb=ta;
	ans=(tb-beg+1)*Ab+(ta-beg+1)*Aa;

	tb=ask(beg,Hb);
	if(Ha>Hb-(tb-beg+1)*(beg+tb)/2)
		ta=ask(tb+1,Ha+Hb-(tb-beg+1)*(beg+tb)/2);
	else
		ta=tb;
	ans=min(ans,(ta-beg+1)*Aa+(tb-beg+1)*Ab);
	return ans;
	
}
void work()
{
	ll Ha=read(),Hb=read();
	Aa=read();Ab=read();
	ll ans=ask(1,Ha,Hb);
	cout<<ans<<' ';
	ll sum=0;
	for(int i=1;Ha>0||Hb>0;i++)
	{

		ll t;
		t=sum+(Ha>0)*Aa+(Hb>0)*Ab+ask(i+1,Ha-i,Hb);
		if(t==ans)
		{
			sum=sum+(Ha>0)*Aa+(Hb>0)*Ab;
			cout<<'A';
			Ha-=i;
		}
		else
		{
			sum=sum+(Ha>0)*Aa+(Hb>0)*Ab;
			cout<<'B';
			Hb-=i;

		}
	}
	cout<<'\n';
}
int main()
{
	// freopen("1.in","r",stdin);
	for(int t=read();t;t--)
	 	work();
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
5 15 5 25
5 15 25 5

output:

155 BBBBBA
105 AAABBB

result:

ok 2 cases

Test #2:

score: -100
Time Limit Exceeded

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: