QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344161#5505. Great Chaseucup-team1198#WA 296ms3900kbC++203.0kb2024-03-03 17:20:382024-03-03 17:20:38

Judging History

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

  • [2024-03-03 17:20:38]
  • 评测
  • 测评结果:WA
  • 用时:296ms
  • 内存:3900kb
  • [2024-03-03 17:20:38]
  • 提交

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() && (stack.back().first >= p || 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[i].first, left[i].second + right[i].second));
        if (i + 1 < left.size() && (j + 1 == right.size() || events_left[i] < events_right[i])) {
            ++i;
        } else {
            ++j;
        }
    }
    ans = min(ans, Frac(left[i].first + right[i].first, left[i].second + right[i].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: 1ms
memory: 3812kb

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: 296ms
memory: 3900kb

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:

123931295255.2361194640
16414958969.7272811905
5228879381.5943491422
322225396.5713473390
50171218552.2794501930
183885744.7692307692
2234417354.8709242034
93195406120.0720418766
14036630941.8380109537
412975327.5555555556
976630191.1444696912
4703493416.5283192485
429299452.4737872686
5580908908.50...

result:

wrong answer 1st numbers differ - expected: '145405766328.3491211', found: '123931295255.2361145', error = '0.1476865'