QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#608832#2410. Average Rankkevinyang#AC ✓1576ms1251148kbC++143.1kb2024-10-04 05:07:102024-10-04 05:07:11

Judging History

This is the latest submission verdict.

  • [2024-10-04 05:07:11]
  • Judged
  • Verdict: AC
  • Time: 1576ms
  • Memory: 1251148kb
  • [2024-10-04 05:07:10]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int sq = 1000;

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n,w;
	cin >> n >> w;
	vector<vector<int>>arr(n+1);
	vector<vector<int>>vals(w+1);
	for(int i = 1; i<=w; i++){
		int k;
		cin >> k;
		for(int j = 0; j<k; j++){
			int x;
			cin >> x;
			arr[x].push_back(i);
			vals[i].push_back(x);
		}
	}
	for(int i = 1; i<=n; i++){
		arr[i].push_back(w+1);
	}
	vector<int>c(n+1);
	vector<vector<int>>dp(w+1,vector<int>(505));
	dp[0][0] = n;
	for(int i = 1; i<=w; i++){
		for(int j = 0; j<=503; j++){
			dp[i][j] = dp[i-1][j];
		}
		for(int u: vals[i]){
			c[u]++;
			dp[i][min(c[u]-1,503ll)]--;
			dp[i][min(c[u],503ll)]++;
		}
	}
	for(int i = 1; i<=w; i++){
		for(int j = 503; j>=0; j--){
			dp[i][j] += dp[i-1][j]+dp[i][j+1]-dp[i-1][j+1];
		}
	}
	vector<int>ans(n+1);

	for(int i = 1; i<=n; i++){
		int cur = 0;
		if(arr[i].size() > 500)continue;
		for(int j = 0; j<arr[i].size(); j++){
			int idx = arr[i][j]-1;
			ans[i]+=dp[idx][j+1] - dp[cur][j+1];
			cur = idx;
		}
	}
	// for(int j = 1; j<=n; j++){
	// 	cout << ans[j] << ' ';
	// }
	// cout << '\n';
	for(int i = 0; i<=w; i++){
		for(int j = 0; j<505; j++){
			dp[i][j] = 0;
		}
	}
	vector<int>big;
	for(int i = 1; i<=n; i++){
		if(arr[i].size() > 500){
			big.push_back(i);
		}
	}
	dp[0][0] = n-big.size();
	for(int i = 1; i<=n; i++){
		c[i] = 0;
	}
	for(int i = 1; i<=w; i++){
		for(int j = 0; j<=503; j++){
			dp[i][j] = dp[i-1][j];
		}
		for(int u: vals[i]){
			if(arr[u].size() > 500)continue;
			c[u]++;
			dp[i][min(c[u]-1,503ll)]--;
			dp[i][min(c[u],503ll)]++;
		}
	}
	for(int i = 1; i<=w; i++){
		for(int j = 503; j>=0; j--){
			dp[i][j] += dp[i-1][j]+dp[i][j+1]-dp[i-1][j+1];
		}
	}
	vector<pii>order;
	for(int i: big){
		int cur = 0;
		for(int j = 0; j<arr[i].size(); j++){
			int idx = arr[i][j]-1;
			ans[i]+=dp[idx][j+1] - dp[cur][j+1];
			if(j==501)break;
			cur = idx;
		}
		order.push_back({i,0});
	}
	auto sorted = [&]() -> bool {
		for(int i = 1; i<order.size(); i++){
			if(order[i].second < order[i-1].second)return false;
		}
		return true;
	};
	auto fix = [&]() -> void {
		for(int i = 1; i<order.size(); i++){
			if(order[i].second < order[i-1].second){
				swap(order[i-1],order[i]);
			}
		}
	};
	for(int i = 1; i<=n; i++){
		c[i] = 0;
	}
	for(int i = 1; i<=w; i++){
		for(int u: vals[i]){
			c[u]++;
		}
		for(int j = 0; j<order.size(); j++){
			order[j].second = c[order[j].first];
		}
		while(!sorted()){
			fix();
		}
		int cur = 0;
		for(int j = (int)order.size()-1; j>=0; j--){
			if(j+1<order.size() && order[j].second < order[j+1].second){
				cur = (int)order.size()-1-j;
			}
			ans[order[j].first]+=cur;
		}
	}
	cout << fixed << setprecision(10);
	for(int i = 1; i<=n; i++){
		double d = w+ans[i];
		cout << d/w << '\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3796kb

input:

4 3
2 1 3
3 2 3 4
2 1 4

output:

1.3333333333
3.0000000000
1.0000000000
2.0000000000

result:

ok 4 numbers

Test #2:

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

input:

20 40
4 14 1 18 5
4 6 5 20 12
4 18 1 14 8
4 4 17 5 15
4 8 3 19 13
4 5 12 1 3
4 13 6 17 8
4 18 16 17 7
3 9 11 5
4 1 9 11 12
4 8 7 11 3
4 17 13 6 19
3 15 4 17
4 14 3 15 1
4 1 18 6 10
3 1 10 8
3 2 8 11
3 17 15 19
4 20 19 14 18
3 3 13 9
2 20 3
4 9 5 7 8
4 16 20 3 9
4 13 15 19 20
4 15 3 10 17
3 10 11 6
4...

output:

2.2500000000
18.0500000000
3.4000000000
13.9250000000
3.4250000000
5.1250000000
13.6750000000
3.6500000000
8.7750000000
15.3750000000
9.1500000000
8.1000000000
7.0750000000
8.4000000000
6.2500000000
16.3000000000
4.1250000000
7.1250000000
9.0750000000
9.4000000000

result:

ok 20 numbers

Test #3:

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

input:

3 2
2 1 2
2 1 3

output:

1.0000000000
1.5000000000
2.5000000000

result:

ok 3 numbers

Test #4:

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

input:

1 1
1 1

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #5:

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

input:

5 6
2 3 2
1 1
1 2
3 5 4 3
1 1
2 5 4

output:

1.8333333333
1.0000000000
1.1666666667
3.1666666667
3.1666666667

result:

ok 5 numbers

Test #6:

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

input:

10 10
3 3 7 1
1 1
4 9 2 10 4
2 10 3
3 2 3 6
4 2 7 8 5
4 4 5 9 8
2 6 8
5 1 6 10 5 9
2 7 4

output:

1.8000000000
2.1000000000
1.2000000000
4.2000000000
4.8000000000
5.1000000000
3.4000000000
4.5000000000
3.4000000000
2.5000000000

result:

ok 10 numbers

Test #7:

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

input:

31 29
7 7 24 13 3 18 9 28
7 21 13 28 29 26 8 31
6 23 8 2 29 24 22
5 13 25 29 22 20
7 6 31 29 24 1 13 12
2 8 19
4 4 30 21 14
5 17 28 1 6 4
8 17 30 18 27 14 21 3 10
8 30 28 25 22 9 15 14 18
6 19 1 17 27 31 12
5 16 20 23 13 1
7 16 7 26 5 15 11 21
7 11 25 30 15 17 14 24
1 12
8 2 10 3 22 5 13 4 23
3 28 1...

output:

5.1724137931
14.2758620690
12.1034482759
11.8965517241
20.2068965517
14.4827586207
16.1034482759
6.1724137931
17.9310344828
22.1034482759
16.1379310345
12.6896551724
1.2068965517
7.2413793103
12.9655172414
17.8275862069
7.9655172414
8.0689655172
14.5862068966
11.8275862069
3.5172413793
9.5862068966
...

result:

ok 31 numbers

Test #8:

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

input:

3 1
0

output:

1.0000000000
1.0000000000
1.0000000000

result:

ok 3 numbers

Test #9:

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

input:

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

output:

3.1666666667
3.3333333333
1.0000000000
3.8333333333
1.6666666667

result:

ok 5 numbers

Test #10:

score: 0
Accepted
time: 1349ms
memory: 1244368kb

input:

300000 300000
150000 152378 20536 230896 243531 130262 222665 146584 12680 200961 255680 2766 29860 293060 200643 182208 86955 290788 137148 79258 187602 223959 170916 247928 46417 10375 136965 171609 213627 82670 98292 163902 213617 207226 53553 128847 234468 29348 152905 210512 265156 144800 22868...

output:

1.5000000000
99999.9999966667
99999.5000000000
99999.4999966667
1.9999966667
1.5000000000
1.0000000000
1.4999966667
1.9999966667
99999.9999966667
99999.4999966667
99999.9999966667
99999.9999966667
99999.9999966667
99999.9999966667
99999.5000000000
99999.4999966667
1.5000000000
1.9999966667
1.5000000...

result:

ok 300000 numbers

Test #11:

score: 0
Accepted
time: 1075ms
memory: 1227244kb

input:

300000 300000
299999 7032 158227 7678 209203 266354 200085 253883 166008 250138 90371 66885 207467 228752 19269 286178 296729 71542 207097 127135 214555 149659 129563 148687 49276 268491 32212 20362 217347 133993 61093 270529 144881 211539 232955 131129 13058 242480 34936 209410 23922 156572 96427 2...

output:

1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1...

result:

ok 300000 numbers

Test #12:

score: 0
Accepted
time: 1089ms
memory: 1227304kb

input:

300000 300000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1...

result:

ok 300000 numbers

Test #13:

score: 0
Accepted
time: 1576ms
memory: 1249008kb

input:

300000 300000
299999 71033 247962 54677 261990 9654 217040 88445 1037 105117 58162 221454 10948 92280 229918 30197 47441 14956 261154 223658 105679 121570 13317 279910 226256 61552 264443 11177 262478 244700 275323 30774 1887 94319 70218 256870 33889 92135 279991 17428 141520 260437 17508 282396 202...

output:

44955.8950266667
24980.8585066667
100613.4860300000
107691.5776266667
162046.5083266667
184146.3950666667
151506.1902233333
55293.6349266667
148521.3815000000
5955.7596933333
169675.9607066667
162650.1529700000
28009.5936766667
97567.9174800000
31344.7446733333
115841.9124233333
30256.0316200000
989...

result:

ok 300000 numbers

Test #14:

score: 0
Accepted
time: 939ms
memory: 1203100kb

input:

2 300000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

1.0000000000
1.0000033333

result:

ok 2 numbers

Test #15:

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

input:

310 290
4 99 168 59 270
9 146 232 41 198 142 186 82 30 161
9 161 191 151 269 55 56 127 39 165
5 264 206 209 201 9
5 23 90 111 271 218
6 47 276 100 146 310 273
3 180 42 72
4 162 192 89 170
1 251
7 105 78 185 88 100 304 20
5 2 65 123 296 131
4 108 235 65 131
2 289 42
11 45 113 227 303 222 291 171 18 5...

output:

142.2517241379
47.5793103448
168.9793103448
137.5758620690
78.0620689655
118.7758620690
93.3931034483
106.5758620690
141.8068965517
197.6068965517
99.7620689655
64.6103448276
179.7068965517
73.5689655172
176.3000000000
148.7758620690
62.9310344828
104.8000000000
78.5413793103
80.5413793103
52.065517...

result:

ok 310 numbers

Test #16:

score: 0
Accepted
time: 7ms
memory: 6964kb

input:

1765 794
40 1326 319 110 1071 1163 1029 603 467 1351 318 902 1143 796 1482 1761 262 345 969 866 1256 572 1441 1078 1362 812 1355 1155 1239 1203 1440 435 357 1049 1670 1667 422 1455 89 1198 1094
30 422 261 1441 52 568 1276 869 584 1502 435 1198 1094 1703 572 157 134 257 1159 128 635 357 1570 35 1113 ...

output:

1078.2783375315
615.2997481108
1314.1863979849
1424.2493702771
454.0818639798
940.3261964736
677.1926952141
430.0239294710
289.3450881612
631.6297229219
792.0327455919
26.0856423174
665.9748110831
283.2279596977
1067.8085642317
444.2455919395
1179.7392947103
879.3488664987
547.9005037783
590.5377833...

result:

ok 1765 numbers

Test #17:

score: 0
Accepted
time: 977ms
memory: 1214980kb

input:

1 300000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #18:

score: 0
Accepted
time: 126ms
memory: 28084kb

input:

300000 1
300000 49768 155480 28861 97552 227184 37757 100849 63219 47794 64854 251728 122056 2801 134528 204772 133045 165499 11257 204257 138807 75117 6823 37823 132760 83446 268187 181730 3612 249343 25649 280441 195002 76101 116736 144375 45713 183801 29935 22987 135773 290568 89307 195031 177754...

output:

1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1...

result:

ok 300000 numbers

Test #19:

score: 0
Accepted
time: 1029ms
memory: 1224100kb

input:

300000 300000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1.6038033333
1...

result:

ok 300000 numbers

Test #20:

score: 0
Accepted
time: 303ms
memory: 72996kb

input:

100000 10000
96 1544 54337 51952 75699 54387 41720 98690 8105 89737 19401 25982 72872 53321 13606 23186 96215 28571 63276 58554 11026 78812 91506 47050 67720 8530 67857 8652 81109 8505 43952 61378 59487 88498 8180 77934 3207 97647 63732 3070 16008 95642 14028 63502 10091 1705 27285 50977 93423 81696...

output:

53336.6059000000
18470.0651000000
49956.6250000000
26444.0265000000
53496.4916000000
32049.2349000000
45075.9361000000
31798.4550000000
34686.0297000000
18832.3840000000
42392.2168000000
76710.1091000000
56593.7572000000
37206.0664000000
32208.9468000000
63398.4485000000
52777.9245000000
19998.39570...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 1542ms
memory: 1251148kb

input:

300000 300000
5 157356 169216 18305 108007 3918
2 205587 67014
2 115998 156445
3 128155 3313 217830
2 86595 294117
3 179919 112643 139659
1 5741
4 238037 197089 182186 117205
5 112778 185124 21090 262456 275381
6 83026 205000 182707 89512 198435 11251
4 291125 239325 280964 159617
6 211325 161480 89...

output:

213950.9664033333
148990.9428666667
104996.9917900000
70147.5188533333
41451.0174666667
127813.8403433333
58572.2408033333
78815.6237333333
34028.5393866667
28106.7376000000
159668.7396800000
132310.9944600000
54541.2790700000
181005.6486666667
56311.4333300000
134421.1365633333
68385.0684566667
560...

result:

ok 300000 numbers

Test #22:

score: 0
Accepted
time: 247ms
memory: 70820kb

input:

100000 10000
90 80838 29211 2147 49644 56197 18473 11030 23767 83262 60875 84370 41533 90913 38305 84261 7862 34797 89005 67747 32187 98023 80692 43911 48990 86686 49171 67043 94639 24874 53132 12337 59797 94192 14415 53884 98079 70111 81342 46838 31370 28128 99843 59900 66576 6199 43302 45951 37351...

output:

51504.0550000000
12665.6546000000
63130.3686000000
40691.2641000000
64652.3626000000
66407.7808000000
53226.7544000000
33905.4586000000
24120.6085000000
33142.7273000000
33318.2300000000
29488.0509000000
13236.1300000000
60599.3709000000
48376.6163000000
25337.5414000000
35407.1154000000
9421.108700...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 1490ms
memory: 1247428kb

input:

300000 300000
5 226400 220239 74825 172235 2996
5 299606 87615 129599 190350 77047
2 9338 135432
5 60859 4714 280222 235596 258967
3 8462 167912 87615
4 278168 279730 285242 87615
2 111500 59917
2 135441 234907
5 268987 264905 92696 141219 87615
2 287419 87615
4 274811 87615 296765 94834
4 120991 28...

output:

96274.9508733333
16869.4594633333
96274.9508733333
96274.9508733333
59268.5401033333
96274.9508733333
10570.1841100000
96274.9508733333
39354.9469633333
96274.9508733333
60554.8801900000
96274.9508733333
96274.9508733333
52343.2678433333
35412.4989100000
64512.9580166667
15418.5722266667
2570.321923...

result:

ok 300000 numbers

Test #24:

score: 0
Accepted
time: 1522ms
memory: 1247272kb

input:

300000 300000
2 297956 28538
3 83232 136045 169110
3 15593 126207 222941
3 190651 57624 131636
5 164816 215083 153334 289804 296131
4 126207 256111 165409 95552
4 14040 118877 42972 69564
4 12016 168978 41692 158254
3 279062 126207 256111
2 126207 136045
5 174375 177539 126207 42224 108173
3 179728 ...

output:

58579.8790666667
28819.7670200000
35264.4336700000
77080.6264633333
17808.8905966667
96414.0677233333
37060.1429766667
96414.0677233333
83156.0145900000
72858.7348366667
43618.1211900000
96414.0677233333
96414.0677233333
38736.1255266667
96414.0677233333
96414.0677233333
96414.0677233333
96414.06772...

result:

ok 300000 numbers

Test #25:

score: 0
Accepted
time: 360ms
memory: 57020kb

input:

300000 3000
347 56478 204263 76691 265446 5360 26423 95256 195667 128406 99722 177562 175055 13210 154674 88284 196227 60392 297562 80078 179333 151004 233521 176873 58903 254739 217826 241387 109580 86763 87709 165063 202919 268171 58778 128645 234210 84032 205871 63012 110167 168788 118032 121390 ...

output:

148317.3553333333
13229.2170000000
108759.9723333333
9715.0990000000
14771.1550000000
75143.2763333333
44080.5826666667
85297.1076666667
63029.5866666667
67443.3030000000
54224.6606666667
45270.3013333333
148317.3553333333
148317.3553333333
72133.2270000000
31808.5410000000
148317.3553333333
112447....

result:

ok 300000 numbers

Test #26:

score: 0
Accepted
time: 1277ms
memory: 1229552kb

input:

30000 300000
0
3 414 5579 23513
4 414 8287 6392 871
5 414 7696 6206 19336 4268
1 6627
7 3188 3181 24176 6334 414 21394 19595
0
3 1786 2224 414
6 6861 7122 22569 21220 4045 5579
0
2 414 5947
3 414 17193 18305
5 16314 11465 5579 414 18305
4 6002 20737 1569 27293
5 408 414 7938 18233 1322
5 14363 27059...

output:

24793.9113500000
6864.2358466667
5759.6114266667
22432.7092133333
15787.4481033333
25401.8990666667
15486.5315233333
15634.7641666667
24455.5793000000
4523.0027366667
14050.3168066667
17965.2176766667
16722.7291500000
12996.6695733333
17667.5605966667
19163.9789766667
14196.4361566667
4704.468606666...

result:

ok 30000 numbers

Test #27:

score: 0
Accepted
time: 56ms
memory: 23968kb

input:

1000 1000
1000 44 839 681 251 965 449 430 775 369 534 990 905 75 234 969 457 318 250 330 342 704 911 109 711 712 6 18 816 998 592 632 886 144 289 296 981 799 379 726 154 536 934 427 269 602 523 541 994 315 611 660 841 495 242 70 399 855 988 949 676 820 264 12 41 585 960 552 876 116 647 238 694 801 9...

output:

1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1...

result:

ok 1000 numbers

Test #28:

score: 0
Accepted
time: 7ms
memory: 9816kb

input:

1000 1000
102 468 438 833 811 970 821 318 789 478 762 17 656 877 672 874 35 86 850 491 614 107 421 71 537 773 297 728 751 357 398 490 713 50 896 802 469 816 13 772 483 14 553 199 26 905 48 101 252 298 361 760 284 637 371 295 385 384 364 142 100 649 520 955 720 640 389 380 464 463 148 15 476 106 511 ...

output:

173.1780000000
201.2680000000
121.2170000000
673.0980000000
677.4930000000
682.7820000000
666.5210000000
57.2530000000
952.2270000000
276.9970000000
524.1410000000
603.0320000000
1.0000000000
886.1430000000
545.2470000000
680.2650000000
59.5410000000
668.7320000000
643.7090000000
101.0250000000
404....

result:

ok 1000 numbers

Test #29:

score: 0
Accepted
time: 364ms
memory: 43364kb

input:

300000 10
100163 199441 107576 272955 159138 175728 278205 153152 35458 167071 137298 53 156083 161962 187743 921 292697 137977 203118 140281 143487 212439 11839 118131 264455 43059 49523 107694 77229 1464 80054 287475 255817 173531 187163 13087 275101 215163 209999 169678 188485 85798 297949 270357...

output:

8465.7000000000
145502.8000000000
145150.6000000000
120904.6000000000
63821.6000000000
39405.1000000000
46820.7000000000
56518.6000000000
18538.3000000000
115369.9000000000
34413.6000000000
219717.1000000000
88880.9000000000
53602.3000000000
163398.1000000000
161492.6000000000
60581.2000000000
11143...

result:

ok 300000 numbers

Test #30:

score: 0
Accepted
time: 1485ms
memory: 1246652kb

input:

300000 300000
3 8653 56239 219542
5 95662 37358 105119 150584 77480
6 4048 258603 75954 263320 95295 37358
3 140501 171436 76539
5 15612 257530 199498 157762 182596
3 265333 255908 182573
4 166010 291455 256151 192163
6 83616 1577 37358 263781 40744 247124
3 238092 37358 273714
3 240019 28215 120700...

output:

88430.6060000000
98502.1698866667
63674.9290800000
44218.0197466667
98502.1698866667
98502.1698866667
23481.3373633333
98502.1698866667
53398.4028666667
45661.8911466667
98502.1698866667
58976.1036766667
4529.5358333333
84590.6026833333
98502.1698866667
84169.8109433333
23136.8801466667
72204.526366...

result:

ok 300000 numbers

Test #31:

score: 0
Accepted
time: 1244ms
memory: 1230784kb

input:

15000 300000
4 11232 643 2833 3527
2 13308 3480
4 5510 9655 46 11069
3 11956 3527 2052
2 8610 11234
2 7629 5293
5 6492 3480 7688 2774 14036
3 3480 10795 11630
4 4557 14572 2052 3756
0
1 1763
5 10520 4172 5178 9538 6379
0
1 10183
2 13021 5293
2 3527 1804
2 9115 12418
3 14914 11308 5688
3 2052 13021 1...

output:

5254.0702733333
10143.0992600000
10252.9794833333
6061.4365033333
329.4141100000
1316.2249866667
2758.6162566667
8302.3257933333
3575.0992833333
9264.0882466667
6691.7742100000
8132.1906433333
5909.6813000000
7355.3708633333
11301.9984533333
3219.1375666667
1825.5491700000
8315.8265000000
2898.42922...

result:

ok 15000 numbers

Test #32:

score: 0
Accepted
time: 1571ms
memory: 1248368kb

input:

300000 300000
2 208568 111922
4 91432 77323 125218 198677
3 94774 1393 119875
5 207083 61681 183716 51268 151727
1 250066
1 197792
2 259534 214913
6 172941 137989 157017 62295 272066 208917
2 163103 136199
3 119936 172317 7851
3 20633 21474 204622
1 205687
3 214744 84964 125285
3 46467 63138 881
4 1...

output:

43063.4171533333
162835.6039200000
160498.4537633333
140417.7613833333
99187.9451333333
96812.4675833333
88942.5888000000
30493.7753933333
169560.4401533333
76390.1761966667
65174.7809233333
180265.8304200000
156978.3973700000
172347.3124833333
56928.5671766667
101454.2320966667
10268.8330500000
847...

result:

ok 300000 numbers

Test #33:

score: 0
Accepted
time: 1329ms
memory: 1227372kb

input:

600 300000
6 141 100 306 519 87 277
5 181 401 88 217 19
5 561 54 91 85 279
2 17 74
4 562 472 30 506
6 464 88 228 492 142 445
1 167
2 228 87
3 174 236 385
8 590 417 148 183 427 110 573 194
4 308 424 429 167
3 369 72 382
2 578 457
2 403 73
1 171
4 443 306 583 146
3 540 442 583
2 541 46
5 54 322 432 10...

output:

357.3051133333
442.4966533333
178.0022966667
243.7438300000
344.7653966667
412.0830266667
112.4246633333
594.0560200000
358.4018300000
201.6649800000
550.5695533333
460.9772266667
160.1883000000
84.6691200000
3.9026233333
196.7332933333
93.0218700000
5.5680600000
98.4496866667
535.8564666667
26.1236...

result:

ok 600 numbers

Test #34:

score: 0
Accepted
time: 1021ms
memory: 1224100kb

input:

300000 300000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1...

result:

ok 300000 numbers

Test #35:

score: 0
Accepted
time: 1347ms
memory: 1244320kb

input:

300000 300000
150000 152378 20536 230896 243531 130262 222665 146584 12680 200961 255680 2766 29860 293060 200643 182208 86955 290788 137148 79258 187602 223959 170916 247928 46417 10375 136965 171609 213627 82670 98292 163902 213617 207226 53553 128847 234468 29348 152905 210512 265156 144800 22868...

output:

1.5000000000
100000.0000000000
99999.5000000000
99999.5000000000
2.0000000000
1.5000000000
1.0000000000
1.5000000000
2.0000000000
100000.0000000000
99999.5000000000
100000.0000000000
100000.0000000000
100000.0000000000
100000.0000000000
99999.5000000000
99999.5000000000
1.5000000000
2.0000000000
1.5...

result:

ok 300000 numbers

Test #36:

score: 0
Accepted
time: 1010ms
memory: 1226992kb

input:

3000 300000
1500 1243 2819 1259 2982 2440 368 2897 2784 102 1448 137 96 2361 2465 1233 28 150 9 2924 1872 2732 2744 185 239 587 2016 1383 1517 2006 2722 2725 2275 1122 971 859 2533 2918 1488 742 869 227 258 2925 2083 901 2089 2959 2264 1213 782 2442 330 2038 1434 2846 1024 1870 2476 402 2679 1149 17...

output:

1.8000000000
1.8400000000
999.6350000000
999.6900000000
999.5550000000
999.5300000000
999.5300000000
999.5750000000
999.6650000000
1.8200000000
999.6750000000
999.5950000000
999.6700000000
1.8100000000
1.7900000000
999.5600000000
999.6250000000
1.7600000000
999.6700000000
1.9200000000
999.6900000000...

result:

ok 3000 numbers