QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110514#6542. Optimal Quadratic Functionhjroh0315Compile Error//C++202.8kb2023-06-02 18:10:492023-06-02 18:10:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-02 18:10:52]
  • 评测
查看
  • [2023-06-02 18:10:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using lf=__float128;

#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 __float128 T; // long double, Rational, double + mod<P>...
typedef vector<T> vd;
typedef vector<vd> vvd;

const T eps = lf(1)/1e6, 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

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)) {
			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()
{
    cin.tie(0)->sync_with_stdio(0);
	// simplex with 7 dimensions, each being r, a1, a2, b1, b2, c1, c2 (1 and 2 exist due to bypassing nonnegativity constraints)
    // max -r
    // s.t. -r - a1*x^2 + a2*x^2 - b1*x + b2*x - c1 + c2 <= -y
    //      -r + a1*x^2 - a2*x^2 + b1*x - b2*x + c1 - c2 <= y
    vector<lf>c{-1,0,0,0,0,0,0};
    int q;cin>>q;
    while(q--)
    {
        vector<vector<lf>>A;
        vector<lf>B;
        vector<lf>x;
        int n;cin>>n;
        while(n--)
        {
            long long x,y;
            cin>>x>>y;
            B.push_back(-y);
            A.push_back({-1,-x*x,x*x,-x,x,-1,1});
            B.push_back(y);
            A.push_back({-1,x*x,-x*x,x,-x,1,-1});
        }
        lf ans=LPSolver(A,B,c).solve(x);
        cout<<setprecision(7)<<fixed<<abs(double(ans*ans))<<"\n";
    }
}
源文件, 语言: C++20

详细 

answer.code: In member function ‘void LPSolver::pivot(int, int)’:
answer.code:35:47: error: call of overloaded ‘abs(__gnu_cxx::__alloc_traits<std::allocator<__float128>, __float128>::value_type&)’ is ambiguous
   35 |                 rep(i,0,m+2) if (i != r && abs(D[i][s]) > eps) {
      |                                            ~~~^~~~~~~~~
In file included from /usr/include/c++/11/bits/std_abs.h:38,
                 from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code: In function ‘int main()’:
answer.code:101:31: warning: narrowing conversion of ‘((- x) * x)’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
  101 |             A.push_back({-1,-x*x,x*x,-x,x,-1,1});
      |                             ~~^~
answer.code:101:31: warning: narrowing conversion of ‘((- x) * x)’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
answer.code:101:35: warning: narrowing conversion of ‘(x * x)’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
  101 |             A.push_back({-1,-x*x,x*x,-x,x,-1,1});
      |                                  ~^~
answer.code:101:35: warning: narrowing conversion of ‘(x * x)’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
answer.code:101:38: warning: narrowing conversion of ‘- x’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
  101 |             A.push_back({-1,-x*x,x*x,-x,x,-1,1});
      |                                      ^~
answer.code:101:38: warning: narrowing conversion of ‘- x’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
answer.code:101:41: warning: narrowing conversion of ‘x’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
  101 |             A.push_back({-1,-x*x,x*x,-x,x,-1,1});
      |                                         ^
answer.code:101:41: warning: narrowing conversion of ‘x’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
answer.code:103:30: warning: narrowing conversion of ‘(x * x)’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
  103 |             A.push_back({-1,x*x,-x*x,x,-x,1,-1});
      |                             ~^~
answer.code:103:30: warning: narrowing conversion of ‘(x * x)’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
answer.code:103:35: warning: narrowing conversion of ‘((- x) * x)’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
  103 |             A.push_back({-1,x*x,-x*x,x,-x,1,-1});
      |                                 ~~^~
answer.code:103:35: warning: narrowing conversion of ‘((- x) * x)’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
answer.code:103:38: warning: narrowing conversion of ‘x’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
  103 |             A.push_back({-1,x*x,-x*x,x,-x,1,-1});
      |                                      ^
answer.code:103:38: warning: narrowing conversion of ‘x’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
answer.code:103:40: warning: narrowing conversion of ‘- x’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
  103 |             A.push_back({-1,x*x,-x*x,x,-x,1,-1});
      |                                        ^~
answer.code:103:40: warning: narrowing conversion of ‘- x’ from ‘long long int’ to ‘__float128’ [-Wnarrowing]
English 繁體中文 简体中文

服务器时间: 2024-12-03 01:54:10 | 开源项目