QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87872#5377. $N$ 门问题tricyzhkx0 10ms3636kbC++141.4kb2023-03-14 16:51:332023-03-14 16:51:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 16:51:35]
  • 评测
  • 测评结果:0
  • 用时:10ms
  • 内存:3636kb
  • [2023-03-14 16:51:33]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef vector<double> vd;
double solve(vd P)
{
	int n=P.size();
	if(n==2)
	{
		if(P[0]>P[1]) return 1;
		else if(P[0]<P[1]) return 0;
		else return 0.5;
	}
	double mx=-1;
	vector<int> pos;
	for(int i=0;i<n;i++)
		if(P[i]>mx) pos={i},mx=P[i];
		else if(P[i]==mx) pos.push_back(i);
	auto calc=[&](int i)
	{
		double minn=1;
		for(int j=1;j<n;j++)if(i!=j)
		{
			vd Q=P;
			double t=(1-P[i])/(1-P[j]-P[i]);
			for(int k=0;k<n;k++)
				if(k!=i) Q[k]*=t;
			Q.erase(Q.begin()+j);
			minn=min(minn,solve(Q));
		}
		return minn;
	};
	int sz=pos.size();
	if(P[0]<mx || sz==1) return calc(pos[0]);
	else return 1./sz*calc(0)+(sz-1.)/sz*calc(pos[1]);
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b) return x=1,y=0,a;
	ll g=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return g;
}
struct exCRT
{
	ll a,m;
	exCRT(ll _a=0,ll _m=0):a(_a),m(_m){}
	bool merge(const exCRT &C)
	{
		ll x,y,g=exgcd(m,C.m,x,y);
		if((a-C.a)%g) return false;
		m=m/g*C.m;
		a=(C.a+((a-C.a)/g*(lll)y%m+m)*C.m)%m;
		return true;
	}
}C(0,1);
int main()
{
	int T;
	ll a,m,n;
	cin>>T;
	while(T--)
	{
		scanf("%lld%lld",&a,&m);
		if(!C.merge(exCRT(a,m))) return puts("error"),0;
	}
	n=C.a;
	if(n>10) return puts("0.000000"),0;
	vd P(n,1./n);
	printf("%.6lf\n",solve(P));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 5
Accepted
time: 2ms
memory: 3532kb

input:

1
2 3

output:

0.500000

result:

ok single line: '0.500000'

Test #2:

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

input:

1
3 5

output:

0.666667

result:

ok single line: '0.666667'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

1
4 5

output:

0.625000

result:

ok single line: '0.625000'

Test #4:

score: -5
Runtime Error

input:

1
0 4

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 2ms
memory: 3636kb

input:

8
1 160005726539569
1 233
0 1
1 2947295521
1 686719856393
1 54289
1 12649337
1 37281334283719577

output:

1.000000

result:

wrong answer 1st lines differ - expected: 'error', found: '1.000000'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Runtime Error

Test #57:

score: 25
Accepted
time: 0ms
memory: 3348kb

input:

15
15 17
2 3
5 31
4 5
12 29
38 41
3 11
44 47
16 23
11 19
6 13
3 37
1 2
21 43
5 7

output:

0.000000

result:

ok single line: '0.000000'

Test #58:

score: 0
Accepted
time: 0ms
memory: 3336kb

input:

14
10 16
21 37
0 23
0 5
11 17
1 3
17 29
19 31
33 43
6 13
4 7
16 41
9 19
0 11

output:

0.000000

result:

ok single line: '0.000000'

Test #59:

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

input:

14
7 23
2 16
2 19
9 11
2 5
7 13
2 7
25 41
25 31
3 9
7 43
3 37
8 17
9 29

output:

0.000000

result:

ok single line: '0.000000'

Test #60:

score: 0
Accepted
time: 0ms
memory: 3428kb

input:

14
2 13
14 19
38 43
10 17
3 8
21 29
0 9
4 7
2 5
1 37
2 11
5 23
22 31
10 41

output:

0.000000

result:

ok single line: '0.000000'

Test #61:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

2
543380932 999999999
451172165 1000000000

output:

0.000000

result:

ok single line: '0.000000'

Test #62:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

15
1 2
9 13
31 37
1 17
0 23
1 3
2 5
17 31
9 11
5 29
4 47
6 7
40 41
1 19
26 43

output:

0.000000

result:

ok single line: '0.000000'

Test #63:

score: 0
Accepted
time: 10ms
memory: 3336kb

input:

50000
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 ...

output:

0.000000

result:

ok single line: '0.000000'

Test #64:

score: 0
Accepted
time: 9ms
memory: 3316kb

input:

50000
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 ...

output:

0.000000

result:

ok single line: '0.000000'

Test #65:

score: -25
Runtime Error

input:

50000
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 ...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%