QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288159#7753. Energy DistributionUNos_maricones#WA 2ms7284kbC++142.1kb2023-12-22 07:58:442023-12-22 07:58:45

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2023-12-22 07:58:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7284kb
  • [2023-12-22 07:58:44]
  • 提交

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'