QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797044#9804. Guess the PolygonChinese_zjc_WA 1ms3816kbC++142.3kb2024-12-02 14:54:412024-12-02 14:54:46

Judging History

This is the latest submission verdict.

  • [2024-12-02 14:54:46]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3816kb
  • [2024-12-02 14:54:41]
  • Submitted

answer

#include <bits/stdc++.h>
int T, n, cnt[1005];
long double L[1005], M[1005], R[1005];
long double query(int p, int eps = 0)
{
    std::cout << "? " << p * 4 + eps << " 4" << std::endl;
    long long a, b;
    std::cin >> a >> b;
    return 1.0l * a / b;
}
long double k(long double x1, long double y1, long double x2, long double y2, long double x)
{
    return (x - x1) / (x2 - x1) * y2 + (x - x2) / (x1 - x2) * y1;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> T;
    while (T--)
    {
        std::cin >> n;
        std::fill(cnt, cnt + 1001, 0);
        std::vector<int> app;
        for (int i = 1, x, y; i <= n; ++i)
            std::cin >> x >> y, ++cnt[x], app.push_back(x);
        std::sort(app.begin(), app.end());
        app.erase(std::unique(app.begin(), app.end()), app.end());
        if (cnt[app[0]] == 1)
            M[app[0]] = 0;
        else
            R[app[0]] = query(app[0], 1);
        for (std::size_t i = 1; i + 1 < app.size(); ++i)
            if (cnt[app[i]] == 1)
                M[app[i]] = query(app[i]);
            else
                L[app[i]] = query(app[i], -1),
                R[app[i]] = query(app[i], +1);
        if (cnt[app.back()] == 1)
            M[app.back()] = 0;
        else
            L[app.back()] = query(app.back(), -1);
        long double sum = 0;
        for (std::size_t i = 1; i < app.size(); ++i)
            if (cnt[app[i - 1]] == 1 && cnt[app[i]] == 1)
                sum += (M[app[i]] - M[app[i - 1]]) * (app[i] - app[i - 1]);
            else if (cnt[app[i - 1]] == 1)
            {
                long double dx = (L[app[i]] - M[app[i - 1]]) / (app[i] - app[i - 1] - 0.25);
                sum += (L[app[i]] + M[app[i - 1]] + dx / 4) * (app[i] - app[i - 1]);
            }
            else if (cnt[app[i]] == 1)
            {
                long double dx = (M[app[i]] - R[app[i - 1]]) / (app[i] - app[i - 1] - 0.25);
                sum += (M[app[i]] + R[app[i - 1]] - dx / 4) * (app[i] - app[i - 1]);
            }
            else
                sum += (L[app[i]] + R[app[i - 1]]) * (app[i] - app[i - 1]);
        long long ans = static_cast<long long>(std::round(sum));
        std::cout << "! " << (ans % 2 ? ans : ans / 2) << ' ' << (ans % 2 ? 2 : 1) << std::endl;
    }
    return 0;
}

详细

Test #1:

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

input:

2
4
3 0
1 3
1 1
0 0
3 2
7 4
3
0 0
999 1000
1000 999
1999 1000

output:

? 3 4
? 5 4
! 3 1
? 3996 4
! 1995 2

result:

wrong answer the answer is incorrect, expect: 1999/2, find: 1995/2 (test case 2)