When answering D question of AtCoder Beginner Contest 236, I encountered a phenomenon in which PyPy and Python have different standard outputs for the same script standard input.
With PyPy, recursion ends halfway and this is not the intended behavior like Python.
Is this a specification? Also, what should I do to get Python-like output on PyPy?
#script.py
import operator
import functools
# input -----
n = int(input())
a = [[0]*n*2 for_in range(n*2)]
for i in range (2*n-1):
for j, e in enumerate (map(int, input().split())), i+1):
a[i][j]=a[j][i]=e
# -----------
defrec(i):
globalans
if not__debug__:
print(f" called rec({i=})\n{pairs=}\n{not_selected=}\n{ans=}\n")
if i==2*n:
an=max(
an,
functools.reduce(
operator.xor,
(a[e1-1][e2-1]for e1, e2 in zip (*[iter(pairs)]*2),
0,
),
)
return
if i%2 == 0:
e=min(not_selected)
pairs.append(e)
not_selected.discard(e)
rec(i+1)
pairs.pop()
not_selected.add(e)
else:
for e in not_selected:
pairs.append(e)
not_selected.discard(e)
rec(i+1)
pairs.pop()
not_selected.add(e)
pairs = [ ]
not_selected=set(range(2*n))
an = 0
rec(0)
print(ans)
2
4 0 1
5 3
2
$python-O script.py
~ console input~
called rec(i=0)
pairs = [ ]
not_selected = {0,1,2,3}
an = 0
called rec(i=1)
pairs = [0]
not_selected = {1,2,3}
an = 0
called rec(i=2)
pairs = [0,1]
not_selected = {2,3}
an = 0
called rec(i=3)
pairs = [0,1,2]
not_selected={3}
an = 0
called rec(i=4)
pairs = [0,1,2,3]
not_selected=set()
an = 0
called rec(i=2)
pairs = [0,2]
not_selected = {1,3}
an=4
called rec(i=3)
pairs = [0,2,1]
not_selected={3}
an=4
called rec(i=4)
pairs = [0,2,1,3]
not_selected=set()
an=4
called rec(i=2)
pairs = [0,3]
not_selected = {1,2}
an=4
called rec(i=3)
pairs = [0,3,1]
not_selected = {2}
an=4
called rec(i=4)
pairs = [0,3,1,2]
not_selected=set()
an=4
called rec(i=2)
pairs = [0,2]
not_selected = {1,3}
an=6
called rec(i=3)
pairs = [0,2,1]
not_selected={3}
an=6
called rec(i=4)
pairs = [0,2,1,3]
not_selected=set()
an=6
called rec(i=2)
pairs = [0,3]
not_selected = {2,1}
an=6
called rec(i=3)
pairs = [0,3,1]
not_selected = {2}
an=6
called rec(i=4)
pairs = [0,3,1,2]
not_selected=set()
an=6
called rec(i=4)
pairs = [0,3,1,2]
not_selected=set()
an=6
6
$pypy-O test.py
~ console input~
called rec(i=0)
pairs = [ ]
not_selected = {0,1,2,3}
an = 0
called rec(i=1)
pairs = [0]
not_selected = {1,2,3}
an = 0
called rec(i=2)
pairs = [0,1]
not_selected = {2,3}
an = 0
called rec(i=3)
pairs = [0,1,2]
not_selected={3}
an = 0
called rec(i=4)
pairs = [0,1,2,3]
not_selected=set()
an = 0
4
for e in not_selected:
This is because not_selected is rewriting not_selected while looping about the element.
Make a copy of the container you plan to rewrite before using it for the loop as follows:
for e intuple(not_selected):
(Compared to the revised results, the results of Python's execution are also abnormal, with pairs=[0,2] appearing twice.)
© 2024 OneMinuteCode. All rights reserved.