QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#74206#5444. Tavern Chesszhangboju#WA 2ms3740kbC++141.7kb2023-01-31 08:59:192023-01-31 08:59:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-31 08:59:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3740kb
  • [2023-01-31 08:59:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;short f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;return;
}
const int N=15;
int n,m;
int ha[N],hb[N];
int aa[N],ab[N];
int cnta[N],cntb[N];
double ansa,ansb,ansp;
void dfsa(double p,int numa,int numb);
void dfsb(double p,int numa,int numb);
void dfsa(double p,int numa,int numb)
{
	if(!numa||!numb)
	{
		if(!numa&&!numb) ansp+=p;
		else if(!numa) ansb+=p;
		else ansa+=p;
		return;
	}
	int pos=0;
	for(int i=1;i<=n;++i)
		if(ha[i]>0&&(pos==0||cnta[i]<cnta[pos]))
			pos=i;
	if(!pos) return;
	for(int i=1;i<=m;++i)
	{
		if(hb[i]<=0) continue;
		ha[pos]-=ab[i];
		hb[i]-=aa[pos];
		++cnta[pos];
		dfsb(p/numb,numa-(ha[pos]<=0),numb-(hb[i]<=0));
		ha[pos]+=ab[i];
		hb[i]+=aa[pos];
		--cnta[pos];
	}
}
void dfsb(double p,int numa,int numb)
{
	if(!numa||!numb)
	{
		if(!numa&&!numb) ansp+=p;
		else if(!numa) ansb+=p;
		else ansa+=p;
		return;
	}
	int pos=0;
	for(int i=1;i<=m;++i)
		if(hb[i]>0&&(pos==0||cntb[i]<cntb[pos]))
			pos=i;
	if(!pos) return;
	for(int i=1;i<=m;++i)
	{
		if(ha[i]<=0) continue;
		hb[pos]-=aa[i];
		ha[i]-=ab[pos];
		++cntb[pos];
		dfsa(p/numa,numa-(ha[i]<=0),numb-(hb[pos]<=0));
		hb[pos]+=aa[i];
		ha[i]+=ab[pos];
		--cntb[pos];
	}
}
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;++i) read(ha[i]),aa[i]=ha[i];
	for(int i=1;i<=m;++i) read(hb[i]),ab[i]=hb[i];
	if(n>m) dfsa(1,n,m);
	else if(n<m) dfsb(1,n,m);
	else dfsa(0.5,n,m),dfsb(0.5,n,m);
	printf("%.10lf\n%.10lf\n%.10lf",ansa,ansb,ansp);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3740kb

input:

2 3
2 5
3 4 1

output:

0.1250000000
0.7500000000
0.1250000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

6 6
1 1 4 5 1 4
1 1 4 5 1 4

output:

0.2418672840
0.2418672840
0.5162654321

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

7 7
1 1 1 1 1 1 1
1 1 1 1 1 1 1

output:

0.0000000000
0.0000000000
1.0000000000

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 3432kb

input:

1 7
7
1 1 1 1 1 1 1

output:

0.0000000000
0.0000000000
1.0000000000

result:

ok 3 numbers

Test #5:

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

input:

2 3
736618938 652769331
328875880 97571721 44608905

output:

1.0000000000
0.0000000000
0.0000000000

result:

ok 3 numbers

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 3548kb

input:

5 4
53585130 731696211 668322278 611205195 158818781
569587984 776042583 745745433 330119007

output:

0.0243055556
0.0124421296
0.0743634259

result:

wrong answer 1st numbers differ - expected: '0.0668403', found: '0.0243056', error = '0.0425347'