QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404905#7753. Energy DistributionSorting#WA 1ms3952kbC++201.9kb2024-05-04 22:55:122024-05-04 22:55:13

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2024-05-04 22:55:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3952kb
  • [2024-05-04 22:55:12]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using ll = long long;
using vd = vector<double>;
using vvd = vector<vd>;


#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const double eps = 1e-11;

int solveLinear(vector<vd>& A, vd& b, vd& x) {
	int n = sz(A), m = sz(x), rank = 0, br, bc;
	if (n) assert(sz(A[0]) == m);
	vi col(m); iota(all(col), 0);

	rep(i,0,n) {
		double v, bv = 0;
		rep(r,i,n) rep(c,i,m)
			if ((v = fabs(A[r][c])) > bv)
				br = r, bc = c, bv = v;
		if (bv <= eps) {
			rep(j,i,n) if (fabs(b[j]) > eps) return -1;
			break;
		}
		swap(A[i], A[br]);
		swap(b[i], b[br]);
		swap(col[i], col[bc]);
		rep(j,0,n) swap(A[j][i], A[j][bc]);
		bv = 1/A[i][i];
		rep(j,i+1,n) {
			double fac = A[j][i] * bv;
			b[j] -= fac * b[i];
			rep(k,i+1,m) A[j][k] -= fac*A[i][k];
		}
		rank++;
	}

	x.assign(m, 0);
	for (int i = rank; i--;) {
		b[i] /= A[i][i];
		x[col[i]] = b[i];
		rep(j,0,i) b[j] -= A[j][i] * b[i];
	}
	return rank; // (multiple solutions if rank < m)
}

void solve() {
    int n;
    cin >> n;

    vector<vd> W(n, vd(n));
    // vector<vector<double>> W(n, vd(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> W[i][j];
        }
    }

    vd ones(n, 1);
    vd out(n);

    vvd W2 = W;
    int rank = solveLinear(W2, ones, out);

    double sum = accumulate(out.begin(), out.end(), 0.0);
    for(int i = 0; i < n; i++) {
        out[i] /= sum;
        // cerr << out[i] << ' ';
    }

    double ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            ans += out[i] * out[j] * W[i][j];
        }
    }
    cout << setprecision(20) << fixed << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3952kb

input:

2
0 1
1 0

output:

0.25000000000000000000

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

3
0 2 1
2 0 2
1 2 0

output:

0.57142857142857139685

result:

ok found '0.5714286', expected '0.5714290', error '0.0000004'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

3
0 1 2
1 0 1
2 1 0

output:

0.50000000000000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3868kb

input:

4
0 3 1 0
3 0 1 0
1 1 0 2
0 0 2 0

output:

0.42857142857142871417

result:

wrong answer 1st numbers differ - expected: '0.7500000', found: '0.4285714', error = '0.3214286'