QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#383141 | #7753. Energy Distribution | helcsnewsxd | WA | 872ms | 4000kb | C++20 | 2.2kb | 2024-04-08 23:54:26 | 2024-04-08 23:54:26 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'