QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797777#9804. Guess the Polygonucup-team4975#WA 1ms3872kbC++234.2kb2024-12-03 18:08:302024-12-03 18:08:31

Judging History

This is the latest submission verdict.

  • [2024-12-03 18:08:31]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3872kb
  • [2024-12-03 18:08:30]
  • Submitted

answer

#define LOCAL
#include <bits/stdc++.h>
#define fir first
#define sec second
#define el '\n'

#ifdef LOCAL
#define FINISH cerr << "FINISH" << endl;
#else
#define FINISH ;
#endif

#ifdef LOCAL
#define debug(x) cerr << setw(4) << #x << " == " << x << endl
#else
#define debug(x)
#endif

#ifdef LOCAL
#define debugv(x)                   \
    cerr << setw(4) << #x << ":: "; \
    for (auto i : x)                \
        cerr << i << " ";           \
    cerr << endl
#else
#define debugv(x)
#endif

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
ostream& operator<<(ostream& out, PII& x)
{
    out << x.fir << " " << x.sec << endl;
    return out;
}

const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 200020;
struct point {
	int x, y;
};
void solve()
{
    int n;
    cin >> n;
    vector<point> p(n + 1);
    for (int i = 1; i <= n; i++) {
    	cin >> p[i].x >> p[i].y;
    }
    sort(next(p.begin()), p.end(), [&](point x, point y) {
    	return x.x < y.x;
    });	
    ll lasx = 0, lasy = 1;
    ll areax = 0, areay = 1;
    int lft = 0;
    int flag = 0;
    for (int i = 2; i < n; i++) {
    	if (p[i].x == p[i - 1].x) {
    		flag = 1;
    		continue;
    	}
    	
    	if (flag == 1) {
    		flag = 0;
    		int x1, y1, x2, y2;
    		if ((p[i].x + 2 * p[i - 1].x) % 3 == 0) {
	    		cout << "? " << (p[i].x + 2 * p[i - 1].x) / 3 << " " << 1 << endl;
	    	}
	    	else {
	    		cout << "? " << (p[i].x + 2 * p[i - 1].x) << " " << 3 << endl;
	    	}
	    	cin >> x1 >> y1;
	    	if ((2 * p[i].x + p[i - 1].x) % 3 == 0) {
	    		cout << "? " << (2 * p[i].x + p[i - 1].x) / 3 << " " << 1 << endl;
	    	}
	    	else {
	    		cout << "? " << (2 * p[i].x + p[i - 1].x) << " " << 3 << endl;
	    	}
	    	cin >> x2 >> y2;

	    	ll nxtx = 2 * x2 * y1 - x1 * y2;
	    	ll nxty = y1 * y2;
	    	ll g = __gcd (nxtx, nxty);
	    	nxtx /= g, nxty /= g;
	    	lasx = nxtx, lasy = nxty;

	    	ll x = x2 * y1 + x1 * y2;
	    	ll y = y1 * y2;
	    	g = __gcd(x, y);
	    	x = x / g, y = y / g;

	    	ll len = p[i].x - p[i - 1].x;
	    	x = x * len;

	    	ll nxtareax = x * areay + y * areax;
	    	ll nxtareay = y * areay;
	    	g = __gcd (nxtareax, nxtareay);
	    	areax = nxtareax / g;
	    	areay = nxtareay / g;
    	}

    	int res = p[i].x;
    	if ((p[i].x + p[i - 1].x) % 2 == 0) {
    		cout << "? " << (p[i].x + p[i - 1].x) / 2 << " " << 1 << endl;
    	}
    	else {
    		cout << "? " << (p[i].x + p[i - 1].x) << " " << 2 << endl;
    	}
    	ll x, y;
    	cin >> x >> y;

    	ll nxtx = 2 * x * lasy - y * lasx;
    	ll nxty = y * lasy;
    	ll g = __gcd (nxtx, nxty);
    	nxtx /= g, nxty /= g;
    	lasx = nxtx, lasy = nxty;

    	ll len = p[i].x - p[i - 1].x;
    	x = x * len;

    	ll nxtareax = x * areay + y * areax;
    	ll nxtareay = y * areay;
    	g = __gcd (nxtareax, nxtareay);
    	areax = nxtareax / g;
    	areay = nxtareay / g;
    }
    if (p[n].x == p[n - 1].x) {
    	cout << "! " << areax << " " << areay << endl;
    	return;
    }
    if (flag == 1) {
    	if ((p[n].x + p[n - 1].x) % 2 == 0) {
    		cout << "? " << (p[n].x + p[n - 1].x) / 2 << " " << 1 << endl;
    	}
    	else {
    		cout << "? " << (p[n].x + p[n - 1].x) << " " << 2 << endl;
    	}
    	ll x, y;
    	cin >> x >> y;

    	ll len = p[n].x - p[n - 1].x;
    	x = x * len;

    	ll nxtareax = x * areay + y * areax;
    	ll nxtareay = y * areay;
    	ll g = __gcd (nxtareax, nxtareay);
    	areax = nxtareax / g;
    	areay = nxtareay / g;

    	cout << "! " << areax << " " << areay << endl;
    	return;
    }
    ll len = p[n].x - p[n - 1].x;
	ll nxtx = len * lasx;
    ll nxty = 2 * lasy;
    ll g = __gcd (nxtx, nxty);
    nxtx /= g, nxty /= g;
    ll nxtareax = nxty * areax + nxtx * areay;
    ll nxtareay = nxty * areay;
    g = __gcd (nxtareax, nxtareay);
    areax = nxtareax / g;
    areay = nxtareay / g;

    cout << "! " << areax << " " << areay << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

详细

Test #1:

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

input:

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

output:

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

result:

ok correct! (2 test cases)

Test #2:

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

input:

9
4
1 1
1 3
3 0
0 0
3 2
1 2
4
0 0
1 3
1 1
3 0
1 2
3 2
4
0 0
3 0
1 2
1 1
1 2
1 2
4
0 0
3 0
1 2
1 1
1 1
1 2
4
0 0
3 0
1 1
1 2
1 2
1 1
3
1000 0
0 0
0 1000
500 1
4
0 0
1000 0
1000 1000
0 1000
1000 1
1000 1

output:

? 1 2
? 2 1
! 5 2
? 1 2
? 2 1
! 7 2
? 1 2
? 2 1
! 3 2
? 1 2
? 2 1
! 2 1
? 1 2
? 2 1
! 5 2
? 500 1
! 500000 1
? 1000 3
? 2000 3
? 500 1

result:

wrong answer number of queries exceeds the limit: 2 (test case 7)