QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#825107 | #9770. Middle Point | ucup-team6225# | WA | 0ms | 3840kb | C++14 | 3.9kb | 2024-12-21 17:23:03 | 2024-12-21 17:23:13 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
using pii = pair<int, int>;
const int N = 1000010, M = 1010, SZ = (1 << 18) + 5;
static char buf[SZ], *bgn = buf, *til = buf;
char getc() {
if(bgn == til) bgn = buf, til = buf + fread(buf, 1, SZ, stdin);
return bgn == til ? EOF : *bgn++;
}
template<typename T>
void read(T &x) {
char ch = getc(); T fh = 0; x = 0;
while(ch < '0' || ch > '9') fh |= (ch == '-'), ch = getc();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getc();
x = fh ? -x : x;
}
template<typename Type, typename... argc>
void read(Type &x, argc &...args) {read(x), read(args...);}
template<typename T>
void print(T x) {
if(x < 0) putchar('-'), x = -x;
if(x / 10) print(x / 10);
putchar(x % 10 + '0');
}
int a, b, x, y;
vector<int> px, py, edge[M];
map<pii, int> id;
map<int, pii> pre;
vector<pii> ap, aq;
vector<pii> merge(int a, int x) {
// cerr << a << " " << x << "\n";
if(x == a || x == 0) return {};
int l = 0, r = a; vector<pii> tmp;
py.pb(l), py.pb(r);
while(l < r) {
int mid = (l + r) >> 1;
// cerr << l << " " << r << " " << mid << "\n";
if((l + r) & 1) return {{-1, -1}};
tmp.pb({l, r}), py.pb(mid), pre[mid] = {l, r};
if(x == mid) return tmp;
else if(x < mid) r = mid;
else l = mid;
}
return tmp;
}
int add(int x, int y) {
if(id.find({x, y}) != id.end()) return 0;
vector<pii> p = merge(a, x), q = merge(b, y);
if((!p.empty() && p[0].fi < 0) || (!q.empty() && q[0].fi < 0)) return -1;
int sum = max(p.size(), q.size());
// printf("%d\n", sum);
reverse(p.begin(), p.end()), reverse(q.begin(), q.end());
for(int i = 1; i <= sum; ++i) {
if(p.size() > q.size()) {
if(id.find({(p.back().fi + p.back().se) / 2, 0}) == id.end()) {
add(p.back().fi, 0), add(p.back().se, 0);
id[{(p.back().fi + p.back().se) / 2, 0}] = 1;
ap.pb({p.back().fi, 0}), aq.pb({p.back().se, 0});
// fprintf(stderr, "%d 0 %d 0\n", p.back().fi, p.back().se);
}
p.pop_back();
}
else if(p.size() < q.size()) {
if(id.find({0, (q.back().fi + q.back().se) / 2}) == id.end()) {
add(0, q.back().fi), add(0, q.back().se);
id[{0, (q.back().fi + q.back().se) / 2}] = 1;
ap.pb({0, q.back().fi}), aq.pb({0, q.back().se});
// fprintf(stderr, "0 %d 0 %d\n", q.back().fi, q.back().se);
}
q.pop_back();
}
else {
if(id.find({(p.back().fi + p.back().se) / 2, (q.back().fi + q.back().se) / 2}) == id.end()) {
add(p.back().fi, q.back().fi), add(p.back().se, q.back().se);
id[{(p.back().fi + p.back().se) / 2, (q.back().fi + q.back().se) / 2}] = 1;
ap.pb({p.back().fi, q.back().fi}), aq.pb({p.back().se, q.back().se});
// fprintf(stderr, "%d %d %d %d\n", p.back().fi, q.back().fi, p.back().se, q.back().se);
}
p.pop_back(), q.pop_back();
}
}
id[{x, y}] = 1;
return 1;
}
int main() {
#ifdef Kelly
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("err.txt", "w", stderr);
#endif
cin >> a >> b >> x >> y;
vector<pii> p = merge(a, x);
swap(px, py);
vector<pii> q = merge(b, y);
// cerr << p.size() << " " << q.size() << "\n";
if((!p.empty() && p[0].fi < 0) || (!q.empty() && q[0].fi < 0)) {cout << "-1"; return 0;}
id[{0, 0}] = id[{0, b}] = id[{a, 0}] = id[{a, b}] = 1;
add(x, y);
printf("%d\n", (int)ap.size());
for(int i = 0; i < ap.size(); ++i) printf("%d %d %d %d\n", ap[i].fi, ap[i].se, aq[i].fi, aq[i].se);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
2 2 1 1
output:
1 0 0 2 2
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
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: 3840kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
2024 0 1012 0
output:
1 0 0 2024 0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3776kb
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: 3784kb
input:
2024 2026 2024 2026
output:
0
result:
ok correct!
Test #8:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
1000000000 1000000000 70 0
output:
-1
result:
ok correct!
Test #9:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
3 6 2 4
output:
-1
result:
ok correct!
Test #10:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
7 7 7 2
output:
-1
result:
ok correct!
Test #11:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
6 2 5 2
output:
-1
result:
ok correct!
Test #12:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 7 5 5
output:
-1
result:
ok correct!
Test #13:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
4 7 2 3
output:
-1
result:
ok correct!
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 3784kb
input:
8 2 2 2
output:
2 0 0 8 0 0 0 4 0
result:
wrong answer target point have not been added into S