Problem p02679 (python)

Fixed submission:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
# INF = 1e18+10

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

n = int(input())

a_b = [() for i in range(n)]
m_b_a = [() for i in range(n)]

# a_b_value_indices = {}
# m_b_a_value_indices = {}

a_b_value_count = {}
m_b_a_value_count = {}

a_b_value_rep = {}
m_b_a_value_rep = {}

used = [False for _ in range(n)]
zeroes = 0
is_zero = [False for _ in range(n)]

for i in range(n):
	a, b = map(int, input().split())

	if a == 0 and b == 0:
		zeroes += 1
		used[i] = True
		is_zero[i] = True
	else:
		if a == 0:
			a_b[i] = (0, 1)
			m_b_a[i] = (1, 0)
		elif b == 0:
			a_b[i] = (1, 0)
			m_b_a[i] = (0, 1)
		else:
			neg = False
			if a*b < 0:
				neg = True
			d = gcd(abs(a), abs(b))
			a = abs(a) // d
			b = abs(b) // d

			if neg:
				a_b[i] = (-a, b)
				m_b_a[i] = (b, a)
			else:
				a_b[i] = (a, b)
				m_b_a[i] = (-b, a)

		a_b_value_count[a_b[i]] = a_b_value_count.get(a_b[i], 0) + 1
		# a_b_value_indices[a_b[i]] = a_b_value_indices.get(a_b[i], []) + [i]
 
		m_b_a_value_count[m_b_a[i]] = m_b_a_value_count.get(m_b_a[i], 0) + 1
		# m_b_a_value_indices[m_b_a[i]] = m_b_a_value_indices.get(m_b_a[i], []) + [i]
		if a_b[i] not in a_b_value_rep:
			a_b_value_rep[a_b[i]] = i
		if m_b_a[i] not in m_b_a_value_rep:
			m_b_a_value_rep[m_b_a[i]] = i

ans = 1
for i in range(n):
	if not is_zero[i] and not used[a_b_value_rep[a_b[i]]]:
		# if not connected
		if a_b[i] not in m_b_a_value_count:
			ans *= pow(2, a_b_value_count[a_b[i]], MODULO)
			ans %= MODULO
			used[a_b_value_rep[a_b[i]]] = True
			# for j in a_b_value_indices[a_b[i]]:
			# 	used[j] = True
		else:
			s = a_b_value_count[a_b[i]]
			t = m_b_a_value_count[a_b[i]]
			ans *= ((1*pow(2, s, MODULO) + 1*pow(2, t, MODULO) -1) % MODULO)
			ans %= MODULO

			used[a_b_value_rep[a_b[i]]] = True
			used[m_b_a_value_rep[a_b[i]]] = True
			# for j in m_b_a_value_indices[a_b[i]]:
			# 	used[j] = True
 
			# used_a_b_keys.add(a_b_key)
			# used_a_b_keys.add(-1/a_b_key)
 
 
# -1 is for empty
print((ans-1+zeroes) % MODULO)

Buggy submission (verdict: Runtime Error):
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a_b_value_count = {}
m_b_a_value_count = {}
zeroes = 0

for i in range(n):
	a, b = map(int, input().split())

	if a == 0 and b == 0:
		zeroes += 1
	else:
		if a == 0:
			a_b = 0
			m_b_a = INF
		elif b == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a / b
			m_b_a = -b / a

		a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		m_b_a_value_count[m_b_a] = m_b_a_value_count.get(m_b_a, 0) + 1

a_b = list(set(a_b_value_count.keys()))
m_b_a = [-1/item for item in a_b]

# a_b.sort()
# m_b_a.sort(reverse=True)


# print("a_b", a_b)
# print("a_b_value_count", a_b_value_count)
# print()

# print("m_b_a", m_b_a)
# print("m_b_a_value_count", m_b_a_value_count)

if len(a_b) != len(m_b_a):
	# print("Error!")
	exit()

n = len(a_b)
used = [False for _ in range(n)]

mba_to_ind = {}
for i in range(n):
	mba_to_ind[m_b_a[i]] = i

ans = 1
for i in range(n):
	# print("i", i)
	if not used[i]:
		a_b_key = a_b[i]
		# print("a_b_key", a_b_key)
		# if not connected
		if a_b_key not in m_b_a_value_count:
			# print("not connected")
			ans *= pow(2, a_b_value_count[a_b_key], MODULO)
			ans %= MODULO
			used[i] = True
			# for j in a_b_value_indices[a_b[i]]:
			# 	used[j] = True
		else:
			# print(" connected")
			s = a_b_value_count[a_b_key]
			t = m_b_a_value_count[a_b_key]
			# print("s, t", s, t)
			ans *= (1*pow(2, s, MODULO) + 1*pow(2, t, MODULO) -1)
			ans %= MODULO

			# for j in a_b_value_indices[a_b[i]]:
			used[i] = True
			# for j in m_b_a_value_indices[a_b[i]]:
			used[mba_to_ind[a_b_key]] = True
	# print("ans", ans)
	# print("used", used)
	# print()


			# used_a_b_keys.add(a_b_key)
			# used_a_b_keys.add(-1/a_b_key)


# -1 is for empty
print((ans-1+zeroes) % MODULO)

Buggy submission (verdict: Runtime Error):
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]

a_b_value_count = {} # a_b values
m_b_a_value_count = {} # a_b values

used_a_b_keys = set()
# a_b_used = {}
# [False for _ in range(n)]
# m_b_a_used = [False for _ in range(n)]
used = [False for _ in range(n)]

zeroes = 0
for i in range(n):
	a[i], b[i] = map(int, input().split())

	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		m_b_a_value_count[m_b_a] = m_b_a_value_count.get(m_b_a, 0) + 1

ans = 1
for a_b_key in a_b_value_count.keys():
	if a_b_key not in used_a_b_keys:
		# not connected
		if a_b_key not in m_b_a_value_count:
			ans *= pow(2, a_b_value_count[a_b_key], MODULO)
			ans %= MODULO
			used_a_b_keys.add(a_b_key)
			# m_b_a_used[-1/a_b_key] = True
		else:
			a = a_b_value_count[a_b_key]
			b = m_b_a_value_count[a_b_key]
			ans *= ((1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1) % MODULO)
			ans %= MODULO

			used_a_b_keys.add(a_b_key)
			used_a_b_keys.add(-1/a_b_key)


	# if not used[i]:
	# 	if len(graph[i]) == 0:
	# 		used[i] = True
	# 		ans *= 2
	# 		ans %= MODULO
	# 	else:
	# 		chet, nechet = 0, 0
	# 		# for item in 
	# 		a, b = dfs_chet_nechet(i)
	# 		ans *= ((1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1) % MODULO)
	# 		# ans *= comb(i)
	# 		ans %= MODULO

# -1 is for empty
print((ans-1+zeroes) % MODULO)

Buggy submission (verdict: Runtime Error):
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]

a_b_value_count = {} # a_b values
m_b_a_value_count = {} # a_b values

a_b_used = [False for _ in range(n)]
# m_b_a_used = [False for _ in range(n)]
used = [False for _ in range(n)]

zeroes = 0
for i in range(n):
	a[i], b[i] = map(int, input().split())

	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		m_b_a_value_count[m_b_a] = m_b_a_value_count.get(m_b_a, 0) + 1

ans = 1
for a_b_key in a_b_used.keys():
	if not a_b_used[a_b_key]:
		# not connected
		if m_b_a_value_count[a_b_key] == 1:
			ans *= pow(2, a_b_value_count[a_b_keys], MODULO)
			ans %= MODULO
			a_b_used[a_b_key] = True
			# m_b_a_used[-1/a_b_key] = True
		else:
			a = a_b_value_count[a_b_keys]
			b = m_b_a_value_count[a_b_keys]
			ans *= ((1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1) % MODULO)
			ans %= MODULO

			a_b_used[a_b_keys] = True
			a_b_used[-1/a_b_keys] = True


	# if not used[i]:
	# 	if len(graph[i]) == 0:
	# 		used[i] = True
	# 		ans *= 2
	# 		ans %= MODULO
	# 	else:
	# 		chet, nechet = 0, 0
	# 		# for item in 
	# 		a, b = dfs_chet_nechet(i)
	# 		ans *= ((1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1) % MODULO)
	# 		# ans *= comb(i)
	# 		ans %= MODULO

# -1 is for empty
print((ans-1+zeroes) % MODULO)

Buggy submission (verdict: Runtime Error):
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]

for i in range(n):
	a[i], b[i] = map(int, input().split())

graph = [[] for _ in range(n)]
value_indices = {} # a_b values
zeroes = 0
used = [False for _ in range(n)]
for i in range(n):
	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
		# for j in range(n):
		# 	graph[i].append(j)
		# 	graph[j].append(i)
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		if m_b_a in value_indices:
			for j in value_indices[m_b_a]:
				graph[i].append(j)
				graph[j].append(i)
		value_indices[a_b] = value_indices.get(a_b, []) + [i]

# print("value_indices", value_indices)
# print("graph", graph)

def dfs_chet_nechet(i, chet=0, nechet=0):
	# print("dfs_chet_nechet", i)
	used[i] = True
	a, b = chet, nechet
	for child in graph[i]:
		if not used[child]:
			a1, b1 = dfs_chet_nechet(child, nechet, chet)
			a += b1
			b += a1
	# print("return  a+1, b")
	return a+1, b


# def comb(i):
# 	# print("comb", i)
# 	layers = [[i], []]
# 	used[i] = True

# 	chet = 0
# 	nechet = 0
# 	is_chet = True
# 	cur_layer_ind = 0
# 	next_layer_ind = 1

# 	while len(layers[cur_layer_ind]) > 0:
# 		if is_chet:
# 			cur_layer_ind = 0
# 			next_layer_ind = 1
# 			chet += len(layers[cur_layer_ind])
# 		else:
# 			cur_layer_ind = 1
# 			next_layer_ind = 0
# 			nechet += len(layers[cur_layer_ind])
# 		is_chet = not is_chet
# 		# layers.append(cur_layer)
# 		layers[next_layer_ind] = []
# 		for item in layers[cur_layer_ind]:
# 			for child in graph[item]:
# 				if not used[child]:
# 					layers[next_layer_ind].append(child)
# 					used[child] = True
# 		# cur_layer = next_layer.copy()
# 	# including empty
# 	return 1*pow(2, chet, MODULO) + 1*pow(2, nechet, MODULO) -1


ans = 1
for i in range(n):
	if not used[i]:
		if len(graph[i]) == 0:
			used[i] = True
			ans *= 2
			ans %= MODULO
		else:
			a, b = dfs_chet_nechet(i)
			ans *= (1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1)
			# ans *= comb(i)
			ans %= MODULO

# -1 is for empty
print((ans-1+zeroes) % MODULO)

Buggy submission (verdict: Runtime Error):
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
a_b = [0 for i in range(n)]
m_b_a = [0 for i in range(n)]

for i in range(n):
	a[i], b[i] = map(int, input().split())
	a_b[i] = a[i] / b[i]
	m_b_a[i] = -b[i] / a[i]

# print("a_b", a_b)
# print("m_b_a", m_b_a)

graph = [[] for _ in range(n)]
# rep_size = {}
value_indices = {} # a_b values
# value_size = {} # a_b values
for i in range(n):
	if m_b_a[i] in value_indices:
		for j in value_indices[m_b_a[i]]:
			graph[i].append(j)
			graph[j].append(i)
		# rep_size[rep] += value_size[m_b_a[i]]
		# rep_size[i] = 1
	value_indices[a_b[i]] = value_indices.get(a_b[i], []) + [i]
	 # = value_rep.get(a_b[i], i)
	# value_size[a_b[i]] = value_size.get(a_b[i], 0) + 1

# print("value_indices", value_indices)
# print("graph", graph)

def comb(i):
	layers = []
	cur_layer = [i]
	next_layer = []
	used[i] = True
	while len(cur_layer) > 0:
		layers.append(cur_layer)
		next_layer = []
		for item in cur_layer:
			for child in graph[item]:
				if not used[child]:
					next_layer.append(child)
					used[child] = True
		cur_layer = next_layer.copy()
	# print(layers)
	chet = 0
	nechet = 0
	for i in range(len(layers)):
		if i % 2 == 0:
			chet += len(layers[i])
		else:
			nechet += len(layers[i])
	return pow(2, chet, MODULO) + pow(2, nechet, MODULO) -1
	# return 1


ans = 1
used = [False for _ in range(n)]
for i in range(n):
	if not used[i]:
		if len(graph[i]) == 0:
			used[i]
			ans *= 2
			ans %= MODULO
		else:
			ans *= comb(i)
			ans %= MODULO
print(ans-1)