QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#826245 | #9770. Middle Point | ucup-team008# | WA | 22ms | 11928kb | Python3 | 1.3kb | 2024-12-22 04:40:31 | 2024-12-22 04:40:32 |
Judging History
answer
from fractions import Fraction
def ispowoftwo(n):
return n&(n-1) == 0
def solve():
maxa, maxb = (int(x) for x in input().split())
wanta, wantb = (int(x) for x in input().split())
afrac = Fraction(wanta, max(1, maxa))
bfrac = Fraction(wantb, max(1, maxb))
adenom = afrac.denominator
bdenom = bfrac.denominator
if not ispowoftwo(adenom) or not ispowoftwo(bdenom):
print(-1)
return
can = set()
can.add((Fraction(0, 1), Fraction(0, 1)))
can.add((Fraction(0, 1), Fraction(1, 1)))
can.add((Fraction(1, 1), Fraction(0, 1)))
can.add((Fraction(1, 1), Fraction(1, 1)))
q = [(afrac, bfrac)]
ret = []
while q:
(a, b) = q.pop()
if (a, b) in can:
continue
can.add((a, b))
if a.denominator == 1:
al = Fraction(a)
else:
al = Fraction(a.numerator // 2, a.denominator // 2)
ar = 2 * a - al
if b.denominator == 1:
bl = Fraction(b)
else:
bl = Fraction(b.numerator // 2, b.denominator // 2)
br = 2 * b - bl
q.append((al, bl))
q.append((ar, br))
ret.append((al, bl, ar, br))
ret.sort(key=lambda x: max(x[0].denominator, x[1].denominator, x[2].denominator, x[3].denominator))
print(len(ret))
for a, b, c, d in ret:
print(int(a * maxa), int(b * maxb), int(c * maxa), int(d * maxb))
solve()
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 22ms
memory: 11924kb
input:
2 2 1 1
output:
1 0 0 2 2
result:
ok correct!
Test #2:
score: 0
Accepted
time: 4ms
memory: 11880kb
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: 22ms
memory: 11800kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 22ms
memory: 11792kb
input:
2024 0 1012 0
output:
1 0 0 2024 0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 18ms
memory: 11900kb
input:
2024 2024 2023 2023
output:
-1
result:
ok correct!
Test #6:
score: 0
Accepted
time: 21ms
memory: 11880kb
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: 21ms
memory: 11840kb
input:
2024 2026 2024 2026
output:
0
result:
ok correct!
Test #8:
score: 0
Accepted
time: 21ms
memory: 11812kb
input:
1000000000 1000000000 70 0
output:
-1
result:
ok correct!
Test #9:
score: 0
Accepted
time: 21ms
memory: 11700kb
input:
3 6 2 4
output:
-1
result:
ok correct!
Test #10:
score: 0
Accepted
time: 14ms
memory: 11876kb
input:
7 7 7 2
output:
-1
result:
ok correct!
Test #11:
score: 0
Accepted
time: 18ms
memory: 11812kb
input:
6 2 5 2
output:
-1
result:
ok correct!
Test #12:
score: 0
Accepted
time: 12ms
memory: 11764kb
input:
5 7 5 5
output:
-1
result:
ok correct!
Test #13:
score: 0
Accepted
time: 11ms
memory: 11808kb
input:
4 7 2 3
output:
-1
result:
ok correct!
Test #14:
score: 0
Accepted
time: 21ms
memory: 11860kb
input:
8 2 2 2
output:
2 0 2 8 2 0 2 4 2
result:
ok correct!
Test #15:
score: 0
Accepted
time: 17ms
memory: 11764kb
input:
3 3 0 2
output:
-1
result:
ok correct!
Test #16:
score: 0
Accepted
time: 18ms
memory: 11920kb
input:
7 7 1 4
output:
-1
result:
ok correct!
Test #17:
score: 0
Accepted
time: 13ms
memory: 11924kb
input:
6 3 6 1
output:
-1
result:
ok correct!
Test #18:
score: 0
Accepted
time: 8ms
memory: 11880kb
input:
4 2 2 1
output:
1 0 0 4 2
result:
ok correct!
Test #19:
score: 0
Accepted
time: 17ms
memory: 11832kb
input:
7 2 3 2
output:
-1
result:
ok correct!
Test #20:
score: 0
Accepted
time: 10ms
memory: 11908kb
input:
2 7 0 3
output:
-1
result:
ok correct!
Test #21:
score: 0
Accepted
time: 11ms
memory: 11712kb
input:
1 7 1 0
output:
0
result:
ok correct!
Test #22:
score: 0
Accepted
time: 12ms
memory: 11912kb
input:
5 1 0 0
output:
0
result:
ok correct!
Test #23:
score: 0
Accepted
time: 21ms
memory: 11828kb
input:
8 7 4 3
output:
-1
result:
ok correct!
Test #24:
score: 0
Accepted
time: 21ms
memory: 11792kb
input:
180057652 674822131 110693180 428023738
output:
-1
result:
ok correct!
Test #25:
score: 0
Accepted
time: 16ms
memory: 11852kb
input:
62347541 812142018 42922107 486416913
output:
-1
result:
ok correct!
Test #26:
score: 0
Accepted
time: 7ms
memory: 11856kb
input:
239604722 244429197 78993837 108804105
output:
-1
result:
ok correct!
Test #27:
score: 0
Accepted
time: 22ms
memory: 11812kb
input:
416861903 381749084 375027630 373683256
output:
-1
result:
ok correct!
Test #28:
score: 0
Accepted
time: 21ms
memory: 11928kb
input:
594119084 519068971 429116021 298715088
output:
-1
result:
ok correct!
Test #29:
score: -100
Wrong Answer
time: 20ms
memory: 11916kb
input:
536870912 536870912 233225286 372408647
output:
179 536870912 0 536870912 536870912 0 0 0 536870912 0 536870912 536870912 536870912 0 0 536870912 0 536870912 268435456 536870912 536870912 0 268435456 0 536870912 0 268435456 536870912 536870912 0 0 268435456 0 0 0 268435456 536870912 0 536870912 268435456 536870912 536870912 268435456 536870912 40...
result:
wrong answer Jury has a better answer