글 읽기 - 음 재귀 없애고 반복으로 고쳤는데도 시간초과.....python3으로는.....

blutics 6년 전 0

python3으로는 안되는걸까요??

재귀를 반복으로 고치고도 시간 초과가 나네요.

_sum+=hole[i]*(0!=round(x[i].real)) 이부분은 원래 스트링으로 고쳤다가 다시 float에 넣었는데

안그러면 0으로 인식을 못하더라구요.

아무튼.....애잇!!!!

shot과 hole을 곱하는것도 fft로 하는건가?? 방법이 있는건가요.....

pypy로 고쳐야하는건가요.....

import sys
import math

def fft(x,inv):
    n=len(x)
    p=int(math.log(n,2))+1
    q='%0'+'%d'%(len(bin(n-1))-2)+'d'
    r=[int((q%int(bin(i)[2:]))[::-1],2) for i in range(n)]
    tmp=[]
    for i in r:
        tmp+=x[i],
    x=tmp        
    for s in range(1,p):
        m=2**s
        wm=math.exp(1)**(math.pi*1j*2/m*(-1 if inv else 1))
        for k in range(0,n,m):
            w=1
            for j in range(m//2):
                t=w*x[k+j+m//2]
                u=x[k+j]
                x[k+j]=u+t
                x[k+j+m//2]=u-t
                w*=wm
    if inv:
        for i in range(n): x[i]/=n
    return x

def extension(a,m):
    n=math.ceil(math.log(m,2))+1
    return a+[0]*(2**n-len(a))

def multiply(a,b):
    n=max(len(a),len(b))
    a=extension(a,n)
    b=extension(b,n)
    c=fft(a,False)
    d=fft(b,False)
    return fft([c[i]*d[i]for i in range(len(c))],True)
    
read=sys.stdin.readline
temp=[]
hole=[0]*200001
for i in range(int(read())):
    temp+=int(read()),
shot=[0]*(max(temp)*2+1)
shot[0]=1
for i in temp:
    shot[i]=1
for i in range(int(read())):
    hole[int(read())]+=1
x=multiply(shot,shot)
_sum=0
for i in range(1,len(x)):
    _sum+=hole[i]*(0!=round(x[i].real))
print(_sum)

blutics 6년 전 0

애초에 런타임 에러가.....젠장...ㅠㅠ

blutics 6년 전 0

pypy/pypy3에서 왜 런타임 에러가.......ㅠㅠ

blutics 6년 전 0

아.....진짜......해결했네요.......파이썬은 문법선택이 중요하네요........

pypy/pypy3에서 왜 런타임 에러뜨는지는 아직도 모르겠네요.......

startlink 6년 전 1

PyPy3에서 런타임 에러는 예전부터 존재하던 채점 프로그램 버그? 버그라고 하긴 그렇고, 아무튼 수정했습니다. 정확하게는 PyPy3에서 사용하는 시스템 콜 중에서 현재 채점 프로그램이 허용하지 않는 것이 있었습니다. 이를 허용하게 바꿨습니다.

이와 관련된 모든 제출을 재채점했습니다.

재채점 결과: https://www.acmicpc.net/rejudg...

blutics 6년 전 0

옷!!!! 감사합니다!!!!!

startlink 6년 전 1

PyPy에서 런타임 에러가 나는 이유는 30번 줄 때문입니다.

Traceback (most recent call last):
  File "Main.py", line 51, in <module>
    x=multiply(shot,shot)
  File "Main.py", line 34, in multiply
    a=extension(a,n)
  File "Main.py", line 30, in extension
    return a+[0]*(2**n-len(a))
TypeError: unsupported operand type(s) for *: 'list' and 'float'

blutics 6년 전 0

감사합니다!!!! 아침부터 수고하십니다!

jh05013 6년 전 1

math.ceil이 파이썬2에서는 float이라니... 파이썬2는 무섭군요.

blutics 6년 전 0

그래서 파이썬파이썬 했나봄 ㅎㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

음 재귀 없애고 반복으로 고쳤는데도 시간초과.....python3으로는.....

blutics 6년 전 0

blutics 6년 전 0

blutics 6년 전 0

blutics 6년 전 0

startlink 6년 전 1

blutics 6년 전 0

startlink 6년 전 1

blutics 6년 전 0

jh05013 6년 전 1

blutics 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말