QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#815869#9804. Guess the Polygonucup-team1769#WA 1ms3816kbC++203.8kb2024-12-15 18:12:442024-12-15 18:12:45

Judging History

This is the latest submission verdict.

  • [2024-12-15 18:12:45]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3816kb
  • [2024-12-15 18:12:44]
  • Submitted

answer

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

#define max_len 1200

struct frac_num
{
    int fz, fm;
    frac_num() = default;
    frac_num(int zz, int mm)
    {
        fz = zz, fm = mm;
        mk_gcd();
    }
    frac_num(int zz)
    {
        fz = zz, fm = 1;
    }
    void mk_gcd()
    {
        int g = gcd(fz, fm);
        fz = fz / g, fm = fm / g;
    }
    frac_num operator+(const frac_num&r) const
    {
        return frac_num(fz * r.fm + fm * r.fz, fm * r.fm);
    }
    frac_num operator-(const frac_num&r) const
    {
        return frac_num(fz * r.fm - fm * r.fz, fm * r.fm);
    }
    frac_num operator+(const int&r) const
    {
        return frac_num(fz + fm * r, fm);
    }
    frac_num operator-(const int&r) const
    {
        return frac_num(fz - fm * r, fm);
    }
    frac_num operator*(const frac_num&r) const
    {
        return frac_num(fz * r.fz, fm * r.fm);
    }
    frac_num operator*(const int r) const
    {
        return frac_num(fz * r, fm);
    }
    frac_num operator/(const int r) const
    {
        return frac_num(fz, fm * r);
    }
    bool operator==(const int r) const
    {
        return fm == 1 && fz == r;
    }
    bool operator<(const int r) const
    {
        return 1.0 * fz / fm < r;
    }
    bool operator<(const frac_num&r) const
    {
        return fz * r.fm < fm * r.fz;
    }
};


frac_num print_ques(frac_num fn)
{
    fn.mk_gcd();
    cout << "? " << fn.fz << " " << fn.fm << endl;
    int zz, mm;
    cin >> zz >> mm;
    return frac_num(zz, mm);
}
void print_ans(frac_num fn)
{
    fn.mk_gcd();
    cout << "! " << fn.fz << " " << fn.fm << endl;
}

int N;
map<int, set<int>> poi_map;
void input()
{
    poi_map.clear();
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        poi_map[x].insert(y);
    }
}


int vec_ji_cha(vector<int> vec)
{
    return vec.back() - vec.front();
}

void sol()
{
    input();
    // x, [y]
    vector<pair<frac_num, vector<int>>> poi_vec;
    for(auto [pir_x, pirs] : poi_map)
    {
        poi_vec.push_back({pir_x, vector<int>()});
        for(auto yy : pirs)
        {
            poi_vec.back().second.push_back(yy);
        }
    }
    int poi_su = poi_vec.size();
    frac_num ans_m2 = 0;
    frac_num last_bian_len = frac_num(0, 1);
    frac_num last_x = poi_vec[0].first;
    if(poi_vec[0].second.size() > 1)
    {
        last_bian_len = print_ques(last_x);
    }
    // int last_jicha = 0;
    for (int i = 1; i < poi_su - 1; i++)
    {
        auto [now_x, y_vec] = poi_vec[i];
        auto y_diff_th = print_ques(now_x);
        if(y_vec.size() == 1)
        {
            ans_m2 = ans_m2 + (y_diff_th + last_bian_len) * (now_x - last_x);
            last_x = now_x;
            last_bian_len = y_diff_th;
        }
        else
        {
            ans_m2 = ans_m2 + (y_diff_th + last_bian_len) * (now_x - last_x);

            auto mid_x = (now_x + poi_vec[i + 1].first) / 2;
            auto y_diff_mid = print_ques(mid_x);
            ans_m2 = ans_m2 + (y_diff_th + y_diff_mid) * (mid_x - now_x);

            last_x = mid_x;
            last_bian_len = y_diff_mid;
        }
    }
    {
        auto [now_x, y_vec] = poi_vec.back();
        {
            auto end_b = frac_num(0, 1);
            if(y_vec.size() == 1)
            {
                ans_m2 = ans_m2 + (last_bian_len) * (now_x - last_x);

            }
            else
            {
                auto y_diff_mid = print_ques(now_x);
                ans_m2 = ans_m2 + (last_bian_len + y_diff_mid) * (now_x - last_x);

            }
        }

    }
    ans_m2.fm *= 2;
    print_ans(ans_m2);
    
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        sol();
    }
    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

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

output:

? 1 1
? 2 1
! 3 1
? 999 1
! 1999 2

result:

ok correct! (2 test cases)

Test #2:

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

input:

9
4
1 1
1 3
3 0
0 0
3 1
1 2

output:

? 1 1
? 2 1
! 7 2

result:

wrong answer the answer is incorrect, expect: 5/2, find: 7/2 (test case 1)