QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#688472#7753. Energy Distributionicpc_zhzx034#WA 22ms3888kbC++141.7kb2024-10-30 09:47:492024-10-30 09:47:50

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2024-10-30 09:47:50]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:3888kb
  • [2024-10-30 09:47:49]
  • 提交

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'