QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138584#5433. Absolute DifferenceKronos#WA 3ms3808kbC++207.0kb2023-08-11 23:58:502023-08-11 23:58:52

Judging History

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

  • [2023-08-11 23:58:52]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3808kb
  • [2023-08-11 23:58:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;

struct debug {
#define contPrint                     \
    {                                 \
        *this << "[";                 \
        int f = 0;                    \
        for (auto it : x) {           \
            *this << (f ? ", " : ""); \
            *this << it;              \
            f = 1;                    \
        }                             \
        *this << "]";                 \
        return *this;                 \
    }

    ~debug() { cerr << endl; }
    template <class c>
    debug& operator<<(c x) {
        cerr << x;
        return *this;
    }
    template <class c, class d>
    debug& operator<<(pair<c, d> x) {
        *this << "(" << x.first << ", " << x.second << ")";
        return *this;
    }
    template <class c>
    debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};

#define dbg(x) "[" << #x << ": " << x << "]  "
#define Wa()                                  \
    cerr << "[LINE: " << __LINE__ << "] -> "; \
    debug() <<
#define FASTIO                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    vector<array<int, 3>> events;

    vector<pair<int, int>> seg_alice(n);
    for (auto& [x, y] : seg_alice) {
        scanf("%d %d", &x, &y);
        events.push_back({x, 0, 0});
        events.push_back({y, 1, 0});
    }

    vector<pair<int, int>> seg_bob(m);
    for (auto& [x, y] : seg_bob) {
        scanf("%d %d", &x, &y);
        events.push_back({x, 0, 1});
        events.push_back({y, 1, 1});
    }

    sort(events.begin(), events.end());

    vector<pair<int, int>> new_seg_alice;

    {
        bool alice_running = false;

        int a_st = -1;

        for (auto [x, y, z] : events) {
            if (z == 0) {
                if (y == 0) {
                    a_st = x;
                    alice_running = true;
                } else if (y == 1) {
                    new_seg_alice.push_back({a_st, x});
                    alice_running = false;
                }
            } else {
                if (alice_running) {
                    new_seg_alice.push_back({a_st, x});
                    a_st = x;
                }
            }
        }
    }

    sort(new_seg_alice.begin(), new_seg_alice.end());
    new_seg_alice.resize(unique(new_seg_alice.begin(), new_seg_alice.end()) - new_seg_alice.begin());

    for (auto& [x, y, z] : events) {
        z ^= 1;
    }
    sort(events.begin(), events.end());

    vector<pair<int, int>> new_seg_bob;
    {
        bool alice_running = false;

        int a_st = -1;

        for (auto [x, y, z] : events) {
            Wa() dbg(x) dbg(y) dbg(z);

            if (z == 0) {
                if (y == 0) {
                    a_st = x;
                    alice_running = true;
                } else if (y == 1) {
                    new_seg_bob.push_back({a_st, x});
                    alice_running = false;
                }
            } else {
                if (alice_running) {
                    new_seg_bob.push_back({a_st, x});
                    a_st = x;
                }
            }

            Wa() dbg(a_st);
        }
    }

    sort(new_seg_bob.begin(), new_seg_bob.end());
    new_seg_bob.resize(unique(new_seg_bob.begin(), new_seg_bob.end()) - new_seg_bob.begin());


    vector <pair <int, int>> notun_seg_alice, notun_seg_bob;
    int new_n = new_seg_alice.size();
    int new_m = new_seg_bob.size();

    for (int i = 0; i < new_n; ++i) {
        if (!notun_seg_alice.empty() and notun_seg_alice.back().second == new_seg_alice[i].first) {
            notun_seg_alice.back().second = new_seg_alice[i].second;
        } else {
            notun_seg_alice.push_back(new_seg_alice[i]);
        }
    }

    for (int i = 0; i < new_m; ++i) {
        if (!notun_seg_bob.empty() and notun_seg_bob.back().second == new_seg_bob[i].first) {
            notun_seg_bob.back().second = new_seg_bob[i].second;
        } else {
            notun_seg_bob.push_back(new_seg_bob[i]);
        }
    }

    new_seg_alice = notun_seg_alice;
    new_seg_bob = notun_seg_bob;
    new_n = new_seg_alice.size();
    new_m = new_seg_bob.size();

    Wa() dbg(new_seg_alice) dbg(new_seg_bob);

    map <pair <int, int>, int> mp_alice, mp_bob;

    for (int i = 0; i < new_n; i++) {
        mp_alice[new_seg_alice[i]]++;
    }

    for (int i = 0; i < new_m; i++) {
        mp_bob[new_seg_bob[i]]++;
    }

    long double tot_n = 0, tot_m = 0;

    vector <long double> sq_alice(new_n + 1), sq_bob(new_m + 1);
    vector <long double> dif_alice(new_n + 1), dif_bob(new_m + 1);
    vector <long double> eq_sum_alice(new_n + 1), eq_sum_bob(new_m + 1);

    for (int i = 0; i < new_n; ++i) {
        auto [x, y] = new_seg_alice[i];
        sq_alice[i] = y * y - x * x;
        dif_alice[i] = y - x;
        if (x == y) eq_sum_alice[i] = 1;
        tot_n += y - x;
    }

    for (int i = 0; i < new_m; ++i) {
        auto [x, y] = new_seg_bob[i];
        sq_bob[i] = y * y - x * x;
        dif_bob[i] = y - x;
        if (x == y) eq_sum_bob[i] = 1;
        tot_m += y - x;
    }

    for (int i = 1; i < new_n + 1; ++i) {
        sq_alice[i] += sq_alice[i - 1];
        dif_alice[i] += dif_alice[i - 1];
        eq_sum_alice[i] += eq_sum_alice[i - 1];
    }

    for (int i = 1; i < new_m + 1; ++i) {
        sq_bob[i] += sq_bob[i - 1];
        dif_bob[i] += dif_bob[i - 1];
        eq_sum_bob[i] += eq_sum_bob[i - 1];
    }

    long double sum = 0;
    for (int i = 0; i < new_n; ++i) {
        auto [a, b] = new_seg_alice[i];
        auto id = lower_bound(new_seg_bob.begin(), new_seg_bob.end(), new_seg_alice[i]) - new_seg_bob.begin();
        
        long double sq_g = (sq_bob[new_m] - (id ? sq_bob[id - 1] : 0)) / 2.0;
        long double dif_g = (dif_bob[new_m] - (id ? dif_bob[id - 1] : 0)) / 2.0;

        sum += sq_g * (b - a) - dif_g * (b + a);
        
        long double sq_l = -(id ? sq_bob[id - 1] : 0) / 2.0;
        long double dif_l = -(id ? dif_bob[id - 1] : 0) / 2.0;

        sum += sq_l * (b - a) - dif_l * (b + a);

        if (mp_alice[new_seg_alice[i]] and mp_bob[new_seg_alice[i]]) {
            sum += (b - a) * (b - a) * (b - a) / 3.0;
        }

        long double eq_sum_g = eq_sum_bob[new_m] - (id ? eq_sum_bob[id - 1] : 0);
        long double llen = new_m - id;

        if (eq_sum_g) sum += eq_sum_g * (b - a) - (b * b - a * a) / 2.0 * llen;
        
        long double eq_sum_l = (id ? eq_sum_bob[id - 1] : 0);
        llen = id;
        Wa() dbg(b - a) dbg(b * b - a * a) dbg(eq_sum_g) dbg(eq_sum_l);

        if (eq_sum_l) sum += (b * b - a * a) / 2.0 * llen - eq_sum_l * (b - a);
    }

    if (tot_n) sum /= tot_n;
    else sum /= new_n;
    if (tot_m) sum /= tot_m;
    else sum /= new_m;

    printf("%.10Lf\n", sum);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3724kb

input:

1 1
0 1
0 1

output:

0.3333333333

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

1 1
0 1
1 1

output:

0.5000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3808kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

0.0000000001

result:

wrong answer 1st numbers differ - expected: '666666666.6666666', found: '0.0000000', error = '1.0000000'