QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99758#5377. $N$ 门问题zhouhuanyi5 2ms3724kbC++231.7kb2023-04-23 17:22:022023-04-23 17:22:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-23 17:22:04]
  • 评测
  • 测评结果:5
  • 用时:2ms
  • 内存:3724kb
  • [2023-04-23 17:22:02]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 50000
using namespace std;
long long read()
{
    char c=0;
    long long sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
__int128 T,a,b,sx,sy,n;
double ans;
__int128 gcd(__int128 a,__int128 b)
{
    if (!b) return a;
    return gcd(b,a%b);
}
__int128 lcm(__int128 a,__int128 b)
{
    return a/gcd(a,b)*b;
}
void exgcd(__int128 a,__int128 b)
{
    if (!b)
    {
	sx=1,sy=0;
	return;
    }
    exgcd(b,a%b);
    __int128 tx=sx;
    sx=sy,sy=tx-(a/b)*sy;
    return;
}
double solve(vector<double>v)
{
    if (v.size()==2) return max(v[0],v[1]);
    double res=0,rest=0,maxn;
    int cnt=0;
    vector<double>sv;
    for (int i=0;i<v.size();++i) res=max(res,v[i]);
    for (int i=0;i<v.size();++i)
	if (v[i]==res)
	    cnt++;
    for (int i=0;i<v.size();++i)
	if (v[i]==res)
	{
	    maxn=0;
	    for (int j=1;j<v.size();++j)
		if (i!=j)
		{
		    sv.clear();
		    for (int k=0;k<v.size();++k)
			if (k!=j)
			{
			    if (k==i) sv.push_back(v[k]);
			    else sv.push_back(v[k]*(1-v[i])/(1-v[i]-v[j]));
			}
		    maxn=max(maxn,solve(sv));
		}
	    rest+=maxn/cnt;
	}
    return rest;
}
int main()
{
    vector<double>v;
    __int128 d=0,p=1,sp,g;
    T=read();
    while (T--)
    {
	a=read(),b=read(),g=gcd(p,b),sp=lcm(p,b);
	if ((a-d)%g!=0)
	{
	    puts("error");
	    return 0;
	}
	exgcd(p,b),sx=((sx*((a-d)/g))%sp+sp)%sp,d=(p*sx+d)%sp,p=sp;
    }
    n=d;
    if (n<2)
    {
	puts("error");
	return 0;
    }
    for (int i=1;i<=n;++i) v.push_back(1.0/n);
    printf("%0.6lf\n",solve(v));
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

1
2 3

output:

0.500000

result:

ok single line: '0.500000'

Test #2:

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

input:

1
3 5

output:

0.666667

result:

ok single line: '0.666667'

Test #3:

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

input:

1
4 5

output:

0.625000

result:

ok single line: '0.625000'

Test #4:

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

input:

1
0 4

output:

error

result:

ok single line: 'error'

Test #5:

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

input:

1
1 3

output:

error

result:

ok single line: 'error'

Subtask #2:

score: 0
Wrong Answer

Test #6:

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

input:

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

output:

error

result:

ok single line: 'error'

Test #7:

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

input:

10
2 64
0 2
2 512
2 4
2 32
2 16
2 256
0 1
2 8
2 128

output:

0.500000

result:

ok single line: '0.500000'

Test #8:

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

input:

10
3 256
3 16
0 1
3 8
3 512
3 32
3 4
3 128
3 64
1 2

output:

0.666667

result:

ok single line: '0.666667'

Test #9:

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

input:

10
0 2
4 8
0 4
4 256
0 1
4 512
4 32
4 128
4 64
4 16

output:

0.625000

result:

ok single line: '0.625000'

Test #10:

score: -10
Wrong Answer
time: 0ms
memory: 3636kb

input:

10
5 128
5 32
5 16
1 4
0 1
5 64
5 256
5 512
1 2
5 8

output:

0.622857

result:

wrong answer 1st lines differ - expected: '0.466667', found: '0.622857'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #4:

0%

Subtask #6:

score: 0
Memory Limit Exceeded

Test #57:

score: 0
Memory Limit Exceeded

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:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%