QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#383164 | #7753. Energy Distribution | helcsnewsxd | WA | 986ms | 3988kb | C++20 | 1.7kb | 2024-04-09 00:20:07 | 2024-04-09 00:20:07 |
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 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'