QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#378462 | #6693. Fast and Fat | Credit | WA | 55ms | 3652kb | C++17 | 1.2kb | 2024-04-06 13:06:21 | 2024-04-06 13:06:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
void solve()
{
int n;
cin >> n;
vector<pair<ll, ll>>a(n + 1);
ll mx = 0;
for (int i = 1;i <= n;i++) {
cin >> a[i].first >> a[i].second;
mx = max(mx, a[i].first);
}
int l = 1, r = mx;
while (l < r) {
int mid = (r + l) >> 1;
auto check = [&] (int x) -> bool {
vector<ll> v1, v2;
for (int i = 1;i <= n;i++) {
if (a[i].first < x)v2.push_back(a[i].second);
else v1.push_back(a[i].first + a[i].second - x);
}
int p1 = 0;
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
for (auto i : v2) {
while (p1 < v1.size() && v1[p1] < i)p1++;
if (p1 == v1.size())return 1;
p1++;
}
return 0;
};
if (check(mid))r = mid - 1;
else l = mid + 1;
}
cout << r << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
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: 55ms
memory: 3652kb
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:
352409015 785434740 470297536 280572174 704877363 960871619 691253610 560579096 136979645 399988835 610497257 576427566 636500914 315900406 370430730 526259136 781258283 631916852 300930080 419999540 431930706 479323439 530080165 391912907 708925499 467782813 457987604 389750719 447390354 696516804 ...
result:
wrong answer 1st numbers differ - expected: '352409014', found: '352409015'