QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276576 | #7030. Ultraman vs. Aodzilla and Bodzilla | zzuqy# | AC ✓ | 147ms | 3584kb | C++14 | 3.3kb | 2023-12-05 23:00:20 | 2023-12-05 23:00:21 |
Judging History
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