QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138591#5433. Absolute DifferenceKronosWA 3ms3856kbC++207.7kb2023-08-12 00:31:362023-08-12 00:31:39

Judging History

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

  • [2023-08-12 00:31:39]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3856kb
  • [2023-08-12 00:31:36]
  • 提交

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);
    vector <long double> val_sum_alice(new_n + 1), val_sum_bob(new_m + 1);

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

    for (int i = 0; i < new_m; ++i) {
        auto [x, y] = new_seg_bob[i];
        sq_bob[i] = 1.0 * y * y - 1.0 * x * x;
        dif_bob[i] = y - x;
        if (x == y) eq_sum_bob[i] = 1, val_sum_alice[i] = x;
        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];
        val_sum_alice[i] += val_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];
        val_sum_bob[i] += val_sum_bob[i - 1];
    }

    long double sum = 0;
    for (int i = 0; i < new_n; ++i) {
        long long a, b;
        a = new_seg_alice[i].first;
        b = new_seg_alice[i].second;
        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) * (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) * (b - a);

        Wa() dbg(sq_g) dbg(sq_l) dbg(dif_g) dbg(dif_l); 

        if (mp_alice[new_seg_alice[i]] and mp_bob[new_seg_alice[i]]) {
            sum += 1.0 * (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 val_sum_g = val_sum_bob[new_m] - (id ? val_sum_bob[id - 1] : 0);

        if (eq_sum_g) sum -= val_sum_g * (b - a) - (1.0 * b * b - 1.0 * a * a) / 2.0 * eq_sum_g;
        
        long double eq_sum_l = (id ? eq_sum_bob[id - 1] : 0);
        long double val_sum_l = (id ? val_sum_bob[id - 1] : 0);

        if (eq_sum_l) sum -= (1.0 * b * b - 1.0 * a * a) / 2.0 * eq_sum_l - val_sum_l * (b - a);

        Wa() dbg(b - a) dbg(b * b - a * a) dbg(eq_sum_g) dbg(eq_sum_l);

        if (a == b) {
            long double llen = new_m - id;
            sum += sq_g * llen - 1.0 * a * dif_g * 2.0;
            llen = id;
            sum += 1.0 * a * dif_l * 2.0 - sq_l * id;
        }
    }

    Wa() dbg(sum);

    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: 1ms
memory: 3736kb

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: 2ms
memory: 3728kb

input:

1 1
0 1
1 1

output:

0.5000000000

result:

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

Test #3:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.6666666297

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.0000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 3ms
memory: 3856kb

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.0000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

score: -100
Wrong Answer
time: 3ms
memory: 3736kb

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

-0.5000000003

result:

wrong answer 1st numbers differ - expected: '1000000000.5000000', found: '-0.5000000', error = '1.0000000'