QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276420#7030. Ultraman vs. Aodzilla and Bodzillazzuqy#TL 0ms3792kbC++141.6kb2023-12-05 21:04:062023-12-05 21:04:07

Judging History

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

  • [2023-12-05 21:04:07]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3792kb
  • [2023-12-05 21:04:06]
  • 提交

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 H)
{
	ll tH=2*H+beg*beg-beg-1;
	ll x=sqrt(tH);
	while((beg+x)*(x-beg+1)/2<H)
		x++;
	return x;
}
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);
	// freopen("1.out","w",stdout);
	for(int t=read();t;t--)
	 	work();
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3792kb

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: