QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356247#6517. Computational GeometryDjangle162857#WA 0ms3636kbC++201.6kb2024-03-17 17:03:122024-03-17 17:03:13

Judging History

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

  • [2024-03-17 17:03:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3636kb
  • [2024-03-17 17:03:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
typedef long long ll;
const int mod = 1000000007;
const int inf = 2147483647;
const int N = 200020;
void solve()
{
	int A, B, x, y;
	cin >> x >> y >> A >> B;
	A = min(A, x), B = min(B, y);
	if (x == y) {
		cout << "YES\n";
		cout << "2 2\n";
		return;
	}
	if (x == 1 || y == 1) {
		cout << "NO" << el;
		return;
	}
	map<vector<int>, int> mp;
	for (int i = 2; i * i <= x && i <= A; i++) {
		// x->i
		int now = x;
		vector<int> s;
		while (now >= 1) {
			s.push_back(now % i);
			now = now / i;
		}
		mp[s] = i;
	}
	for (int i = 2; i * i <= y && i <= B; i++) {
		// x->i
		int now = y;
		vector<int> s;
		while (now >= 1) {
			s.push_back(now % i);
			now = now / i;
		}
		if (mp.find(s) != mp.end()) {
			cout << "YES" << el;
			cout << mp[s] << " " << i << el;
			return;
		}
	}
	int flag = 0;
	if (x < y) {
		swap(x, y);
		swap(A, B);
		flag = 1;
	}
	int a, b;
	int minb = sqrt(y) + 1;
	int mina = sqrt(x) + 1;
	for (int p = 1; p * p < x && p * p < y; p++) {
		if ((x - y) % p != 0)
			continue;
		int res = (x - y) / p;
		a = min(A, x / p);
		b = a - res;
		if (a < mina || b < minb)
			continue;
		int q = x - a * p;
		if (q < a && q < b) {
			cout << "YES" << el;
			if (flag)
				swap(a, b);
			cout << a << " " << b << el;
			return;
		}
	}
	cout << "NO" << el;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3636kb

input:

2
4
1 0
2 0
1 1
0 0
6
10 4
9 7
5 7
4 5
6 4
9 3

output:

NO
NO

result:

wrong output format Expected integer, but "NO" found