QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#259569 | #7750. Revenge on My Boss | ucup-team484 | WA | 0ms | 3416kb | C++17 | 1.8kb | 2023-11-21 02:07:29 | 2023-11-21 02:07:30 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
void solve() {
int n; cin >> n;
vector<ll> a(n), b(n), c(n), d(n);
vector<array<ll, 3>> tmp(n);
ll sm = 0;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> c[i];
tmp[i] = {a[i], b[i], c[i]};
sm += b[i];
}
for (int i = 0; i < n; i++)
tie(a[i], b[i]) = make_pair(a[i] - b[i], (sm + a[i]) * c[i]);
vector<int> ans(n);
auto ok = [&](ll C) {
for (int i = 0; i < n; i++) {
ans[i] = i;
d[i] = C - b[i];
if (d[i] < 0)
d[i] = (d[i] - c[i] + 1) / c[i];
else
d[i] /= c[i];
// cout << a[i] << " " << d[i] << endl;
}
sort(all(ans), [&](int i, int j) {
int oi = a[i] > 0, oj = a[j] > 0;
if (oi != oj)
return oi < oj;
if (oi == 1)
return d[i] <= d[j];
return a[i] + d[i] == a[j] + d[j] ? d[i] > d[j] : a[i] + d[i] < a[j] + d[j];
});
ll pref = 0;
for (int i: ans) {
// cout << a[i] << " " << d[i] << endl;
if (d[i] < pref)
return 0;
pref += a[i];
}
return 1;
};
ll lo = 0, hi = 1e18;
while (lo >= hi) {
ll mi = (lo + hi) / 2;
if (ok(mi))
hi = mi - 1;
else
lo = mi + 1;
}
ok(lo);
// ll pref = 0, suf = 0, val = 0;
// for (int i = 0; i < n; i++)
// suf += tmp[i][1];
// for (int i = 0; i < n; i++) {
// pref += tmp[ans[i]][0];
// val = max(val, (pref + suf) * tmp[ans[i]][2]);
// suf -= tmp[ans[i]][1];
// }
// cout << val << endl;
for (int i = 0; i < n; i++)
cout << ans[i] + 1 << " \n"[i + 1 == n];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t; cin >> t; while (t--) solve();
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3416kb
input:
2 4 1 1 4 5 1 5 1 9 1 9 8 1 9 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 8 3 2 7
output:
3 1 4 2 3 8 2 4 5 7 9 6 1
result:
wrong answer Wrong Answer on Case#1