QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#383164#7753. Energy DistributionhelcsnewsxdWA 986ms3988kbC++201.7kb2024-04-09 00:20:072024-04-09 00:20:07

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2024-04-09 00:20:07]
  • 评测
  • 测评结果:WA
  • 用时:986ms
  • 内存:3988kb
  • [2024-04-09 00:20:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define fore(i, a, b) for(ll i = a, bella = b; i < bella; i++)
#define mset(a, b) memset(a, b, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define SZ(a) ll(a.size())
#define fst first
#define snd second
#define pb push_back
#define FIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

typedef double ld;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

const ll MAXN = 15;
ll w[MAXN][MAXN], n;
ld v[MAXN];

ld calc() {
    ld ret = 0;
    fore(i, 0, n) fore(j, i + 1, n) ret += v[i] * v[j] * ld(w[i][j]);
    return ret;
}

void upd(ll a, ll b) {
    ld sum = v[a] + v[b];
    ld s = 0, e = v[a] + v[b];
    ll it = 100;
    while(it--) {
        ld m0 = (s * 2.0 + e) / 3.0, m1 = (s + e * 2.0) / 3.0;
        
        ld a0 = m0, b0 = sum - a0;
        ld a1 = m1, b1 = sum - a1;

        v[a] = a0, v[b] = b0;
        ld c0 = calc();

        v[a] = a1, v[b] = b1;
        ld c1 = calc();

        if(c0 < c1) {
            s = m0;
            v[a] = s, v[b] = sum - v[a];
        } else {
            e = m1;
            v[a] = e, v[b] = sum - v[a];
        }
    }
}

int main() { FIO;

    cin >> n;
    fore(i, 0, n) fore(j, 0, n) cin >> w[i][j];

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> distr(0, n-1);
    auto cl=clock();
    while(ld(clock() - cl)/CLOCKS_PER_SEC < 0.98) {
        fore(i, 0, n) v[i] = 1.0/ld(n);

        ll it = 1000;
        while(it--) {
            ll a = distr(rng), b;
            while(a == b) b = distr(rng);

            upd(a, b);
        }
    }
    
    cout << fixed << setprecision(12) << calc() << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 980ms
memory: 3892kb

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: 981ms
memory: 3848kb

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: 978ms
memory: 3952kb

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: 980ms
memory: 3936kb

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: 982ms
memory: 3956kb

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: 983ms
memory: 3900kb

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: 986ms
memory: 3988kb

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: 986ms
memory: 3880kb

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: -100
Wrong Answer
time: 985ms
memory: 3936kb

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

result:

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