QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#268927#7753. Energy DistributionSATSKYAC ✓1ms4044kbC++201.4kb2023-11-29 01:08:292024-10-31 10:27:01

Judging History

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

  • [2024-10-31 10:27:01]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1ms
  • 内存:4044kb
  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2023-11-29 01:08:31]
  • 评测
  • 测评结果:100
  • 用时:1ms
  • 内存:3780kb
  • [2023-11-29 01:08:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;const double eps=1e-10;
struct Mat{int n,m;vector<vector<double>>mat;vector<int>sol;Mat(int _n,int _m){ini(_n,_m);}
	void ini(int _n,int _m){n=_n,m=_m,mat.resize(n,vector<double>(m,0));}
	int Gauss(){int pt=0;for(int c=0;c<n;c++){int t=pt;for(int i=pt;i<n;i++)if(abs(mat[i][c])>abs(mat[t][c]))t=i;
		if(abs(mat[t][c])<eps)continue;swap(mat[t],mat[pt]);for(int i=m-1;i>=c;i--)mat[pt][i]/=mat[pt][c];
		for(int i=0;i<n;i++)if(pt!=i&&abs(mat[i][c])>eps)for(int j=m-1;j>=c;j--)mat[i][j]-=mat[pt][j]*mat[i][c];pt++;}
		for(int i=pt+1;i<n;i++)if(abs(mat[i][m-1])>eps)return 0;return 2-bool(pt==n);}};
int main(){ios::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;vector<vector<int>>a(n,vector<int>(n));
	for(auto &k:a)for(auto&kk:k)cin>>kk;int B=(1<<n);double mx=0;
	for(int k=1;k<B;k++){
		vector<int>arr;for(int i=0;i<n;i++)if(k&(1<<i))arr.push_back(i);int siz=arr.size();
		Mat A(siz,siz+1);for(int i=0;i<siz;A.mat[i][siz]=1,i++)for(int j=0;j<siz;j++)
			if(i!=j)A.mat[i][j]=(i<j)?a[arr[i]][arr[j]]:a[arr[j]][arr[i]];
		if(A.Gauss()!=1)continue;vector<double>res(siz,0);double sum=0;bool jud=0;
		for(int i=0;i<siz;i++)res[i]=A.mat[i][siz],sum+=res[i],jud|=(res[i]<-eps);
		if(jud||abs(sum)<eps)continue;for(auto &k:res)k/=sum;sum=0;
		for(int i=0;i<siz;i++)for(int j=i+1;j<siz;j++)sum+=res[i]*res[j]*a[arr[i]][arr[j]];
		mx=max(mx,sum);}cout<<fixed<<setprecision(12)<<mx;}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3908kb

input:

2
0 1
1 0

output:

0.250000000000

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #2:

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

input:

3
0 2 1
2 0 2
1 2 0

output:

0.571428571429

result:

ok found '0.5714286', expected '0.5714290', error '0.0000004'

Test #3:

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

input:

3
0 1 2
1 0 1
2 1 0

output:

0.500000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

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

input:

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

output:

0.750000000000

result:

ok found '0.7500000', expected '0.7500000', error '0.0000000'

Test #5:

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

input:

5
0 0 0 4 4
0 0 2 0 4
0 2 0 2 0
4 0 2 0 0
4 4 0 0 0

output:

1.000000000000

result:

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

Test #6:

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

input:

6
0 9 5 5 10 6
9 0 0 0 0 1
5 0 0 0 3 0
5 0 0 0 10 5
10 0 3 10 0 0
6 1 0 5 0 0

output:

2.857142857143

result:

ok found '2.8571429', expected '2.8571430', error '0.0000000'

Test #7:

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

input:

7
0 0 0 0 50 10 45
0 0 0 0 0 3 1
0 0 0 0 0 4 16
0 0 0 0 44 0 0
50 0 0 44 0 37 6
10 3 4 0 37 0 2
45 1 16 0 6 2 0

output:

12.511584800741

result:

ok found '12.5115848', expected '12.5115850', error '0.0000000'

Test #8:

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

input:

8
0 0 56 0 0 58 16 0
0 0 37 20 0 82 0 0
56 37 0 0 98 0 83 0
0 20 0 0 0 0 100 0
0 0 98 0 0 62 29 0
58 82 0 0 62 0 43 0
16 0 83 100 29 43 0 4
0 0 0 0 0 0 4 0

output:

25.009117896522

result:

ok found '25.0091179', expected '25.0091180', error '0.0000000'

Test #9:

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

input:

9
0 0 0 135 0 0 0 448 476
0 0 0 0 0 0 208 17 0
0 0 0 467 1 0 0 0 134
135 0 467 0 0 0 92 369 207
0 0 1 0 0 176 0 235 0
0 0 0 0 176 0 65 363 413
0 208 0 92 0 65 0 0 0
448 17 0 369 235 363 0 0 0
476 0 134 207 0 413 0 0 0

output:

119.000000000000

result:

ok found '119.0000000', expected '119.0000000', error '0.0000000'

Test #10:

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

input:

10
0 0 0 289 0 397 0 0 140 155
0 0 28 101 35 614 0 0 545 300
0 28 0 0 329 702 0 242 0 298
289 101 0 0 0 0 0 0 720 0
0 35 329 0 0 0 0 38 0 0
397 614 702 0 0 0 229 0 0 0
0 0 0 0 0 229 0 317 0 0
0 0 242 0 38 0 317 0 961 309
140 545 0 720 0 0 0 961 0 92
155 300 298 0 0 0 0 309 92 0

output:

240.250000000000

result:

ok found '240.2500000', expected '240.2500000', error '0.0000000'

Test #11:

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

input:

10
0 295 2 809 333 880 284 305 41 295
295 0 512 1000 281 153 42 550 962 930
2 512 0 727 709 969 665 973 301 410
809 1000 727 0 282 551 960 804 274 956
333 281 709 282 0 613 505 406 896 441
880 153 969 551 613 0 769 770 40 288
284 42 665 960 505 769 0 919 989 490
305 550 973 804 406 770 919 0 400 209...

output:

327.373658966686

result:

ok found '327.3736590', expected '327.3736590', error '0.0000000'

Test #12:

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

input:

10
0 403 2 164 0 399 279 156 109 472
403 0 292 279 100 326 153 124 103 426
2 292 0 0 58 87 0 177 324 334
164 279 0 0 256 188 0 257 467 23
0 100 58 256 0 453 75 21 0 309
399 326 87 188 453 0 0 319 395 434
279 153 0 0 75 0 0 342 431 72
156 124 177 257 21 319 342 0 265 0
109 103 324 467 0 395 431 265 0...

output:

155.370358145035

result:

ok found '155.3703581', expected '155.3703580', error '0.0000000'

Test #13:

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

input:

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

output:

3.133273703041

result:

ok found '3.1332737', expected '3.1332740', error '0.0000001'

Test #14:

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

input:

10
0 52 25 22 39 47 85 63 8 2
52 0 0 87 2 20 50 87 88 6
25 0 0 77 27 58 81 0 98 0
22 87 77 0 28 0 49 53 59 0
39 2 27 28 0 0 65 76 0 0
47 20 58 0 0 0 88 0 0 3
85 50 81 49 65 88 0 60 85 1
63 87 0 53 76 0 60 0 76 88
8 88 98 59 0 0 85 76 0 0
2 6 0 0 0 3 1 88 0 0

output:

29.542946848427

result:

ok found '29.5429468', expected '29.5429470', error '0.0000000'

Test #15:

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

input:

10
0 79 0 192 19 79 0 0 0 0
79 0 0 0 164 100 74 0 26 176
0 0 0 0 184 153 152 0 0 39
192 0 0 0 0 90 54 0 18 0
19 164 184 0 0 195 107 0 8 53
79 100 153 90 195 0 0 124 96 149
0 74 152 54 107 0 0 181 28 0
0 0 0 0 0 124 181 0 0 3
0 26 0 18 8 96 28 0 0 0
0 176 39 0 53 149 0 3 0 0

output:

59.383410497166

result:

ok found '59.3834105', expected '59.3834100', error '0.0000000'

Test #16:

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

input:

10
0 416 0 476 0 0 2 0 204 750
416 0 0 850 0 0 471 0 835 67
0 0 0 0 184 274 0 135 557 709
476 850 0 0 904 0 0 556 0 0
0 0 184 904 0 141 0 0 0 0
0 0 274 0 141 0 0 167 486 0
2 471 0 0 0 0 0 0 617 0
0 0 135 556 0 167 0 0 241 226
204 835 557 0 0 486 617 241 0 0
750 67 709 0 0 0 0 226 0 0

output:

226.000000000000

result:

ok found '226.0000000', expected '226.0000000', error '0.0000000'

Test #17:

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

input:

10
0 777 0 543 382 5 266 0 255 250
777 0 0 0 0 0 566 637 0 469
0 0 0 0 183 671 0 711 335 294
543 0 0 0 929 475 0 925 0 46
382 0 183 929 0 777 674 399 0 732
5 0 671 475 777 0 0 814 453 0
266 566 0 0 674 0 0 0 0 703
0 637 711 925 399 814 0 0 654 928
255 0 335 0 0 453 0 654 0 0
250 469 294 46 732 0 703...

output:

272.271056742292

result:

ok found '272.2710567', expected '272.2710570', error '0.0000000'

Test #18:

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

input:

10
0 1 0 0 0 0 4 0 0 0
1 0 0 2 3 0 5 0 0 0
0 0 0 1 0 0 0 0 0 0
0 2 1 0 0 2 3 0 0 3
0 3 0 0 0 0 0 0 0 1
0 0 0 2 0 0 4 0 0 0
4 5 0 3 0 4 0 0 3 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 3 0 0 1
0 0 0 3 1 0 0 5 1 0

output:

1.250000000000

result:

ok found '1.2500000', expected '1.2500000', error '0.0000000'

Test #19:

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

input:

10
0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1
0 1 1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 0

output:

0.250000000000

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #20:

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

input:

10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 622 0 0 0 0 0 0
0 0 622 0 0 0 0 0 0 585
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 982
0 0 0 0 0 0 0 0 0 0
0 0 0 585 0 0 0 982 0 0

output:

245.500000000000

result:

ok found '245.5000000', expected '245.5000000', error '0.0000000'

Test #21:

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

input:

10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 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:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Extra Test:

score: 0
Extra Test Passed