QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288164#7753. Energy DistributionUNos_maricones#WA 890ms3864kbC++201.3kb2023-12-22 08:20:382023-12-22 08:20:39

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2023-12-22 08:20:39]
  • 评测
  • 测评结果:WA
  • 用时:890ms
  • 内存:3864kb
  • [2023-12-22 08:20:38]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int main()
{
  int n;
  scanf("%d", &n );

  vector< vector< int > > w( n, vector< int> ( n ) );
  for( int i = 0; i < n; ++ i )
    for( int j = 0; j < n; ++ j )
      scanf("%d", &w[i][j] );

  double ans = 0.0;
  auto score = [&]( vector< double > &e )
  {
    double sc = 0;

    for( int i = 0; i < n; ++ i )
      for( int j = i + 1; j < n; ++ j )
        sc += 1.0 * e[i] * e[j] * w[i][j];

    ans = max( ans, sc );
    return sc;
  };

  uniform_int_distribution<int> dis(0, n - 1);

  vector< double > e ( n, 1.0 / n );

  while( 1.0 * clock() / CLOCKS_PER_SEC < 0.9 )
  {
    int x = dis( rng ), y = dis( rng );
    if( x == y ) continue;

    const double sum = e[x] + e[y];

    double low = 0.0, high = sum;
    for( int it = 0; it < 100; ++ it )
    {
      const double x1 = low + ( high - low ) / 3.0L;
      auto e1 = e;
      e1[x] = x1, e1[y] = sum - x1;

      const double x2 = high - ( high - low ) / 3.0L;
      auto e2 = e;
      e2[x] = x2, e2[y] = sum - x2;

      if( score( e1 ) > score( e2 ) )
        high = x2;
      else
        low = x1;
    }
    
    e[x] = low, e[y] = sum - low;
  }

  printf("%0.12f\n", ans );
  return 0;
}


详细

Test #1:

score: 100
Accepted
time: 862ms
memory: 3800kb

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: 855ms
memory: 3804kb

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: 866ms
memory: 3804kb

input:

3
0 1 2
1 0 1
2 1 0

output:

0.500000000001

result:

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

Test #4:

score: 0
Accepted
time: 874ms
memory: 3820kb

input:

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

output:

0.750000000002

result:

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

Test #5:

score: 0
Accepted
time: 875ms
memory: 3748kb

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.000000000002

result:

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

Test #6:

score: 0
Accepted
time: 882ms
memory: 3804kb

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.857142857146

result:

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

Test #7:

score: 0
Accepted
time: 890ms
memory: 3864kb

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.511584800755

result:

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

Test #8:

score: 0
Accepted
time: 890ms
memory: 3760kb

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.009117896546

result:

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

Test #9:

score: -100
Wrong Answer
time: 882ms
memory: 3824kb

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:

113.790867002600

result:

wrong answer 1st numbers differ - expected: '119.0000000', found: '113.7908670', error = '0.0437742'