QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#841706 | #9770. Middle Point | arca | WA | 0ms | 3872kb | C++20 | 1.7kb | 2025-01-03 22:59:41 | 2025-01-03 22:59:41 |
Judging History
answer
#include <algorithm>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using namespace std;
using i64 = long long;
using P = pair<i64, i64>;
i64 A, B, x, y;
vector<pair<i64, i64>> s;
set<pair<i64, i64>> E;
i64 dep = 0;
auto dist = [](P &a, i64 b, i64 c) {
return (a.first - b) * (a.first - b) + (a.second - c) * (a.second - c);
};
void dfs(i64 a, i64 b) {
sort(s.begin(), s.end(), [&](P &a1, P &b1) {
return dist(a1, a, b) < dist(b1, a, b);
});
auto [l, r] = s[0];
int nl = a * 2 - l, nr = b * 2 - r;
dep++;
if (!E.contains({nl, nr})) dfs(nl, nr);
else cout << dep << "\n";
if (dep) cout << nl << " " << nr << " " << l << " " << r << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> A >> B >> x >> y;
s.push_back({0, 0});
s.push_back({A, 0});
s.push_back({0, B});
s.push_back({A, B});
E = set(s.begin(), s.end());
// Check
if (E.contains({x, y})) {
cout << 0 << "\n";
return 0;
}
if (A == 0 && B == 0 && (x != 0 || y != 0)) {
cout << -1 << '\n';
return 0;
}
{
i64 d1, c1, d2, c2;
for (d1 = 0, c1 = -1; A && (1ll << d1) <= A; d1++) {
if ((1ll << d1) * x % A == 0) {
c1 = (1ll << d1) * x / A;
break;
}
}
for (d2 = 0, c2 = -1; B && (1ll << d2) <= B; d2++) {
if ((1ll << d2) * y % B == 0) {
c2 = (1ll << d2) * y / B;
break;
}
}
if (c1 == -1 || c2 == -1) {
cout << -1 << '\n';
return 0;
}
}
dfs(x, y);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
2 2 1 1
output:
1 2 2 0 0
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
8 8 5 0
output:
3 8 0 0 0 4 0 0 0 2 0 8 0
result:
ok correct!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3576kb
input:
2024 0 1012 0
output:
-1
result:
wrong answer Jury has a better answer