QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#605336#6401. Classic: N Real DNA Potslqh2024#WA 0ms3928kbC++171.9kb2024-10-02 16:45:022024-10-02 16:45:03

Judging History

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

  • [2024-10-02 16:45:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3928kb
  • [2024-10-02 16:45:02]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using i64 = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K> using rb_tree = tree<K, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const i64 mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);

void QAQ() {
    int n, v;
    cin >> n >> v;

    vector<array<int, 2>> a(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
    }

    double l = -2e9, r = 2e9;

    auto chk = [&](double k) {
        int res = 1;
        map<double, int> q;
        for (int i = 1; i <= n; i++) {
            double t = a[i][1] - k * a[i][0];
            auto it = q.upper_bound(t);
            if (it != q.begin()) {
                it = prev(it);
                int now = it -> second + 1;
                res = max(res, now);
                it = q.lower_bound(t);
                while (it != q.end() && it -> second <= now) {
                    it = q.erase(it);
                }
                q.insert({a[i][1] - k * a[i][0], now});
            } else {
                q.insert({a[i][1] - k * a[i][0], 1});
            }
        }
        return res >= v;
    };

    for (int i = 0; i < 50; i++) {
        auto mid = (l + r) / 2;

        if (chk(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }

    cout << l << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3
1 2
2 4
3 3
4 1

output:

-1.000000082740

result:

ok found '-1.0000001', expected '-1.0000000', error '0.0000001'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3928kb

input:

2 2
1 1
5 3

output:

0.499998265013

result:

wrong answer 1st numbers differ - expected: '0.5000000', found: '0.4999983', error = '0.0000017'