Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(sub):
    global N, K
    nsub = {}
    for i in list(sub.keys()):
        ni = i + 1
        if ni < N:
            s = sub[i] + S[ni]
            nsub[ni] = s
            A.add(s)
    if len(nsub) > 0:
        dfs(nsub)


S = list(input())
N = len(S)
K = int(input())
alpha = [chr(ord('a') + i) for i in range(26)]

A = set()
for c in alpha:
    if len(A) < K:
        sub = {}
        for i, s in enumerate(S):
            if c == s:
                A.add(s)
                sub[i] = c
        dfs(sub)

A = list(A)
A.sort()
print(A[K - 1])


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(s, pos):
    global N, K
    ns = {}
    if len(A) > K:
        return
    for i in pos:
        ni = i + 1
        if ni < N:
            x = s + S[ni]
            if x in ns:
                ns[x].append(ni)
            else:
                ns[x] = [ni]
    candidate = []
    for x in list(ns.keys()):
        candidate.append((x, ns[x]))
    candidate.sort()
    for c, idx in candidate:
        A.add(c)
        dfs(c, idx)


S = list(input())
N = len(S)
K = int(input())
alpha = [chr(ord('a') + i) for i in range(26)]

A = set()
for c in alpha:
    if len(A) < K:
        pos = []
        for i, s in enumerate(S):
            if c == s:
                A.add(c)
                pos.append(i)
        dfs(c, pos)

A = list(A)
A.sort()
print(A[K - 1])

Buggy python submission (verdict: Runtime Error):
def dfs(s):
    global K, cnt, ans, S
    if cnt == K:
        ans = s
        return
    for c in alpha:
        if S.count(s + c) > 0:
            cnt += 1
            dfs(s + c)


S = input()
K = int(input())
cnt = 0
alpha = [chr(ord('a') + i) for i in range(26)]
ans = ''
dfs('')
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(s, pos):
    global N, K
    ns = {}
    if len(A) > K:
        return
    for i in pos:
        ni = i + 1
        if ni < N:
            x = s + S[ni]
            if x in ns:
                ns[x].append(ni)
            else:
                ns[x] = [ni]
    candidate = []
    for x in list(ns.keys()):
        candidate.append((x, ns[x]))
    candidate.sort()
    for c, idx in candidate:
        A.add(c)
        dfs(c, idx)


S = list(input())
N = len(S)
K = int(input())
alpha = [chr(ord('a') + i) for i in range(26)]

A = set()
for c in alpha:
    if len(A) < K:
        pos = []
        for i, s in enumerate(S):
            if c == s:
                A.add(c)
                pos.append(i)
        dfs(c, pos)

A = list(A)
A.sort()
print(A[K - 1])
Buggy python submission (verdict: Time Limit Exceeded):
def solve(A, B):
    M = A * B
    cnt = 0

    x, y = A, B
    while y - x >= 1:
        x += 1
        y = M // x if M % x else M // x - 1
        cnt += 1
    cnt += y - 1

    x, y = B, A
    while y - x >= 1:
        x += 1
        y = M // x if M % x else M // x - 1
        cnt += 1
    cnt += y - 1

    return cnt


Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]

for A, B in Query:
    print(solve(A, B))


Fixed submission:
def solve(A, B):
    from math import sqrt
    M = A * B
    cnt = 0

    x, y = A, B
    if y - x >= 1:
        z = int(sqrt(M))
        x = z
        y = M // x if M % x else M // x - 1
        cnt += z - A
    cnt += y - 1

    x, y = B, A
    if y - x >= 1:
        z = int(sqrt(M))
        x = z
        y = M // x if M % x else M // x - 1
        cnt += z - B
    cnt += y - 1

    return cnt


Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]

for A, B in Query:
    print(solve(A, B))
Buggy python submission (verdict: Runtime Error):
class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.par_weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            root = self.find(self.parents[x])
            self.par_weight[x] += self.par_weight[self.parents[x]]
            self.parents[x] = root
            return self.parents[x]

    def union(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            self.par_weight[x] = -w
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.par_weight[y] = w

    def weight(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return self.par_weight[x] + self.weight(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.find_position(y) - self.find_position(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)


Fixed submission:
class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.par_weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            root = self.find(self.parents[x])
            self.par_weight[x] += self.par_weight[self.parents[x]]
            self.parents[x] = root
            return self.parents[x]

    def union(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            self.par_weight[x] = -w
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.par_weight[y] = w

    def weight(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return self.par_weight[x] + self.weight(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.weight(y) - self.weight(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(L, i, pos):
    global goal, LL
    rst = False
    if i == LL:
        rst |= (pos == goal)
    else:
        d = L[i]
        if pos + d not in memo[i]:
            r = dfs(L, i + 1, pos + d)
            memo[i][pos + d] = r
        rst |= memo[i][pos + d]
        if pos - d not in memo[i]:
            r = dfs(L, i + 1, pos - d)
            memo[i][pos - d] = r
        rst |= memo[i][pos - d]
    return rst


S = input().split('T')
x, y = map(int, input().split())

X = []
Y = []
for i, s in enumerate(S):
    if i % 2 == 0:
        X.append(len(s))
    else:
        Y.append(len(s))

if sum(X) < abs(x) or sum(Y) < abs(y):
    print('No')
    exit()


goal, LL = x, len(X)
memo = [{} for _ in range(LL)]
memo[0][X[0]] = True
flag_x = dfs(X, 1, X[0])

goal, LL = y, len(Y)
memo = [{} for _ in range(LL)]
flag_y = dfs(Y, 0, 0)

if flag_x and flag_y:
    print('Yes')
else:
    print('No')


Fixed submission:
S = input().split('T')
x, y = map(int, input().split())

X = []
Y = []
for i, s in enumerate(S):
    if i % 2 == 0:
        X.append(len(s))
    else:
        Y.append(len(s))

if sum(X) < abs(x) or sum(Y) < abs(y):
    print('No')
    exit()

pos = set([X[0]])
for i in range(1, len(X)):
    d = X[i]
    npos = set()
    for p in pos:
        npos.add(p + d)
        npos.add(p - d)
    pos = npos
flag_x = x in pos

pos = set([0])
for i in range(len(Y)):
    d = Y[i]
    npos = set()
    for p in pos:
        npos.add(p + d)
        npos.add(p - d)
    pos = npos
flag_y = y in pos

if flag_x and flag_y:
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(L, i, pos):
    global goal, LL
    rst = False
    if i == LL:
        rst |= (pos == goal)
    else:
        d = L[i]
        rst |= dfs(L, i + 1, pos + d)
        rst |= dfs(L, i + 1, pos - d)
    return rst


S = input().split('T')
x, y = map(int, input().split())

X = []
Y = []
for i, s in enumerate(S):
    if i % 2 == 0:
        X.append(len(s))
    else:
        Y.append(len(s))

if sum(X) < abs(x) or sum(Y) < abs(y):
    print('No')
    exit()


goal, LL = x, len(X)
flag_x = dfs(X, 1, X[0])
goal, LL = y, len(Y)
flag_y = dfs(Y, 0, 0)

if flag_x and flag_y:
    print('Yes')
else:
    print('No')


Fixed submission:
S = input().split('T')
x, y = map(int, input().split())

X = []
Y = []
for i, s in enumerate(S):
    if i % 2 == 0:
        X.append(len(s))
    else:
        Y.append(len(s))

if sum(X) < abs(x) or sum(Y) < abs(y):
    print('No')
    exit()

pos = set([X[0]])
for i in range(1, len(X)):
    d = X[i]
    npos = set()
    for p in pos:
        npos.add(p + d)
        npos.add(p - d)
    pos = npos
flag_x = x in pos

pos = set([0])
for i in range(len(Y)):
    d = Y[i]
    npos = set()
    for p in pos:
        npos.add(p + d)
        npos.add(p - d)
    pos = npos
flag_y = y in pos

if flag_x and flag_y:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
def main():
  N = int(input())
  li = list(map(int, input().split()))

  num_of_operation = 0
  
  while True:
    for num in li:
      if num % 2 == 1:
        break
    
    for i in range(N):
      li[i] //= 2
    num_of_operation += 1
  
  print(num_of_operation)

if __name__ == '__main__':
  main()


Fixed submission:
s = input()

ans = 0
for i in s:
  ans += int(i)
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()

offset = len(S) - len(T)

ans = []
for d in range(offset + 1):
    A = ''
    Td = '?' * d + T
    for i in range(len(S)):
        if i < len(Td) and S[i] != Td[i] and '?' not in [S[i], Td[i]]:
            break
        else:
            c = S[i] if Td[i] == '?' else Td[i]
            A += c
    else:        
        ans.append(A.replace('?', 'a'))

if len(ans):
    ans.sort()
    print(ans[0])
else:
    print('UNRESTORABLE')


Fixed submission:
import re


S_ = input()
T = input()

S_ = S_[::-1]
T = T[::-1]

t = ''
for c in T:
    t += '[?' + c + ']'
regex = re.compile(t)

S, cnt = regex.subn(T, S_, count=1)
if cnt:
    S = S.replace('?', 'a')
    print(S[::-1])
else:
    print('UNRESTORABLE')

Buggy python submission (verdict: Runtime Error):
Sx = input()
T = input()

offset = len(Sx) - len(T) + 1
check = [1] * offset

ans = 'UNRESTORABLE'
if len(Sx) >= len(T):
    for d in range(offset):
        for j in range(len(T)):
            check[d] &= (Sx[j + d] == T[j] or Sx[j + d] == '?')
    
    if any(check):
        k = max(k for k, c in enumerate(check) if c)
        ans = ''
        for i in range(len(Sx)):
            if i < k or k + len(T) < i:
                c = Sx[i]
            else:
                c = T[i - k]
            c = 'a' if c == '?' else c

            ans += c

print(ans)


Fixed submission:
import re


S_ = input()
T = input()

S_ = S_[::-1]
T = T[::-1]

t = ''
for c in T:
    t += '[?' + c + ']'
regex = re.compile(t)

S, cnt = regex.subn(T, S_, count=1)
if cnt:
    S = S.replace('?', 'a')
    print(S[::-1])
else:
    print('UNRESTORABLE')
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]

ans = float('inf')
for xi in range(N - 1):
    for xj in range(xi + 1, N):
        for yi in range(N - 1):
            for yj in range(yi + 1, N):
                x1 = min([P[xi][0], P[xj][0], P[yi][0], P[yj][0]])
                x2 = max([P[xi][0], P[xj][0], P[yi][0], P[yj][0]])
                y1 = min([P[xi][1], P[xj][1], P[yi][1], P[yj][1]])
                y2 = max([P[xi][1], P[xj][1], P[yi][1], P[yj][1]])
                if x1 == x2 or y1 == y2:
                    continue

                cnt = 0
                for k in range(N):
                    x3, y3 = P[k]
                    if x1 <= x3 <= x2 and y1 <= y3 <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)


Fixed submission:
N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]
P.sort()

ans = float('inf')
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = P[j][0] - P[i][0]
        if x == 0:
            continue

        Q = P[i: j + 1]
        Q.sort(key=lambda q: q[1])
        y = Q[-1][1] - Q[0][1]
        for k in range(0, len(Q) - K + 1):
            for l in range(k + K - 1, len(Q)):
                ny = Q[l][1] - Q[k][1]
                if ny == 0:
                    continue
                y = min(y, ny)
        ans = min(ans, x * y)

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter


def dfs(x):
    res = True
    for e in edge[x]:
        if color[e] is None:
            color[e] = 0 if color[x] else 1
            res &= dfs(e)
        else:
            if color[e] == color[x]:
                res &= False
            else:
                res &= True
    return res


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    edge[A].append(B)
    edge[B].append(A)

color = [None] * N
color[0] = 0
isBin = dfs(0)

if isBin:
    C = Counter(color)
    print(C[0] * C[1] - M)
else:
    print(N * (N - 1) // 2 - M)


Fixed submission:
from collections import Counter
import sys


sys.setrecursionlimit(10 ** 6)


def dfs(x):
    res = True
    for e in edge[x]:
        if color[e] is None:
            color[e] = 0 if color[x] else 1
            res &= dfs(e)
        else:
            if color[e] == color[x]:
                res &= False
            else:
                res &= True
    return res


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    edge[A].append(B)
    edge[B].append(A)

color = [None] * N
color[0] = 0
isBin = dfs(0)

if isBin:
    C = Counter(color)
    print(C[0] * C[1] - M)
else:
    print(N * (N - 1) // 2 - M)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

dp = [[-float('inf')] * (N + 1) for _ in range(2 * N + 1)]
for i in range(2 * N + 1):
    dp[i][0] = 0
for i in range(2 * N):
    for j in range(1, N + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i][j - 1] + A[i])

dp2 = [0] * (N + 1)
for i in range(N + 1):
    B = A[i + N:]
    B.sort()
    dp2[i] = sum(B[:N])

ans = -float('inf')
for i in range(N + 1):
    S1 = dp[i + N][N]
    S2 = dp2[i]
    ans = max(ans, S1 - S2)

print(ans)


Fixed submission:
from heapq import heappush, heapreplace


N = int(input())
A = list(map(int, input().split()))

dp = [0] * (N + 1)
q = []
cnt = 0
for i in range(N):
    a = A[i]
    heappush(q, a)
    cnt += a
dp[0] = cnt
for i in range(N, 2 * N):
    a = A[i]
    if a > q[0]:
        cnt += a - heapreplace(q, a)
    dp[i - N + 1] = cnt


dp2 = [0] * (N + 1)
q = []
cnt = 0
for i in range(2 * N, 3 * N):
    a = A[i]
    heappush(q, -a)
    cnt += a
dp2[N] = cnt
for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    if a < -q[0]:
        cnt += a - (-heapreplace(q, -a))
    dp2[i - N] = cnt

ans = -float('inf')
for i in range(N + 1):
    ans = max(ans, dp[i] - dp2[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

t, a = map(int, input().split())

for i in range(N - 1):
    nt, na = map(int, input().split())
    pt, pa = nt, na
    while pt < t or pa < a:
        pt += nt
        pa += na
    t = pt
    a = pa
print(t + a)


Fixed submission:
N = int(input())

t, a = map(int, input().split())

for i in range(N - 1):
    nt, na = map(int, input().split())
    p = max(t // nt, a // na)
    pt = nt * p
    pa = na * p
    while pt < t or pa < a:
        pt += nt
        pa += na
    t = pt
    a = pa
print(t + a)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

t, a = map(int, input().split())

for i in range(N - 1):
    nt, na = map(int, input().split())
    pt, pa = nt, na
    while pt < t or pa < a:
        pt += nt
        pa += na
    t = pt
    a = pa
print(t + a)


Fixed submission:
N = int(input())

t, a = map(int, input().split())

for i in range(N - 1):
    nt, na = map(int, input().split())
    p = max(t // nt, a // na)
    pt = nt * p
    pa = na * p
    while pt < t or pa < a:
        pt += nt
        pa += na
    t = pt
    a = pa
print(t + a)
Buggy python submission (verdict: Runtime Error):
from collections import deque

Q = [deque() for _ in range(3)]
for i in range(3):
    for s in list(input()):
        Q[i].append(ord(s) - ord('a'))

k = Q[0].popleft()
while True:
    k = Q[k].popleft()
    if len(Q[k]) == 0:
        break

print('ABC'[k])


Fixed submission:
from collections import deque

Q = [deque() for _ in range(3)]
for i in range(3):
    for s in list(input()):
        Q[i].append(ord(s) - ord('a'))

k = Q[0].popleft()
while len(Q[k]) != 0:
    k = Q[k].popleft()

print('ABC'[k])
Buggy python submission (verdict: Time Limit Exceeded):
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
# from collections import defaultdict
ALPHABET_SIZE = 26

def getlist():
	return list(map(int, input().split()))

class Node(object):
	def __init__(self, char, ALPHABET_SIZE):
		self.char = char
		self.children = [-1] * ALPHABET_SIZE
		self.flag = [0] * ALPHABET_SIZE

class Trie(object):
	def __init__(self):
		self.root = Node(' ', ALPHABET_SIZE)

	def _convert_char_to_num(self, char):
		return ord(char) - ord('a')

	def insert(self, word, tail):
		res = 0 #合う値
		current = self.root
		currentFlag = [0] * ALPHABET_SIZE

		for char in word:
			char_index = self._convert_char_to_num(char)
			for i in range(ALPHABET_SIZE):
				currentFlag[i] += current.flag[i]
			res += currentFlag[char_index]
			currentFlag[char_index] = 0

			if current.children[char_index] != -1:
				current = current.children[char_index]

			else:
				new_node = Node(char, ALPHABET_SIZE)
				current.children[char_index] = new_node
				current = new_node

		char_index = self._convert_char_to_num(tail)
		res += currentFlag[char_index]

		current.flag[self._convert_char_to_num(tail)] += 1

		return res

#処理内容
def main():
	N = int(input())
	L = []
	for i in range(N):
		S = input()[::-1]
		L.append([len(S), S])

	L.sort(key = lambda x:x[0])

	ans = 0
	trie = Trie()
	for val, s in L:
		s1 = s[:-1]
		tail = s[-1]
		ans += trie.insert(s1, tail)
		# print(ans)

	print(ans)

if __name__ == '__main__':
	main()


Fixed submission:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
# from collections import defaultdict
ALPHABET_SIZE = 26

def getlist():
	return list(map(int, input().split()))

class Node(object):
	def __init__(self, char):
		self.char = char
		self.children = {}
		self.flag = [0] * ALPHABET_SIZE

class Trie(object):
	def __init__(self):
		self.root = Node(' ')

	def _convert_char_to_num(self, char):
		return ord(char) - 97

	def insert(self, word, tail):
		res = 0 #合う値
		current = self.root
		currentFlag = [0] * ALPHABET_SIZE

		for char in word:
			char_index = self._convert_char_to_num(char)
			for i in range(ALPHABET_SIZE):
				currentFlag[i] += current.flag[i]
			res += currentFlag[char_index]
			currentFlag[char_index] = 0

			if char_index in current.children:
				current = current.children[char_index]

			# if current.children[char_index] != -1:
			# 	current = current.children[char_index]
			else:
				new_node = Node(char)
				current.children[char_index] = new_node
				current = new_node

		char_index = self._convert_char_to_num(tail)
		res += currentFlag[char_index]

		current.flag[self._convert_char_to_num(tail)] += 1

		return res

#処理内容
def main():
	N = int(input())
	L = []
	for i in range(N):
		S = input()[::-1]
		L.append([len(S), S])

	L.sort(key = lambda x:x[0])

	ans = 0
	trie = Trie()
	for val, s in L:
		s1 = s[:-1]
		tail = s[-1]
		ans += trie.insert(s1, tail)
		# print(ans)

	print(ans)

if __name__ == '__main__':
	main()
Buggy python submission (verdict: Runtime Error):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def Binary_Search(N, K, A):
	#初期化
	left = 0
	right = 10 ** 9
	ans = INF
	
	while left <= right:
		mid = (left + right) // 2
		val = 0
		for i in range(N):
			val += int((A[i] - 1) // mid)
		if val <= K:
			ans = min(ans, mid)
			right = mid - 1
		else:
			left = mid + 1

	return ans

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	ans = Binary_Search(N, K, A)
	print(ans)

if __name__ == '__main__':
	main()

Fixed submission:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def Binary_Search(N, K, A):
	#初期化
	left = 0
	right = 10 ** 9
	ans = INF
	
	while left <= right:
		mid = (left + right) // 2
		val = 0
		if mid == 0:
			return 1
		for i in range(N):
			val += int((A[i] - 1) // mid)
		if val <= K:
			ans = min(ans, mid)
			right = mid - 1
		else:
			left = mid + 1

	return ans

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	ans = Binary_Search(N, K, A)
	print(ans)

if __name__ == '__main__':
	main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def divisor(N):
	divisor_list = []
	n = int((N ** 0.5) // 1)
	for i in range(1, n):
		if N % i == 0:
			divisor_list.append(i)
			divisor_list.append(int(N // i))
	#平方数かどうかで場合分け
	if n ** 2 == N:
		divisor_list.append(n)
	else:
		if N % n == 0:
			divisor_list.append(n)
			divisor_list.append(int(N // n))

	return sorted(divisor_list)

#処理内容
def main():
	N = int(input())
	A = getlist()
	DD = defaultdict(int)
	for i in range(N):
		DD[A[i]] += 1

	ans = N
	for i in range(N):
		DD[A[i]] -= 1
		div = divisor(A[i])
		for j in div:
			if DD[j] >= 1:
				ans -= 1
				break
		DD[A[i]] += 1

	print(ans)

if __name__ == '__main__':
	main()

Fixed submission:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

num = 10 ** 6 + 1 #適当に値を入れる
L = [0 for i in range(num)]
ans = 0
N = int(input())
A = getlist()
for i in range(N):
	L[A[i]] += 1

for i in range(num):
	if L[i] >= 1:
		if L[i] == 1:
			ans += 1
		c = 2
		while i * c <= num - 1:
			L[i * c] = 0; c += 1

print(ans)