QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#825595 | #9770. Middle Point | ucup-team4435# | WA | 0ms | 3828kb | C++23 | 5.7kb | 2024-12-21 20:42:19 | 2024-12-21 20:42:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
auto work = [&](int A, int X) -> vector<pair<int, int>> {
if (A == X || X == 0) {
return {};
}
int p = 1;
while (A % 2 == 0) {
p *= 2;
A /= 2;
}
int f = A;
if (X % f != 0) {
return {{-1, -1}};
}
X /= f;
A = p;
vector<pair<int, int>> o;
int l = 0, r = A;
while (l != X && r != X) {
int mid = l + r >> 1;
o.push_back({l, r});
if (mid == X) {
break;
} else if (mid > X) {
r = mid;
} else {
l = mid;
}
}
for (auto &[x, y]: o) {
x *= f, y *= f;
}
return o;
};
int A, B, X, Y;
cin >> A >> B >> X >> Y;
auto a = work(A, X), b = work(B, Y);
if (!a.empty() && a[0].first == -1 || !b.empty() && b[0].first == -1) {
cout << "-1\n";
return 0;
}
if (a.empty() || b.empty()) {
int i = 0;
cout << max(a.size(), b.size()) << '\n';
while (i < a.size() || i < b.size()) {
int x1 = X, y1 = Y, x2 = X, y2 = Y;
if (i < a.size()) {
x1 = a[i].first, x2 = a[i].second;
}
if (i < b.size()) {
y1 = b[i].first, y2 = b[i].second;
}
i += 1;
cout << x1 << " " << y1 << " " << x2 << " " << y2 << '\n';
}
return 0;
}
vector<array<int, 4>> answer;
for(int rot = 0; rot < 2; ++rot) {
{
vector<array<int, 4>> pref;
for (int i = 0; i < a.size(); ++i) {
pref.push_back({a[i].first, 0, a[i].second, 0});
pref.push_back({a[i].first, B, a[i].second, B});
}
int x = (a.back().first + a.back().second) / 2;
for (int i = 0; i < b.size(); ++i) {
pref.push_back({x, b[i].first, x, b[i].second});
}
if (answer.empty() || answer.size() > pref.size()) {
answer = pref;
if (rot) {
for(auto &t : answer) {
swap(t[0], t[1]);
swap(t[2], t[3]);
}
}
}
}
for (int it = 0; it < 2; ++it) {
vector<array<int, 4>> ans;
ans.push_back({a.back().first, b.back().first, a.back().second, b.back().second});
int pos = 1;
while (pos < a.size() && pos < b.size()) {
int pa = (int) a.size() - pos - 1;
int pb = (int) b.size() - pos - 1;
if (a[pa].first == a[pa + 1].first) {
if (b[pb].first != b[pb + 1].first) break;
} else {
assert(a[pa].second == a[pa + 1].second);
if (b[pb].second != b[pb + 1].second) break;
}
ans.push_back({a[pa].first, b[pb].first, a[pa].second, b[pb].second});
pos++;
}
{
vector<array<int, 4>> pref;
bool ok1 = (b[0].first == ans.back()[1]);
bool ok2 = (b[0].second == ans.back()[3]);
for (int i = 0; i < a.size(); ++i) {
if ((a[i].first == ans.back()[0]) && (a[i].second == ans.back()[2] || ok2)) break;
pref.push_back({a[i].first, 0, a[i].second, 0});
}
for (int i = 0; i < a.size(); ++i) {
if ((a[i].first == ans.back()[0] || ok1) && (a[i].second == ans.back()[2])) break;
pref.push_back({a[i].first, B, a[i].second, B});
}
for (int i = 0; i < b.size(); ++i) {
if (b[i].first == ans.back()[1]) break;
pref.push_back({ans.back()[0], b[i].first, ans.back()[0], b[i].second});
}
for (int i = 0; i < b.size(); ++i) {
if (b[i].second == ans.back()[3]) break;
pref.push_back({ans.back()[2], b[i].first, ans.back()[2], b[i].second});
}
if (answer.empty() || answer.size() > pref.size() + ans.size()) {
answer = pref;
for (int t = (int) ans.size() - 1; t >= 0; --t) {
answer.push_back(ans[t]);
}
if (rot) {
for(auto &t : answer) {
swap(t[0], t[1]);
swap(t[2], t[3]);
}
}
}
}
for (auto &[l, r]: a) swap(l, r);
}
swap(a, b);
swap(A, B);
}
set<array<int, 2>> who;
who.insert({0, 0});
who.insert({A, 0});
who.insert({A, B});
who.insert({0, B});
for(auto &t : answer) {
array<int, 2> F = {t[0], t[1]};
array<int, 2> S = {t[2], t[3]};
assert((F[0] + S[0]) % 2 == 0);
assert((F[1] + S[1]) % 2 == 0);
assert(who.count(F) && who.count(S));
auto MID = F;
MID[0] = (F[0] + S[0]) / 2;
MID[1] = (F[1] + S[1]) / 2;
assert(!who.count(MID));
who.insert(MID);
}
assert(who.count({X, Y}));
cout << answer.size() << '\n';
for(auto &t : answer) {
for(auto &x : t) cout << x << ' ';
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
2 2 1 1
output:
1 0 0 2 2
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
8 8 5 0
output:
3 0 0 8 0 4 0 8 0 4 0 6 0
result:
ok correct!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
2024 0 1012 0
output:
1 0 0 2024 0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
2024 2024 2023 2023
output:
-1
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
8 6 7 3
output:
3 0 0 8 0 4 0 8 0 6 0 8 6
result:
ok correct!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
2024 2026 2024 2026
output:
0
result:
ok correct!
Test #8:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1000000000 1000000000 70 0
output:
-1
result:
ok correct!
Test #9:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 6 2 4
output:
-1
result:
ok correct!
Test #10:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
7 7 7 2
output:
-1
result:
ok correct!
Test #11:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
6 2 5 2
output:
-1
result:
ok correct!
Test #12:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
5 7 5 5
output:
-1
result:
ok correct!
Test #13:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 7 2 3
output:
-1
result:
ok correct!
Test #14:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
8 2 2 2
output:
2 0 2 8 2 0 2 4 2
result:
ok correct!
Test #15:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
3 3 0 2
output:
-1
result:
ok correct!
Test #16:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
7 7 1 4
output:
-1
result:
ok correct!
Test #17:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
6 3 6 1
output:
-1
result:
ok correct!
Test #18:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
4 2 2 1
output:
1 0 0 4 2
result:
ok correct!
Test #19:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
7 2 3 2
output:
-1
result:
ok correct!
Test #20:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 7 0 3
output:
-1
result:
ok correct!
Test #21:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 7 1 0
output:
0
result:
ok correct!
Test #22:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
5 1 0 0
output:
0
result:
ok correct!
Test #23:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
8 7 4 3
output:
-1
result:
ok correct!
Test #24:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
180057652 674822131 110693180 428023738
output:
-1
result:
ok correct!
Test #25:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
62347541 812142018 42922107 486416913
output:
-1
result:
ok correct!
Test #26:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
239604722 244429197 78993837 108804105
output:
-1
result:
ok correct!
Test #27:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
416861903 381749084 375027630 373683256
output:
-1
result:
ok correct!
Test #28:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
594119084 519068971 429116021 298715088
output:
-1
result:
ok correct!
Test #29:
score: -100
Wrong Answer
time: 0ms
memory: 3776kb
input:
536870912 536870912 233225286 372408647
output:
85 0 0 536870912 0 0 536870912 536870912 536870912 0 0 268435456 0 0 536870912 268435456 536870912 134217728 0 268435456 0 134217728 536870912 268435456 536870912 201326592 0 268435456 0 201326592 536870912 268435456 536870912 201326592 0 234881024 0 201326592 536870912 234881024 536870912 ...
result:
wrong answer Jury has a better answer