QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135454#6693. Fast and FatyjWA 110ms3480kbC++141.2kb2023-08-05 15:31:552023-08-05 15:31:57

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 15:31:57]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:3480kb
  • [2023-08-05 15:31:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;

struct dui {
	ll v;
	ll w;
} a[100005], b[100005]; //a按重量,b按能力
bool cmp1(dui a, dui b) {
	return a.w > b.w;
}

bool cmp2(dui a, dui b) {
	return (a.v + a.w) > (b.v + b.w);
}

bool check(ll v) {
	vector<ll>power;
	vector<ll>leizhui;

	for (int i = 0; i < n; i++)

		if (a[i].v < v)
			leizhui.push_back(a[i].w);

	for (int i = 0; i < n; i++)

		if (b[i].v > v)
			power.push_back(b[i].v + b[i].w - v);

	if (power.size() < leizhui.size())
		return false;

	for (int i = 0; i < leizhui.size(); i++)

		if (leizhui[i] > power[i])
			return false;
	return true;
}

void solve() {
	cin >> n;
	ll maxv = 0;
	ll minv = 10000000099;

	for (int i = 0; i < n; i++) {

		ll x, y;
		maxv = max(maxv, x);
		minv = min(minv, x);
		cin >> x >> y;
		a[i] = {x, y};
		b[i] = {x, y};
	}

	sort(a, a + n, cmp1);
	sort(b, b + n, cmp2);
	ll midv = (maxv + minv) >> 1;

	while (minv < maxv) {
		midv = (1 + maxv + minv) >> 1;

		if (check(midv))
			minv = midv;
		else
			maxv = midv - 1;
	}

	cout << maxv << endl;
}

int main() {
	int t;
	cin >> t;

	while (t--)
		solve();
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3480kb

input:

2
5
10 5
1 102
10 100
7 4
9 50
2
1 100
10 1

output:

8
1

result:

ok 2 number(s): "8 1"

Test #2:

score: -100
Wrong Answer
time: 110ms
memory: 3456kb

input:

10000
4
280251502 664541723
375808746 641141991
95134537 898607509
455259328 944978891
2
798417052 547329847
785434740 991778535
6
623628702 857611223
275667427 453747403
292209526 283132767
330752033 988721243
470297536 608192332
477186035 325224271
3
280572174 994054447
306566740 923535026
3781360...

output:

352409014
785434740
470297535
280572174
704877362
960871618
691253608
560579094
56873747
399988835
610497257
576427564
636500913
315900405
370430730
526259135
781258283
631916851
300930080
419999539
431930706
479323438
530080164
391912906
708925498
467782812
457987604
389750718
447390353
696516804
4...

result:

wrong answer 3rd numbers differ - expected: '470297536', found: '470297535'