QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387933 | #7753. Energy Distribution | defnotmee | WA | 0ms | 4024kb | C++20 | 4.5kb | 2024-04-13 04:52:06 | 2024-04-13 04:52:06 |
Judging History
answer
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define O_O
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double dbl;
typedef long double dbll;
const ll INFL = 4e18+25;
const int INF = 1e9+42;
const double EPS = 1e-7;
const int MOD = (1<<23)*17*7 + 1; // 998244353
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;
/**
* Author: Stanford
* Source: Stanford Notebook
* License: MIT
* Description: Solves a general linear maximization problem: maximize $c^T x$ subject to $Ax \le b$, $x \ge 0$.
* Returns -inf if there is no solution, inf if there are arbitrarily good solutions, or the maximum value of $c^T x$ otherwise.
* The input vector is set to an optimal $x$ (or in the unbounded case, an arbitrary solution fulfilling the constraints).
* Numerical stability is not guaranteed. For better performance, define variables such that $x = 0$ is viable.
* Usage:
* vvd A = {{1,-1}, {-1,1}, {-1,-2}};
* vd b = {1,1,-4}, c = {-1,-1}, x;
* T val = LPSolver(A, b, c).solve(x);
* Time: O(NM * \#pivots), where a pivot may be e.g. an edge relaxation. O(2^n) in the general case.
* Status: seems to work?
*/
#pragma once
#define rep(_i,_j,_k) for(int _i = _j; _i < _k; _i++)
typedef long double T; // long double, Rational, double + mod<P>...
typedef vector<T> vd;
typedef vector<vd> vvd;
const T eps = 1e-8, inf = 1/.0;
#define MP make_pair
#define ltj(X) if(s == -1 || MP(X[j],N[j]) < MP(X[s],N[s])) s=j
using vi = vector<int>;
#define sz(x) (int)x.size()
struct LPSolver {
int m, n;
vi N, B;
vvd D;
LPSolver(const vvd& A, const vd& b, const vd& c) :
m(sz(b)), n(sz(c)), N(n+1), B(m), D(m+2, vd(n+2)) {
// for(int i = 0; i < A.size(); i++){
// for(int j = 0; j < A[0].size(); j++){
// cerr << A[i][j] << ' ';
// }
// cerr << " <= " << b[i];
// cerr << '\n';
// }
rep(i,0,m) rep(j,0,n) D[i][j] = A[i][j];
rep(i,0,m) { B[i] = n+i; D[i][n] = -1; D[i][n+1] = b[i];}
rep(j,0,n) { N[j] = j; D[m][j] = -c[j]; }
N[n] = -1; D[m+1][n] = 1;
}
void pivot(int r, int s) {
T *a = D[r].data(), inv = 1 / a[s];
rep(i,0,m+2) if (i != r && abs(D[i][s]) > eps) {
T *b = D[i].data(), inv2 = b[s] * inv;
rep(j,0,n+2) b[j] -= a[j] * inv2;
b[s] = a[s] * inv2;
}
rep(j,0,n+2) if (j != s) D[r][j] *= inv;
rep(i,0,m+2) if (i != r) D[i][s] *= -inv;
D[r][s] = inv;
swap(B[r], N[s]);
}
bool simplex(int phase) {
int x = m + phase - 1;
for (;;) {
int s = -1;
rep(j,0,n+1) if (N[j] != -phase) ltj(D[x]);
if (D[x][s] >= -eps) return true;
int r = -1;
rep(i,0,m) {
if (D[i][s] <= eps) continue;
if (r == -1 || MP(D[i][n+1] / D[i][s], B[i])
< MP(D[r][n+1] / D[r][s], B[r])) r = i;
}
if (r == -1) return false;
pivot(r, s);
}
}
T solve(vd &x) {
int r = 0;
rep(i,1,m) if (D[i][n+1] < D[r][n+1]) r = i;
if (D[r][n+1] < -eps) {
pivot(r, n);
if (!simplex(2) || D[m+1][n+1] < -eps) return -inf;
rep(i,0,m) if (B[i] == -1) {
int s = 0;
rep(j,1,n+1) ltj(D[i]);
pivot(i, s);
}
}
bool ok = simplex(1); x = vd(n);
rep(i,0,m) if (B[i] < n) x[B[i]] = D[i][n+1];
return ok ? D[m][n+1] : inf;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vvd A(2*n,vd(n));
matrix<dbll> v(n,vector<dbll>(n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
cin >> v[i][j];
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
A[2*i][j] = v[i][j]-v[(i+1)%n][j];
A[2*i+1][j] = -(v[i][j]-v[(i+1)%n][j]);
}
}
A.push_back(vd(n,1));
A.push_back(vd(n,-1));
vd B(A.size());
B.back() = -1;
B[A.size()-2] = 1;
vd C(n);
for(int i = 0; i < n; i++){
if(v[i] != vd(n,0))
C = v[i];
}
vd resp(n);
resp[0] = 1;
cout << fixed << setprecision(7) << LPSolver(A,B,C).solve(resp)/2 << '\n';
// for(int i = 0; i < n; i++)
// cerr << resp[i] << ' ';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3936kb
input:
2 0 1 1 0
output:
0.2500000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
3 0 2 1 2 0 2 1 2 0
output:
0.5714286
result:
ok found '0.5714286', expected '0.5714290', error '0.0000004'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.5000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3920kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
0.4285714
result:
wrong answer 1st numbers differ - expected: '0.7500000', found: '0.4285714', error = '0.3214286'