QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#841702 | #9770. Middle Point | arca | ML | 0ms | 3832kb | C++20 | 1.8kb | 2025-01-03 22:55:57 | 2025-01-03 22:55:57 |
Judging History
answer
#include <algorithm>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using namespace std;
using i64 = long long;
i64 A, B, x, y;
vector<pair<i64, i64>> s;
set<pair<i64, i64>> E;
int main() {
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;
}
}
using P = pair<i64, i64>;
auto dist = [&](P &a, i64 b, i64 c) {
return (a.first - b) * (a.first - b) +
(a.second - c) * (a.second - c);
};
int dep = 0;
auto dfs = [&](auto f, i64 a, i64 b) -> void {
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})) f(f, nl, nr);
else cout << dep << "\n";
if (dep) cout << nl << " " << nr << " " << l << " " << r << '\n';
};
dfs(dfs, x, y);
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
input:
2 2 1 1
output:
1 2 2 0 0
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3828kb
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: 3796kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
2024 0 1012 0
output:
1 2024 0 0 0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2024 2024 2023 2023
output:
-1
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
8 6 7 3
output:
3 0 6 8 6 4 6 8 6 6 6 8 0
result:
ok correct!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
2024 2026 2024 2026
output:
0
result:
ok correct!
Test #8:
score: -100
Memory Limit Exceeded
input:
1000000000 1000000000 70 0