QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297679 | #7753. Energy Distribution | ucup-team139 | AC ✓ | 5ms | 3828kb | C++23 | 3.2kb | 2024-01-04 22:35:42 | 2024-01-04 22:35:44 |
Judging History
你现在查看的是测评时间为 2024-01-04 22:35:44 的历史记录
- [2024-10-31 10:22:30]
- hack成功,自动添加数据
- (/hack/1089)
- [2024-01-04 22:35:42]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
#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()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double T; //oppure modular<mod>
typedef vector<T> vd;
const double eps = 1e-8;
vi col; //globale per ricavare il sottospazio
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);
col.resize(m); iota(all(col), 0);
rep(i,0,n) {
T 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 = T(1)/A[i][i];
rep(j,i+1,n) {
T 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, T(0));
for (int i = rank; i--;) {
b[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 t){
int n;
cin>>n;
vector w(n,vector(n,0));
for(auto &i : w)for(auto &j : i)cin>>j;
double ans = 0.0;
for(int mask=1;mask<(1<<n);mask++){
bool ok=true;
vector<int> nodi;
for(int j=0;j<n;j++){
if(mask&(1<<j))nodi.push_back(j);
}
for(auto j : nodi){
for(auto k : nodi){
if(j==k)continue;
assert(w[j][k]==w[k][j]);
if(w[j][k]==0)ok=false;
}
}
if(!ok)continue;
vector<vd> A;
vd B,x;
x.resize(nodi.size());
for(auto a : nodi){
for(auto b : nodi){
if(a==b)continue;
vd tmp;
for(auto i : nodi){
if(i==a)tmp.push_back(-w[a][b]);
else if(i==b)tmp.push_back(w[a][b]);
else tmp.push_back(w[a][i]-w[b][i]);
}
A.push_back(tmp);
B.push_back(0);
}
}
A.push_back(vd(nodi.size(),1));
B.push_back(1);
int rank = solveLinear(A,B,x);
//assert(rank!=-1);
if(rank==-1)continue;
assert(rank==(int)x.size());
double curr=0;
for(int i=0;i<(int)x.size();i++){
if(x[i]<-1e-8){
curr=0.0;
break;
}
for(int j=0;j<i;j++){
curr+=x[i]*x[j]*w[nodi[i]][nodi[j]];
}
}
ans=max(ans,curr);
}
cout<<setprecision(20)<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
input:
2 0 1 1 0
output:
0.25
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
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: 3644kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.5
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
0.75
result:
ok found '0.7500000', expected '0.7500000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3824kb
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
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3656kb
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.8571428571428567622
result:
ok found '2.8571429', expected '2.8571430', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3828kb
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.511584800741426093
result:
ok found '12.5115848', expected '12.5115850', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3684kb
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.009117896522486291
result:
ok found '25.0091179', expected '25.0091180', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3764kb
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:
119
result:
ok found '119.0000000', expected '119.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
10 0 0 0 289 0 397 0 0 140 155 0 0 28 101 35 614 0 0 545 300 0 28 0 0 329 702 0 242 0 298 289 101 0 0 0 0 0 0 720 0 0 35 329 0 0 0 0 38 0 0 397 614 702 0 0 0 229 0 0 0 0 0 0 0 0 229 0 317 0 0 0 0 242 0 38 0 317 0 961 309 140 545 0 720 0 0 0 961 0 92 155 300 298 0 0 0 0 309 92 0
output:
240.25
result:
ok found '240.2500000', expected '240.2500000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 5ms
memory: 3784kb
input:
10 0 295 2 809 333 880 284 305 41 295 295 0 512 1000 281 153 42 550 962 930 2 512 0 727 709 969 665 973 301 410 809 1000 727 0 282 551 960 804 274 956 333 281 709 282 0 613 505 406 896 441 880 153 969 551 613 0 769 770 40 288 284 42 665 960 505 769 0 919 989 490 305 550 973 804 406 770 919 0 400 209...
output:
327.37365896668552523
result:
ok found '327.3736590', expected '327.3736590', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
10 0 403 2 164 0 399 279 156 109 472 403 0 292 279 100 326 153 124 103 426 2 292 0 0 58 87 0 177 324 334 164 279 0 0 256 188 0 257 467 23 0 100 58 256 0 453 75 21 0 309 399 326 87 188 453 0 0 319 395 434 279 153 0 0 75 0 0 342 431 72 156 124 177 257 21 319 342 0 265 0 109 103 324 467 0 395 431 265 0...
output:
155.3703581450353397
result:
ok found '155.3703581', expected '155.3703580', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
10 0 3 10 8 0 3 3 8 9 6 3 0 6 10 0 10 9 9 4 9 10 6 0 7 1 5 6 8 0 0 8 10 7 0 10 6 0 6 9 4 0 0 1 10 0 1 0 2 0 1 3 10 5 6 1 0 6 4 0 4 3 9 6 0 0 6 0 10 0 8 8 9 8 6 2 4 10 0 0 2 9 4 0 9 0 0 0 0 0 10 6 9 0 4 1 4 8 2 10 0
output:
3.133273703041145275
result:
ok found '3.1332737', expected '3.1332740', error '0.0000001'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
10 0 52 25 22 39 47 85 63 8 2 52 0 0 87 2 20 50 87 88 6 25 0 0 77 27 58 81 0 98 0 22 87 77 0 28 0 49 53 59 0 39 2 27 28 0 0 65 76 0 0 47 20 58 0 0 0 88 0 0 3 85 50 81 49 65 88 0 60 85 1 63 87 0 53 76 0 60 0 76 88 8 88 98 59 0 0 85 76 0 0 2 6 0 0 0 3 1 88 0 0
output:
29.54294684842743024
result:
ok found '29.5429468', expected '29.5429470', error '0.0000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
10 0 79 0 192 19 79 0 0 0 0 79 0 0 0 164 100 74 0 26 176 0 0 0 0 184 153 152 0 0 39 192 0 0 0 0 90 54 0 18 0 19 164 184 0 0 195 107 0 8 53 79 100 153 90 195 0 0 124 96 149 0 74 152 54 107 0 0 181 28 0 0 0 0 0 0 124 181 0 0 3 0 26 0 18 8 96 28 0 0 0 0 176 39 0 53 149 0 3 0 0
output:
59.383410497165868946
result:
ok found '59.3834105', expected '59.3834100', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
10 0 416 0 476 0 0 2 0 204 750 416 0 0 850 0 0 471 0 835 67 0 0 0 0 184 274 0 135 557 709 476 850 0 0 904 0 0 556 0 0 0 0 184 904 0 141 0 0 0 0 0 0 274 0 141 0 0 167 486 0 2 471 0 0 0 0 0 0 617 0 0 0 135 556 0 167 0 0 241 226 204 835 557 0 0 486 617 241 0 0 750 67 709 0 0 0 0 226 0 0
output:
226
result:
ok found '226.0000000', expected '226.0000000', error '0.0000000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
10 0 777 0 543 382 5 266 0 255 250 777 0 0 0 0 0 566 637 0 469 0 0 0 0 183 671 0 711 335 294 543 0 0 0 929 475 0 925 0 46 382 0 183 929 0 777 674 399 0 732 5 0 671 475 777 0 0 814 453 0 266 566 0 0 674 0 0 0 0 703 0 637 711 925 399 814 0 0 654 928 255 0 335 0 0 453 0 654 0 0 250 469 294 46 732 0 703...
output:
272.27105674229198939
result:
ok found '272.2710567', expected '272.2710570', error '0.0000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
10 0 1 0 0 0 0 4 0 0 0 1 0 0 2 3 0 5 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 1 0 0 2 3 0 0 3 0 3 0 0 0 0 0 0 0 1 0 0 0 2 0 0 4 0 0 0 4 5 0 3 0 4 0 0 3 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 3 0 0 1 0 0 0 3 1 0 0 5 1 0
output:
1.25
result:
ok found '1.2500000', expected '1.2500000', error '0.0000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
10 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0
output:
0.25
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 622 0 0 0 0 0 0 0 0 622 0 0 0 0 0 0 585 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 982 0 0 0 0 0 0 0 0 0 0 0 0 0 585 0 0 0 982 0 0
output:
245.5
result:
ok found '245.5000000', expected '245.5000000', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Extra Test:
score: 0
Extra Test Passed