QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#288159 | #7753. Energy Distribution | UNos_maricones# | WA | 2ms | 7284kb | C++14 | 2.1kb | 2023-12-22 07:58:44 | 2023-12-22 07:58:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair <int,int> pii;
const int N = 100'005;
struct frac {
ll a, b;
frac () {}
frac (ll a, ll b): a ( a ), b ( b ) {}
bool operator < ( frac s ) const {
return a * s.b < s.a * b;
}
frac operator + ( ll x ) {
return frac ( a + x*b, b );
}
};
int t, n;
ll a[N], b[N], c[N];
int ind[N], ind_res[N];
pair <ll, frac> X_Y[N];
ll s_b, res;
void reset () {
s_b = 0; res = LLONG_MAX;
}
void genArrXY (ll mi) {
for ( int i = 0; i < n; ++i ) {
X_Y[i] = mp(a[i]-b[i], frac(mi - a[i]*c[i] - s_b*c[i], c[i]));
}
}
bool cmp ( int indA, int indB ) {
auto A = X_Y[indA], B = X_Y[indB];
if ( A.ff < 0 and B.ff < 0 )
return B.ss < A.ss;
if ( A.ff < 0 or B.ff < 0 )
return A.ff < B.ff;
return A.ss+A.ff < B.ss+B.ff;
}
ll getMax () {
ll maxi = 0, pref = 0;
for ( int k = 0; k < n; ++k ) {
int i = ind[k];
maxi = max ( maxi, (a[i]+s_b+pref)*c[i] );
pref += a[i] - b[i];
}
return maxi;
}
bool check ( ll mi ) {
genArrXY ( mi );
iota ( ind, ind+n, 0 );
sort ( ind, ind+n, cmp );
ll currAns = getMax ();
if ( currAns < res ) {
res = currAns;
copy ( ind, ind+n, ind_res );
}
return currAns <= mi;
}
void getAns () {
ll lo = 0, hi = LLONG_MAX/3, mi;
while ( lo < hi ) {
mi = (lo+hi)/2;
if ( check ( mi ) ) {
hi = res;
} else {
lo = mi+1;
}
}
}
int main () {
#ifndef LOCAL
#endif
scanf ( "%d", &t );
while ( t-- ) {
reset ();
scanf ( "%d", &n );
for ( int i = 0; i < n; ++i ) {
scanf ( "%lld%lld%lld", a+i, b+i, c+i );
s_b += b[i];
}
getAns ();
for ( int i = 0; i < n; ++i )
printf ( "%d%c", ind_res[i]+1, " \n"[i==n-1] );
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7284kb
input:
2 0 1 1 0
output:
1
result:
wrong answer 1st numbers differ - expected: '0.2500000', found: '1.0000000', error = '0.7500000'