QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99763#5377. $N$ 门问题zhouhuanyi25 124ms3800kbC++231.8kb2023-04-23 17:32:132023-04-23 17:32:15

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:32:15]
  • 评测
  • 测评结果:25
  • 用时:124ms
  • 内存:3800kb
  • [2023-04-23 17:32:13]
  • 提交

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)
    {
	if (v[0]==v[1]) return 0.5;
	else if (v[0]<v[1]) return 0;
	else return 1;
    }
    double res=0,rest=0,minn;
    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)
	{
	    minn=1;
	    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]));
			}
		    minn=min(minn,solve(sv));
		}
	    rest+=minn/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: 3596kb

input:

1
2 3

output:

0.500000

result:

ok single line: '0.500000'

Test #2:

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

input:

1
3 5

output:

0.666667

result:

ok single line: '0.666667'

Test #3:

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

input:

1
4 5

output:

0.625000

result:

ok single line: '0.625000'

Test #4:

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

input:

1
0 4

output:

error

result:

ok single line: 'error'

Test #5:

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

input:

1
1 3

output:

error

result:

ok single line: 'error'

Subtask #2:

score: 10
Accepted

Test #6:

score: 10
Accepted
time: 1ms
memory: 3416kb

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: 3628kb

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: 1ms
memory: 3720kb

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: 3800kb

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: 0
Accepted
time: 1ms
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.466667

result:

ok single line: '0.466667'

Test #11:

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

input:

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

output:

0.416667

result:

ok single line: '0.416667'

Test #12:

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

input:

2
1000000007 1000000008
2 4

output:

error

result:

ok single line: 'error'

Test #13:

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

input:

3
0 1001
0 241221531
0 2

output:

error

result:

ok single line: 'error'

Test #14:

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

input:

3
6 1001
6 241221531
0 2

output:

0.416667

result:

ok single line: '0.416667'

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #15:

score: 10
Accepted
time: 2ms
memory: 3360kb

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 #16:

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

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 #17:

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

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 #18:

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

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 #19:

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

input:

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

output:

0.466667

result:

ok single line: '0.466667'

Test #20:

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

input:

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

output:

0.416667

result:

ok single line: '0.416667'

Test #21:

score: 0
Accepted
time: 6ms
memory: 3640kb

input:

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

output:

0.342857

result:

ok single line: '0.342857'

Test #22:

score: 0
Accepted
time: 116ms
memory: 3752kb

input:

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

output:

0.291667

result:

ok single line: '0.291667'

Test #23:

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

input:

10
1 2
113 128
0 8
1 16
49 64
17 32
241 256
1 4
241 512
0 1

output:

error

result:

ok single line: 'error'

Test #24:

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

input:

10
5 8
237 512
1 2
13 32
12 16
0 1
109 128
1 4
45 64
237 256

output:

error

result:

ok single line: 'error'

Test #25:

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

input:

10
11 16
43 64
235 512
11 32
3 4
0 1
235 256
0 2
107 128
3 8

output:

error

result:

ok single line: 'error'

Test #26:

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

input:

10
9 32
1 2
41 64
233 512
233 256
1 4
0 1
9 16
1 8
115 128

output:

error

result:

ok single line: 'error'

Subtask #4:

score: 0
Time Limit Exceeded

Dependency #3:

100%
Accepted

Test #27:

score: 10
Accepted
time: 1ms
memory: 3440kb

input:

8
1 5
1 15
1 2
1 30
1 3
0 1
1 6
1 10

output:

error

result:

ok single line: 'error'

Test #28:

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

input:

8
2 30
2 15
0 1
2 6
2 5
2 3
2 10
0 2

output:

0.500000

result:

ok single line: '0.500000'

Test #29:

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

input:

8
0 1
0 3
0 15
0 2
0 30
0 6
0 5
0 10

output:

error

result:

ok single line: 'error'

Test #30:

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

input:

8
1 2
5 30
0 1
0 5
2 3
5 6
5 15
5 10

output:

0.466667

result:

ok single line: '0.466667'

Test #31:

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

input:

8
3 5
0 3
3 15
3 10
0 1
1 2
3 30
3 6

output:

0.666667

result:

ok single line: '0.666667'

Test #32:

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

input:

6
0 3
3 4
1 2
3 6
0 1
3 12

output:

0.666667

result:

ok single line: '0.666667'

Test #33:

score: 0
Accepted
time: 124ms
memory: 3628kb

input:

6
0 1
2 6
0 4
2 3
0 2
8 12

output:

0.291667

result:

ok single line: '0.291667'

Test #34:

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

input:

6
0 1
1 2
2 3
1 4
5 6
5 12

output:

0.466667

result:

ok single line: '0.466667'

Test #35:

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

input:

6
3 12
1 2
0 3
0 1
3 4
3 6

output:

0.666667

result:

ok single line: '0.666667'

Test #36:

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

input:

1
5 6

output:

0.466667

result:

ok single line: '0.466667'

Test #37:

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

input:

1
6 7

output:

0.416667

result:

ok single line: '0.416667'

Test #38:

score: 0
Accepted
time: 6ms
memory: 3632kb

input:

1
7 8

output:

0.342857

result:

ok single line: '0.342857'

Test #39:

score: 0
Accepted
time: 121ms
memory: 3540kb

input:

4
0 2
0 4
2 3
3 5

output:

0.291667

result:

ok single line: '0.291667'

Test #40:

score: -10
Time Limit Exceeded

input:

4
0 3
0 9
1 2
4 5

output:


result:


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:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%