QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344162#5505. Great Chaseucup-team1198#WA 292ms3856kbC++203.0kb2024-03-03 17:25:372024-03-03 17:25:37

Judging History

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

  • [2024-03-03 17:25:37]
  • 评测
  • 测评结果:WA
  • 用时:292ms
  • 内存:3856kb
  • [2024-03-03 17:25:37]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

struct Frac{
    long long num;
    long long den;
    Frac(long long num, long long den): num(num), den(den) {}
};

bool operator >=(const Frac& first, const Frac& second) {
    return first.num * second.den >= second.num * first.den;
}

bool operator <(const Frac& first, const Frac& second) {
    return first.num * second.den < second.num * first.den;
}


void solve() {
    int n, v;
    cin >> n >> v;
    vector<pair<long long, long long>> right;
    vector<pair<long long, long long>> left;
    for (int i = 0; i < n; ++i) {
        long long p, vi;
        cin >> p >> vi;
        if (p > 0)
            right.emplace_back(p, vi);
        else
            left.emplace_back(-p, vi);
    }
    auto transform = [](vector<pair<long long, long long>>& cops) {
        sort(cops.begin(), cops.end(), [](const pair<long long, long long>& a, const pair<long long, long long>& b) {
            if (a.second == b.second) {
                return a.first < b.first;
            }
            return a.second < b.second;
        });
        vector<Frac> events;
        vector<pair<long long, long long>> stack;
        for (auto [p, v] : cops) {
            // same speed but closer
            if (!stack.empty() && stack.back().second == v)
                continue;
            while (!stack.empty() && (events.back() >= Frac(p - stack.back().first, v - stack.back().second))) {
                stack.pop_back();
                events.pop_back();
            }
            if (stack.empty()) {
                stack.emplace_back(p, v);
                events.emplace_back(Frac(0, 1));
            } else {
                events.emplace_back(Frac(p - stack.back().first, v - stack.back().second));
                stack.emplace_back(p, v);
            }
        }
        swap(stack, cops);
        return events;
    };
    auto events_right = transform(right);
    auto events_left = transform(left);
    int i = 0;
    int j = 0;
    Frac ans(3e12, 1);
    while (i + 1 < left.size() || j + 1 < right.size()) {
        ans = min(ans, Frac(left[i].first + right[j].first, left[i].second + right[j].second));
        if (i + 1 < left.size() && (j + 1 == right.size() || events_left[i] < events_right[j])) {
            ++i;
        } else {
            ++j;
        }
    }
    ans = min(ans, Frac(left[i].first + right[j].first, left[i].second + right[j].second));
    long double kek = ans.num * v;
    long double lol = ans.den;
    cout << fixed << setprecision(10) << kek / lol << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3804kb

input:

3
4 9
10 2
-7 2
-6 1
7 1
2 8
-1 7
1 6
2 3
-1000000000000 1
1000000000000 1

output:

38.2500000000
1.2307692308
3000000000000.0000000000

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 292ms
memory: 3856kb

input:

10000
200 997007
405524182320 754760
686939601648 419804
687047488212 715566
1446157132 4594
-670522037 4673
763634629282 253755
424307411732 275041
1582708381 8473
-667425982 4622
-522841486 1427
702430907988 460271
1405423646 1060
1497754648 6227
883363410675 723547
56899800372 46435
-810216390 64...

output:

151868962571.5000860691
17942128383.3106280044
5202715639.8351838998
321977234.1563258690
51469146100.9242737480
183885744.7692307692
1741895220.3695540257
95048574022.0840029195
14160973732.2979194699
412975327.5555555556
965508404.5121014926
4703493416.2883765241
352961619.3810438190
5580848621.33...

result:

wrong answer 1st numbers differ - expected: '145405766328.3491211', found: '151868962571.5000916', error = '0.0444494'