QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#617389#5435. Clamped SequenceCipherxzc#WA 1ms5916kbC++233.1kb2024-10-06 15:18:312024-10-06 15:18:32

Judging History

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

  • [2024-10-06 15:18:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5916kb
  • [2024-10-06 15:18:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using db = double;

struct node{
    int l, r;
    db x, k;
};

const int N = 1e5;
int n, m, l1[N], r1[N], l2[N], r2[N];
db s[N << 1], ks[N << 1]; // s: sigma(k2 * x2), ks: sigma(k2)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    vector<int> used;
    db len1 = 0, len2 = 0;
    for (int i = 1; i <= n; i++){
        cin >> l1[i] >> r1[i];
        used.push_back(l1[i]);
        used.push_back(r1[i]);
        len1 += r1[i] - l1[i];
    }
    for (int i = 1; i <= m; i++){
        cin >> l2[i] >> r2[i];
        used.push_back(l2[i]);
        used.push_back(r2[i]);
        len2 += r2[i] - l2[i];
    }
    sort(used.begin(), used.end());
    used.erase(unique(used.begin(), used.end()), used.end());
    bool flag1 = (l1[0] == r1[1]);
    bool flag2 = (l2[1] == r2[1]);

    vector<node> vec1, vec2;
    int p = 0;
    if (flag1){
        for (int i = 1; i <= n; i++){
            assert(l1[i] == r1[i]);
            vec1.emplace_back(l1[i], r1[i], l1[i], db(1.0) / n);
        }
    }else{
        for (int i = 1; i <= n; i++){
            while (p < used.size() && used[p] < l1[i]){
                p++;
            }
            p++;
            while (p < used.size() && used[p] <= r1[i]){
                db gg = db(used[p - 1] + used[p]) / 2;
                db jj = (used[p] - used[p - 1]) / len1;
                vec1.emplace_back(used[p - 1], used[p], gg, jj);
                p++;
            }
        }
    }
    if (flag2){
        for (int i = 1; i <= m; i++){
            assert(l2[i] == r2[i]);
            vec2.emplace_back(l2[i], r2[i], l2[i], db(1.0) / m);
        }
    }else{
        p = 0;
        for (int i = 1; i <= m; i++){
            while (p < used.size() && used[p] < l2[i]){
                p++;
            }
            p++;
            while (p < used.size() && used[p] <= r2[i]){
                db gg = db(used[p - 1] + used[p]) / 2;
                db jj = (used[p] - used[p - 1]) / len2;
                vec2.emplace_back(used[p - 1], used[p], gg, jj);
                p++;
            }
        }
    }

    s[0] = vec2[0].x;
    ks[0] = vec2[0].k;
    for (int i = 1; i < vec2.size(); i++){
        s[i] = s[i - 1] + vec2[i].x * vec2[i].k;
        ks[i] += vec2[i - 1].k;
    }
    db sum = s[vec2.size()] = s[vec2.size() - 1];
    db ksum = ks[vec2.size()] = ks[vec2.size() - 1];

    p = 0;
    db ans = 0;
    for (auto [l, r, x, k] : vec1){
        while (p < vec2.size() && vec2[p].l < l){
            p++;
        }
        if (p < vec2.size() && vec2[p].l == l){
            db res = ks[p - 1] * x - s[p - 1];
            res += (sum - s[p]) - (ksum - ks[p]) * x;
            res = res * k + k * vec2[p].k / 3 * (r - l) * (r - l);
            ans += res;
        }else{
            db res = ks[p - 1] * x - s[p - 1];
            res += (sum - s[p - 1]) - (ksum - ks[p - 1]) * x;
            ans += res * k;
        }
    }

    cout << fixed << setprecision(20) << ans << endl;

    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5916kb

input:

8 3
3 1 4 1 5 9 2 6

output:

3.11111111111111116045

result:

wrong output format Expected integer, but "3.11111111111111116045" found