QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276576#7030. Ultraman vs. Aodzilla and Bodzillazzuqy#AC ✓147ms3584kbC++143.3kb2023-12-05 23:00:202023-12-05 23:00:21

Judging History

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

  • [2023-12-05 23:00:21]
  • 评测
  • 测评结果:AC
  • 用时:147ms
  • 内存:3584kb
  • [2023-12-05 23:00:20]
  • 提交

answer


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

char buf[1<<15],*fs,*ft;
inline char getc(){
  return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:* fs++;
}
inline int read(){
    int This=0,F=1; char ch=getc();
    while(ch<'0'||ch>'9'){
        if(ch=='-') F=-1;
        ch=getc();
    }
    while(ch>='0'&&ch<='9'){
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getc();
    }
    return This*F;
}

inline void write(ll x)
{
	if(x==0)
	{
		putchar('0');
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	int num=0;char ch[40];
	while(x) ch[++num]=x%10+'0',x/=10;
	while(num) putchar(ch[num--]);
}

// ll solve(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(Ha>(ta-beg+1)*(beg+ta)/2&&Hb>Ha-(ta-beg+1)*(beg+ta)/2)
// 		tb=ask(ta+1,Hb+Ha-(ta-beg+1)*(beg+ta)/2);
// 	else
// 		tb=ta;

// 	if(Ha==1&&Hb==8)
// 	{
// 		cout<<endl<<beg<<'?'<<ta<<' '<<tb<<'?'<<ans<<endl;	
// 	}
// 	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;
	
// }
ll ANSA,ANSB,LENA,LENB;
char A[1000000],B[1000000];
ll ask(ll beg,ll H)
{
	if(H<=0)
		return 0;
	ll tH=2*H+1-2;
	ll x=sqrt(tH);
	while((1+x)*x/2<H)
		x++;
	return x;
}
void worka(ll Ha,ll Hb,ll Aa,ll Ab)
{
	ll lena=ask(1,Ha);//A的死亡时间不会更短
	ll lenb=ask(1,Ha+Hb);
	if((lenb+lena+1)*(lenb-lena)/2>=Hb)
	{
		ANSA=lena*Aa+lenb*Ab;
		for(int i=1;i<=lena;i++)
			A[i]='A';
		for(int i=lena+1;i<=lenb;i++)
			A[i]='B';
		LENA=lenb;
	}
	else
	{
		ANSA=lena*Aa+lenb*Ab;
		for(int i=lena+1;i<=lenb;i++)
			A[i]='B';
		for(int i=lena;i>=1;i--)
			A[i]='A';
		A[(lena+1)*lena/2-Ha]='B';
		LENA=lenb;
	}
}
void workb(ll Ha,ll Hb,ll Aa,ll Ab)
{
	ll lenb=ask(1,Hb);
	ll lena=ask(1,Ha+Hb);
	ANSB=lenb*Ab+lena*Aa;
	// cout<<(1+lenb)*lenb/2-Hb<<endl;
	ll t=ask(1,(1+lenb)*lenb/2-Hb+1)-1;
	if((1+t)*t/2+(1+lena)*lena/2-(1+lenb)*lenb/2>=Ha)
	{
		// cout<<"??";
		for(int i=1;i<=t;i++)
			B[i]='A';
		for(int i=t+1;i<=lenb;i++)
			B[i]='B';
		for(int i=lenb+1;i<=lena;i++)
			B[i]='A';
		LENB=lena;
	}
	else
	{
		ll now=Ha-(1+lena)*lena/2+(1+lenb)*lenb/2;
		for(int i=1;i<=lenb;i++)
		{
			if(now>=2*i+1){
				now-=i;
				B[i]='A';
			}
			else
				B[i]='B';
		}
		B[now]='A';
		for(int i=lenb+1;i<=lena;i++)
			B[i]='A';
		LENB=lena;
	}
}
void work()
{
	ll Ha=read(),Hb=read();
	ll Aa=read(),Ab=read();
	worka(Ha,Hb,Aa,Ab);
	workb(Ha,Hb,Aa,Ab);
	int flag='A';
	if(ANSA<ANSB)
		flag='A';
	else if(ANSA>ANSB)
		flag='B';
	else
	{
		for(int x=1;x<=max(LENA,LENB);x++)
			if(A[x]!=B[x])
			{
				if(A[x]<B[x])
					flag='A';
				else 
					flag='B';
				break;
			}
	}
	if(flag=='A')
	{
		cout<<ANSA<<' ';
		for(int i=1;i<=LENA;i++)
			cout<<A[i];
	}
	else
	{
		cout<<ANSB<<' ';
		for(int i=1;i<=LENB;i++)
			cout<<B[i];
	}
	cout<<'\n';
}
int main()
{
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	for(int t=read();t;t--)
	 	work();
}


这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 147ms
memory: 3584kb

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