QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276409 | #7030. Ultraman vs. Aodzilla and Bodzilla | zzuqy# | TL | 1ms | 3724kb | C++14 | 1.4kb | 2023-12-05 20:54:49 | 2023-12-05 20:54:51 |
Judging History
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...