QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#826245#9770. Middle Pointucup-team008#WA 22ms11928kbPython31.3kb2024-12-22 04:40:312024-12-22 04:40:32

Judging History

你现在查看的是最新测评结果

  • [2024-12-22 04:40:32]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:11928kb
  • [2024-12-22 04:40:31]
  • 提交

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