QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523731#5433. Absolute DifferenceohwphilWA 18ms12008kbPython35.8kb2024-08-18 17:07:452024-08-18 17:07:45

Judging History

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

  • [2024-08-18 17:07:45]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:12008kb
  • [2024-08-18 17:07:45]
  • 提交

answer

import sys
from collections import defaultdict
from decimal import *
getcontext().prec = 30

def main():
    n, m = 0, 0
    alice_interval_sums, bob_interval_sums = 0, 0

    alice_intervals = []
    bob_intervals = []

    endpoints = []
    alice_imos = []
    bob_imos = []
    value_compressor = {}

    l, r = 0, 0

    ans = Decimal(0)

    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    m = int(data[1])
    index = 2

    for _ in range(n):
        l = int(data[index])
        r = int(data[index + 1])
        alice_interval_sums += r - l
        alice_intervals.append((l, r))
        index += 2

    for _ in range(m):
        l = int(data[index])
        r = int(data[index + 1])
        bob_interval_sums += r - l
        bob_intervals.append((l, r))
        index += 2
    
    if bob_interval_sums == 0:
        n, m = m, n
        alice_interval_sums, bob_interval_sums = bob_interval_sums, alice_interval_sums
        alice_intervals, bob_intervals = bob_intervals, alice_intervals

    if alice_interval_sums != 0:
        new_alice_intervals = []
        for l, r in alice_intervals:
            if l != r:
                new_alice_intervals.append((l, r))
                endpoints.append(l)
                endpoints.append(r)
            else:
                n -= 1
        alice_intervals = new_alice_intervals
    else:
        for l, r in alice_intervals:
            endpoints.append(l)

    if bob_interval_sums != 0:
        new_bob_intervals = []
        for l, r in bob_intervals:
            if l != r:
                new_bob_intervals.append((l, r))
                endpoints.append(l)
                endpoints.append(r)
            else:
                m -= 1
        bob_intervals = new_bob_intervals
    else:
        for l, r in bob_intervals:
            endpoints.append(l)

    endpoints = sorted(set(endpoints))
    k = len(endpoints)
    alice_imos = [0] * k
    bob_imos = [0] * k

    for i in range(k):
        value_compressor[endpoints[i]] = i

    if bob_interval_sums == 0:
        n, m = m, n
        alice_interval_sums, bob_interval_sums = bob_interval_sums, alice_interval_sums
        alice_intervals, bob_intervals = bob_intervals, alice_intervals

    alice_intervals.sort()
    bob_intervals.sort()

    for l, r in alice_intervals:
        alice_imos[value_compressor[l]] += 1
        if l != r:
            alice_imos[value_compressor[r]] -= 1

    for l, r in bob_intervals:
        bob_imos[value_compressor[l]] += 1
        if l != r:
            bob_imos[value_compressor[r]] -= 1

    if alice_interval_sums != 0:
        for i in range(k - 1):
            alice_imos[i + 1] += alice_imos[i]

    if bob_interval_sums != 0:
        for i in range(k - 1):
            bob_imos[i + 1] += bob_imos[i]

    if alice_interval_sums != 0 and bob_interval_sums != 0:
        curr_cnt = Decimal(0)
        curr_len_sum = Decimal(0)
        curr_square_sum = Decimal(0)

        for i in range(k):
            if alice_imos[i]:
                ans -= curr_cnt * (endpoints[i + 1] - endpoints[i]) * curr_square_sum
                ans += curr_cnt * (endpoints[i + 1] ** 2 - endpoints[i] ** 2) * curr_len_sum
            if bob_imos[i]:
                curr_cnt += 1
                curr_len_sum += endpoints[i + 1] - endpoints[i]
                curr_square_sum += endpoints[i + 1] ** 2 - endpoints[i] ** 2

        curr_cnt = Decimal(0)
        curr_len_sum = Decimal(0)
        curr_square_sum = Decimal(0)

        for i in range(k - 1, -1, -1):
            if alice_imos[i]:
                ans += curr_cnt * (endpoints[i + 1] - endpoints[i]) * curr_square_sum
                ans -= curr_cnt * (endpoints[i + 1] ** 2 - endpoints[i] ** 2) * curr_len_sum
            if bob_imos[i]:
                curr_cnt += 1
                curr_len_sum += endpoints[i + 1] - endpoints[i]
                curr_square_sum += endpoints[i + 1] ** 2 - endpoints[i] ** 2

        ans /= 2

        for i in range(k):
            if alice_imos[i] and bob_imos[i]:
                ans += Decimal((endpoints[i + 1] - endpoints[i])) ** 3 / 3

        ans /= alice_interval_sums
        ans /= bob_interval_sums
    elif bob_interval_sums != 0:
        curr_len_sum = Decimal(0)
        curr_square_sum = Decimal(0)

        for i in range(k):
            if alice_imos[i]:
                ans += endpoints[i] * curr_len_sum
                ans -= curr_square_sum / 2
            if bob_imos[i]:
                curr_len_sum += endpoints[i + 1] - endpoints[i]
                curr_square_sum += endpoints[i + 1] ** 2 - endpoints[i] ** 2

        curr_len_sum = Decimal(0)
        curr_square_sum = Decimal(0)

        for i in range(k - 1, -1, -1):
            if bob_imos[i]:
                curr_len_sum += endpoints[i + 1] - endpoints[i]
                curr_square_sum += endpoints[i + 1] ** 2 - endpoints[i] ** 2
            if alice_imos[i]:
                ans -= endpoints[i] * curr_len_sum
                ans += Decimal(curr_square_sum) / 2

        ans /= bob_interval_sums
        ans /= n
    else:
        curr_cnt = Decimal(0)
        curr_sum = Decimal(0)

        for i in range(k):
            if alice_imos[i]:
                ans += curr_cnt * endpoints[i] - curr_sum
            if bob_imos[i]:
                curr_cnt += 1
                curr_sum += endpoints[i]

        curr_cnt = Decimal(0)
        curr_sum = Decimal(0)

        for i in range(k - 1, -1, -1):
            if alice_imos[i]:
                ans += curr_sum - curr_cnt * endpoints[i]
            if bob_imos[i]:
                curr_cnt += 1
                curr_sum += endpoints[i]

        ans /= n
        ans /= m

    print(ans)

if __name__ == "__main__":
    main()


详细

Test #1:

score: 100
Accepted
time: 14ms
memory: 11088kb

input:

1 1
0 1
0 1

output:

0.333333333333333333333333333333

result:

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

Test #2:

score: 0
Accepted
time: 13ms
memory: 11064kb

input:

1 1
0 1
1 1

output:

0.5

result:

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

Test #3:

score: 0
Accepted
time: 13ms
memory: 10976kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666666666666666667

result:

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

Test #4:

score: 0
Accepted
time: 16ms
memory: 11028kb

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000

result:

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

Test #5:

score: 0
Accepted
time: 16ms
memory: 11092kb

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000

result:

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

Test #6:

score: 0
Accepted
time: 12ms
memory: 11160kb

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.5

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

score: 0
Accepted
time: 6ms
memory: 11092kb

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.0000000005

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

score: 0
Accepted
time: 9ms
memory: 11064kb

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

score: -100
Wrong Answer
time: 18ms
memory: 12008kb

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

8830218.65154057995252717679663

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '8830218.6515406', error = '1313.5845844'