QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795104#9804. Guess the Polygonucup-team3734#RE 17ms10572kbPython31.3kb2024-11-30 17:54:302024-11-30 17:54:30

Judging History

This is the latest submission verdict.

  • [2024-11-30 17:54:30]
  • Judged
  • Verdict: RE
  • Time: 17ms
  • Memory: 10572kb
  • [2024-11-30 17:54:30]
  • Submitted

answer

import sys

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

class Frac:
    def __init__(self, n, d=1):
        self.n = n
        self.d = d
        g = gcd(n, d)
        self.n //= g
        self.d //= g

    def __add__(self, other):
        return Frac(self.n * other.d + other.n * self.d, self.d * other.d)
    
    def __sub__(self, other):
        return Frac(self.n * other.d - other.n * self.d, self.d * other.d)
    
    def __mul__(self, other):
        return Frac(self.n * other.n, self.d * other.d)
    
    def __lt__(self, other):
        return self.n * other.d < other.n * self.d

def ask(x: Frac):
    print('?', x.n, x.d)
    sys.stdout.flush()
    p, q = map(int, input().split())
    return Frac(p, q)

def solve():
    n = int(input())

    pts = []
    for i in range(n):
        x, y = map(int, input().split())
        pts.append((Frac(x), Frac(y)))

    pts = list(sorted(pts))
    answers = [Frac(0) for _ in range(n)]
    for i in range(1, n - 1):
        answers[i] = ask(pts[i][0])
    S = Frac(0)
    for i in range(0, n - 1):
        S += (pts[i + 1][0] - pts[i][0]) * (answers[i] + answers[i + 1])
    S *= Frac(1, 2)
    print('!', S.n, S.d)
    sys.stdout.flush()


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 17ms
memory: 10572kb

input:

2
4
3 0
1 3
1 1
0 0
2 1
2 1
3
0 0
999 1000
1000 999
1999 1000

output:

? 1 1
? 1 1
! 3 1
? 999 1
! 1999 2

result:

ok correct! (2 test cases)

Test #2:

score: -100
Dangerous Syscalls

input:

9
4
1 1
1 3
3 0
0 0
3 1
3 1

output:

? 1 1
? 1 1
! 9 2

result: