QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383162#7753. Energy DistributionhelcsnewsxdRE 0ms0kbC++201.7kb2024-04-09 00:19:402024-04-09 00:19:45

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2024-04-09 00:19:45]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-09 00:19:40]
  • 提交

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 int 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;
}

详细

Test #1:

score: 0
Runtime Error

input:

2
0 1
1 0

output:


result: