QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178088#5377. $N$ 门问题zhoukangyang#25 41ms8116kbC++111.9kb2023-09-13 17:54:202024-07-04 01:56:24

Judging History

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

  • [2024-07-04 01:56:24]
  • 评测
  • 测评结果:25
  • 用时:41ms
  • 内存:8116kb
  • [2023-09-13 17:54:20]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define ull unsigned long long 
#define sz(a) ((int) a.size())
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1 << 21, L = 5e5, mod = 998244353;

double f[N];

ll n;

int k;
ll a[N], b[N];
ll rd() {
	cin >> k;
	L(i, 1, k) {
		cin >> a[i] >> b[i];
	}
	n = 0;
	while(true) {
		int win = 1;
		L(i, 1, k) {
			if(n % b[i] != a[i]) {
				win = 0;
				break;
			}
		}
		if(win) break;
		++n;
		if(n > 200) {
			n = 0;
			break;
		}
	}
	return n;
}

map < vector < double >, double > MP;
double slv(vector < double > a, int cur) { 
	if(sz(a) == 2) {
		return cur == 0;
	}
//	sort(a.begin() + 1, a.end());
//	if(MP.count(a)) return MP[a];
	double win = 1;
	L(p, 1, sz(a) - 1) if(p != cur) {
		double sum1 = 0, sum2 = 0;
		L(i, 0, sz(a) - 1) if(i != cur) {
			sum1 += a[i];
			if(i != p) sum2 += a[i];
		}
		sum1 /= sum2;
		vector < double > b;
		L(i, 0, sz(a) - 1) {
			if(i == cur) b.emplace_back(a[i]);
			else if(i != p) b.emplace_back(a[i] * sum1);
		}
		
		double mx = 0;
		L(i, 0, sz(b) - 1) {
			mx = max(mx, b[i]);
		}
		
		int total = 0;
		double sum = 0;
		L(i, 0, sz(b) - 1) {
			if(fabs(b[i] - mx) <= 1e-9) {
				total += 1;
				sum += slv(b, i);
			}
		}
		
		sum /= total;
		
		win = min(win, sum);
	}
	return MP[a] = win;
}

int main () { 
	ios :: sync_with_stdio(false);
	cin.tie (0); cout.tie (0);
	n = rd();
	if(n < 2) {
		cout << "error\n";
		return 0;
	}
	vector < double > f(n);
	L(i, 0, n - 1) {
		f[i] = 1;
	}
	double ans = (slv(f, 0) + slv(f, 1) * (n - 1)) / n;
	cout.precision(6); cout << fixed;
	cout << ans << '\n';
	return 0;
}

/*
(n-1)/(n-2) 1 [(n-1)/(n-2)] (n-1)/(n-2) (n-1)/(n-2) x 
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 8056kb

input:

1
2 3

output:

0.500000

result:

ok single line: '0.500000'

Test #2:

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

input:

1
3 5

output:

0.666667

result:

ok single line: '0.666667'

Test #3:

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

input:

1
4 5

output:

0.625000

result:

ok single line: '0.625000'

Test #4:

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

input:

1
0 4

output:

error

result:

ok single line: 'error'

Test #5:

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

input:

1
1 3

output:

error

result:

ok single line: 'error'

Subtask #2:

score: 10
Accepted

Test #6:

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

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: 0ms
memory: 7928kb

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

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

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

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: 0ms
memory: 8044kb

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

input:

2
1000000007 1000000008
2 4

output:

error

result:

ok single line: 'error'

Test #13:

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

input:

3
0 1001
0 241221531
0 2

output:

error

result:

ok single line: 'error'

Test #14:

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

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: 0ms
memory: 7716kb

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: 0ms
memory: 7968kb

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: 0ms
memory: 7864kb

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

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: 0ms
memory: 7888kb

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

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: 3ms
memory: 7892kb

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: 37ms
memory: 8116kb

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

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

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

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

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

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

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

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

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

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

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: 41ms
memory: 7952kb

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

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

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

input:

1
5 6

output:

0.466667

result:

ok single line: '0.466667'

Test #37:

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

input:

1
6 7

output:

0.416667

result:

ok single line: '0.416667'

Test #38:

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

input:

1
7 8

output:

0.342857

result:

ok single line: '0.342857'

Test #39:

score: 0
Accepted
time: 41ms
memory: 7980kb

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
Wrong Answer

Test #57:

score: 0
Wrong Answer
time: 0ms
memory: 7640kb

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:

error

result:

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

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%