QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#841700 | #9770. Middle Point | arca | ML | 1ms | 3796kb | C++20 | 1.8kb | 2025-01-03 22:51:15 | 2025-01-03 22:51:23 |
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, P &b) {
return (a.first - b.first) * (a.first - b.first) +
(a.second - b.second) * (a.second - b.second);
};
int dep = 0;
auto dfs = [&](auto f, P x) -> void {
sort(s.begin(), s.end(), [&](P &a, P &b) {
return dist(a, x) < dist(b, x);
});
auto C = s[0];
P D = {x.first * 2 - C.first, x.second * 2 - C.second};
dep++;
if (!E.contains(D)) f(f, D);
else cout << dep << "\n";
if (dep)
cout << D.first << " " << D.second << " " << C.first << " "
<< C.second << '\n';
};
dfs(dfs, {x, y});
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3636kb
input:
2 2 1 1
output:
1 2 2 0 0
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
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: 3596kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
2024 0 1012 0
output:
1 2024 0 0 0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2024 2024 2023 2023
output:
-1
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3540kb
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: 3796kb
input:
2024 2026 2024 2026
output:
0
result:
ok correct!
Test #8:
score: -100
Memory Limit Exceeded
input:
1000000000 1000000000 70 0