QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#688472 | #7753. Energy Distribution | icpc_zhzx034# | WA | 22ms | 3888kb | C++14 | 1.7kb | 2024-10-30 09:47:49 | 2024-10-30 09:47:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pr;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
// #define mid ((l+r)>>1)
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
ll x=0, f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
return x*f;
}
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
ll ans=1, base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod; b>>=1;
}
return ans;
}
void init(){ }
ll n,w[15][15]; double p[15];
void adjust(ll x,ll y){
double sum = p[x] + p[y];
double F = 0, S = 0;
for(ll i=1;i<=n;i++){
if(i==x || i==y) continue;
F += p[i]*w[i][x] - p[i]*w[i][y];
}
F += w[x][y]*sum;
S -= w[x][y];
if(w[x][y]){
p[x] = - F / (2.0 * S);
if(p[x] < 0) p[x] = 0;
if(p[x] > sum) p[x] = sum;
p[y] = sum - p[x];
}
else {
if(F < 0) p[x] = 0, p[y] = sum;
else if(F > 0) p[x] = sum, p[y] = 0;
else p[x] = sum / 2, p[y] = sum / 2;
}
}
void procedure(){
n=read();
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++) w[i][j]=read();
}
for(ll i=1;i<=n;i++) p[i]=1.0/n;
ll T = 50000;
while(T--){
for(ll i=1;i<=n;i++){
for(ll j=i+1;j<=n;j++) adjust(i, j);
}
}
double ans = 0;
for(ll i=1;i<=n;i++){
for(ll j=i+1;j<=n;j++)
ans += p[i] * p[j] * w[i][j];
}
printf("%.10lf\n", ans);
}
int main(){
#ifdef LOCAL
assert(freopen("input.txt","r",stdin));
assert(freopen("output.txt","w",stdout));
#endif
ll T=1;
init();
while(T--) procedure();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3888kb
input:
2 0 1 1 0
output:
0.2500000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
3 0 2 1 2 0 2 1 2 0
output:
0.5714285714
result:
ok found '0.5714286', expected '0.5714290', error '0.0000004'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3884kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.5000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 3ms
memory: 3820kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
0.7500000000
result:
ok found '0.7500000', expected '0.7500000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 4ms
memory: 3832kb
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.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 8ms
memory: 3832kb
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.8571428571
result:
ok found '2.8571429', expected '2.8571430', error '0.0000001'
Test #7:
score: 0
Accepted
time: 10ms
memory: 3820kb
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.5115848007
result:
ok found '12.5115848', expected '12.5115850', error '0.0000000'
Test #8:
score: 0
Accepted
time: 14ms
memory: 3836kb
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.0091178965
result:
ok found '25.0091179', expected '25.0091180', error '0.0000000'
Test #9:
score: -100
Wrong Answer
time: 22ms
memory: 3828kb
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.7908670025
result:
wrong answer 1st numbers differ - expected: '119.0000000', found: '113.7908670', error = '0.0437742'