QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#259569#7750. Revenge on My Bossucup-team484WA 0ms3416kbC++171.8kb2023-11-21 02:07:292023-11-21 02:07:30

Judging History

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

  • [2023-11-21 02:07:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3416kb
  • [2023-11-21 02:07:29]
  • 提交

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