QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188570#7239. Triangleucup-team004WA 1ms3968kbC++201.2kb2023-09-26 01:28:242023-09-26 01:28:25

Judging History

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

  • [2023-09-26 01:28:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3968kb
  • [2023-09-26 01:28:24]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E5;

void solve() {
    int n, c;
    std::cin >> n >> c;
    
    std::bitset<N + 1> a{}, b{};
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a[x] = b[N - x] = 1;
    }
    
    double ans = -1;
    
    for (int s = 2 * c, z = s; s >= 3; s--) {
        while (z > 0 && (z >= s || !a[z])) {
            z--;
        }
        if (2 * z >= s) {
            a[z] = b[N - z] = 0;
            auto v = a & (s < N ? b >> (N - s) : b << (s - N));
            int x = v._Find_next(s - z - 1);
            int y = s - x;
            if (x < y && y < z) {
                double p = 0.5 * (x + y + z);
                double area = std::sqrt(p * (p - x) * (p - y) * (p - z));
                if (ans < 0 || ans > area) {
                    ans = area;
                }
            }
            a[z] = b[N - z] = 1;
        }
    }
    
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(10);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3968kb

input:

4
3 3
1 2 3
4 4
1 2 3 4
3 11
5 7 11
6 11
5 7 8 9 10 11

output:

-1.0000000000
2.9047375097
12.9687123493
12.9687123493

result:

ok 4 numbers

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3904kb

input:

20
5 20
15 20 11 17 18
5 20
12 18 13 20 15
5 20
12 10 14 18 16
5 20
18 16 15 11 14
5 20
18 12 11 20 14
5 20
20 15 10 16 12
5 20
12 10 15 13 17
5 20
18 15 13 20 12
5 20
16 18 20 10 14
5 20
11 15 16 13 18
5 20
11 13 16 14 17
5 20
20 14 11 13 16
5 20
16 11 15 13 18
5 20
11 15 13 20 14
5 20
16 10 13 20 ...

output:

81.3879597975
74.9061913329
56.5685424949
76.9801110677
56.7180526817
45.5960524607
58.9358761706
74.9061913329
64.9923072371
70.9929573972
71.4995629357
66.0000000000
70.9929573972
66.0000000000
31.9755766172
89.9777750336
56.1465715783
71.4995629357
42.4264068712
82.6498638837

result:

wrong answer 1st numbers differ - expected: '81.2599994', found: '81.3879598', error = '0.0015747'