QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#825276 | #9770. Middle Point | ucup-team6225# | WA | 1ms | 4112kb | C++14 | 4.4kb | 2024-12-21 17:57:22 | 2024-12-21 17:57:24 |
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 == 0) return {{0, 0}};
if(x == a) return {{a, a}};
int l = 0, r = a; vector<pii> tmp;
while(l < r) {
int mid = (l + r) >> 1;
// cerr << l << " " << r << " " << mid << "\n";
if((l + r) & 1) return {{-1, -1}};
tmp.pb({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()) {
// int op1 = add(p.back().fi, 0), op2 = add(p.back().se, 0);
// if(op1 < 0 || op2 < 0) return -1;
// 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()) {
// int op1 = add(0, q.back().fi), op2 = add(0, q.back().se);
// if(op1 < 0 || op2 < 0) return -1;
// 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()) {
// int op1 = add(p.back().fi, q.back().fi), op2 = add(p.back().se, q.back().se);
// id[{(p.back().fi + p.back().se) / 2, (q.back().fi + q.back().se) / 2}] = 1;
// if(op1 < 0 || op2 < 0) return -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();
// }
// }
add(p.back().fi, q.back().fi), add(p.back().se, q.back().se);
ap.pb({p.back().fi, q.back().fi}), aq.pb({p.back().se, q.back().se});
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;
if(add(x, y) < 0) {cout << -1; return 0;}
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: 3968kb
input:
2 2 1 1
output:
1 0 0 2 2
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3776kb
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: 3732kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
2024 0 1012 0
output:
1 0 0 2024 0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
2024 2024 2023 2023
output:
-1
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3780kb
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: 3776kb
input:
2024 2026 2024 2026
output:
0
result:
ok correct!
Test #8:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1000000000 1000000000 70 0
output:
-1
result:
ok correct!
Test #9:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 6 2 4
output:
-1
result:
ok correct!
Test #10:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
7 7 7 2
output:
-1
result:
ok correct!
Test #11:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
6 2 5 2
output:
-1
result:
ok correct!
Test #12:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
5 7 5 5
output:
-1
result:
ok correct!
Test #13:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
4 7 2 3
output:
-1
result:
ok correct!
Test #14:
score: 0
Accepted
time: 0ms
memory: 3728kb
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: 3596kb
input:
3 3 0 2
output:
-1
result:
ok correct!
Test #16:
score: 0
Accepted
time: 0ms
memory: 3584kb
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: 3968kb
input:
4 2 2 1
output:
1 0 0 4 2
result:
ok correct!
Test #19:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
7 2 3 2
output:
-1
result:
ok correct!
Test #20:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
2 7 0 3
output:
-1
result:
ok correct!
Test #21:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 7 1 0
output:
0
result:
ok correct!
Test #22:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
5 1 0 0
output:
0
result:
ok correct!
Test #23:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
8 7 4 3
output:
-1
result:
ok correct!
Test #24:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
180057652 674822131 110693180 428023738
output:
-1
result:
ok correct!
Test #25:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
62347541 812142018 42922107 486416913
output:
-1
result:
ok correct!
Test #26:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
239604722 244429197 78993837 108804105
output:
-1
result:
ok correct!
Test #27:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
416861903 381749084 375027630 373683256
output:
-1
result:
ok correct!
Test #28:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
594119084 519068971 429116021 298715088
output:
-1
result:
ok correct!
Test #29:
score: -100
Wrong Answer
time: 0ms
memory: 4112kb
input:
536870912 536870912 233225286 372408647
output:
179 0 0 536870912 0 0 0 268435456 0 134217728 0 268435456 0 201326592 0 268435456 0 201326592 0 234881024 0 218103808 0 234881024 0 0 536870912 536870912 536870912 0 536870912 268435456 536870912 134217728 536870912 268435456 536870912 201326592 536870912 268435456 536870912 226492416 0 234881024 53...
result:
wrong answer Jury has a better answer