QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#794949#9804. Guess the Polygonucup-team296#WA 1ms3616kbC++202.8kb2024-11-30 17:03:232024-11-30 17:03:25

Judging History

This is the latest submission verdict.

  • [2024-11-30 17:03:25]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3616kb
  • [2024-11-30 17:03:23]
  • Submitted

answer

#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

struct rat {
    long p = 0, q = 1;

    rat(long _p, long _q) {
        long d = gcd(_p, _q);
        p = _p / d;
        q = _q / d;
    }

    rat(long x) {
        p = x;
    }

    rat() {

    }

    rat operator + (rat x) const {
        return {p * x.q + x.p * q, q * x.q};
    }

    rat operator - (rat x) const {
        return {p * x.q - x.p * q, q * x.q};
    }

    rat operator * (rat x) const {
        return {p * x.p, q * x.q};
    }

    rat operator / (rat x) const {
        return {p * x.q, q * x.p};
    }
};

struct test {

    rat ask(rat x) {
        cout << "? " << x.p << " " << x.q << endl;
        int p, q;
        cin >> p >> q;
        return {p, q};
    }

    rat calc(rat y1, rat y2, rat x1, rat x2) {
        rat m = {1, 2};
        rat r = y1 + (m - x1) * (y2 - y1) / (x2 - x1);
        return r;
    }

    void solve() {
        int n;
        cin >> n;
        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i];
        }
        sort(x.begin(), x.end());
        vector<pair<int, int>> xx;
        for (int i = 0; i < n; i++) {
            if (xx.empty() || x[i] > xx.back().first) {
                xx.push_back({x[i], 1});
            } else {
                xx.back().second++;
            }
        }
        int m = xx.size();
        vector<rat> val(m, 0);
        vector<rat> val2(m, 0);
        for (int i = 0; i < m; i++) {
            if (xx[i].second == 1) {
                if (i > 0 && i < m - 1)
                    val[i] = ask(xx[i].first);
            } else {
                if (i > 0) {
                    val[i] = ask(rat(xx[i].first) - rat(1, 3));
                }
                if (i < m - 1) {
                    val2[i] = ask(rat(xx[i].first) + rat(1, 3));
                }
            }
        }
        rat res = 0;
        for (int i = 0; i < m - 1; i++) {
            rat x1, y1, x2, y2;
            if (xx[i].second == 1) {
                x1 = 0;
                y1 = val[i];
            } else {
                x1 = {1, 3};
                y1 = val2[i];
            }
            if (xx[i + 1].second == 1) {
                x2 = 1;
                y2 = val[i + 1];
            } else {
                x2 = {2, 3};
                y2 = val[i + 1];
            }
            res = res + calc(y1, y2, x1, x2) * (xx[i + 1].first - xx[i].first);
        }
//        res = res * rat(1, 2);
        cout << "! " << res.p << " " << res.q << endl;
    }
};

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
4
3 0
1 3
1 1
0 0
4 3
5 3

output:

? 2 3
? 4 3
! 7 2

result:

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