QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356247 | #6517. Computational Geometry | Djangle162857# | WA | 0ms | 3636kb | C++20 | 1.6kb | 2024-03-17 17:03:12 | 2024-03-17 17:03:13 |
Judging History
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