QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383141#7753. Energy DistributionhelcsnewsxdWA 872ms4000kbC++202.2kb2024-04-08 23:54:262024-04-08 23:54:26

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2024-04-08 23:54:26]
  • 评测
  • 测评结果:WA
  • 用时:872ms
  • 内存:4000kb
  • [2024-04-08 23:54:26]
  • 提交

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 long double ld;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

const ll MAXN = 15;
const ld EPS = 1e-6;
ll w[MAXN][MAXN], n;
ld v[MAXN], sum[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 s = 0, e = v[a] + v[b];
    ll it = 50;
    while(it-- && (e - s) > EPS) {
        ld m0 = (s * 2.0 + e) / 3.0, m1 = (s + e * 2.0) / 3.0;
        
        ld a0 = m0, b0 = v[a] + v[b] - a0;
        ld a1 = m1, b1 = v[a] + v[b] - a1;

        ld c0 = a0 * sum[a] + b0 * sum[b] + ld(w[a][b]) * (2.0 * a0 * b0 - a0 * v[b] - v[a] * b0);
        ld c1 = a1 * sum[a] + b1 * sum[b] + ld(w[a][b]) * (2.0 * a1 * b1 - a1 * v[b] - v[a] * b1);

        if((c0 - c1) > EPS) e = m1;
        else s = m0;
    }

    sum[a] = sum[b] = 0;
    fore(i, 0, n) if(i != a && i != b) sum[i] -= v[a] * ld(w[i][a]) + v[b] * ld(w[i][b]);

    ld nwA = s, nwB = v[a] + v[b] - nwA;
    v[a] = nwA, v[b] = nwB;

    fore(i, 0, n) {
        sum[a] += v[i] * ld(w[a][i]);
        sum[b] += v[i] * ld(w[b][i]);

        if(i != a && i != b) sum[i] += v[a] * ld(w[i][a]) + v[b] * ld(w[i][b]);
    }
}

int main() { FIO;

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

    fore(i, 0, n) v[i] = 1.0/ld(n);
    fore(i, 0, n) fore(j, 0, n) sum[i] += v[j] * ld(w[i][j]);

    // cout << "Valores iniciales:\n";
    // fore(i, 0, n) cout << fixed << setprecision(12) << v[i] << '\n';

    auto cl=clock();
    while(ld(clock() - cl)/CLOCKS_PER_SEC < 0.99) {
        ll a = rand() % n, b = a;
        while(a == b) b = rand() % n;

        upd(a, b);
    }

    // cout << "Valores finales:\n";
    // fore(i, 0, n) cout << fixed << setprecision(12) << v[i] << '\n';

    // cout << "Respuesta:\n";
    cout << fixed << setprecision(12) << calc() << '\n';

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 869ms
memory: 4000kb

input:

2
0 1
1 0

output:

0.249999296882

result:

ok found '0.2499993', expected '0.2500000', error '0.0000007'

Test #2:

score: -100
Wrong Answer
time: 872ms
memory: 3948kb

input:

3
0 2 1
2 0 2
1 2 0

output:

0.568186824076

result:

wrong answer 1st numbers differ - expected: '0.5714290', found: '0.5681868', error = '0.0032422'