QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378462#6693. Fast and FatCreditWA 55ms3652kbC++171.2kb2024-04-06 13:06:212024-04-06 13:06:23

Judging History

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

  • [2024-04-06 13:06:23]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:3652kb
  • [2024-04-06 13:06:21]
  • 提交

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'