Problem:


Score : 600 points

Problem Statement

Takahashi has N balls with positive integers written on them. The integer written on the i-th ball is A_i.
He would like to form some number of pairs such that the sum of the integers written on each pair of balls is a power of 2.
Note that a ball cannot belong to multiple pairs.
Find the maximum possible number of pairs that can be formed.

Here, a positive integer is said to be a power of 2 when it can be written as 2^t using some non-negative integer t.

Constraints

1 \leq N \leq 2\times 10^5

1 \leq A_i \leq 10^9

A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible number of pairs such that the sum of the integers written on each pair of balls is a power of 2.

Sample Input 1

3
1 2 3

Sample Output 1

1

We can form one pair whose sum of the written numbers is 4 by pairing the first and third balls.
Note that we cannot pair the second ball with itself.

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2



Sample input:
3
1 2 3


Sample output:
1

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict, deque
# import random
N = int(input())
tmp = list(map(int, input().split()))
# tmp = [random.randint(1,10**9) for _ in range(10**5)]
# print("run")

An = deque()
for a in tmp:
    An.append(a)

maxA = max(tmp)

t2 = [2**i for i in range(32) if 2**i <= maxA]
t2.reverse()

ans = 0
for t in t2:
    # print(f"t={t}")

    tmp_dict = defaultdict(list)
    for A in An:
        tmp_dict[A%t].append(A)
    # print("An")
    # print(f"tmp_dict len = {len(tmp_dict)}")

    tmp = 0
    for k,v in list(tmp_dict.items()):
        if k == 0 or k == t:
            m = len(v) // 2
        else:
            if len(v) < len(tmp_dict[t-k]):
                m = len(v)
                dellist = v
            else:
                m = len(tmp_dict[t-k])
                dellist = tmp_dict[t-k]

        if m > 0:
            # print(f"m={m}")
            tmp += m
            for l in dellist:
                try:
                    # An.remove(l)
                    pass
                except Exception:
                    pass
    ans += tmp//2

print(ans)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
Ae=[]
Ao=[]
for i in range(N):
    if A[i]%2==0:
        Ae.append(A[i])
    else:
        Ao.append(A[i])
Ae.sort()
Ao.sort()
s=0
t=0
i=1
while i<=len(Ao):
    a=int(math.log2(Ao[-i]))
    if 2**(a+1)-Ao[-i] in Ao[:-i]:
        s+=1
        Ao.remove(2**(a+1)-Ao[-i])
        i+=1
    else:
        i+=1
j=1
while j<=len(Ae):
    b=int(math.log2(Ae[-j]))
    if 2**(a+1)-Ae[-j] in Ae[:-j]:
        s+=1
        Ae.remove(2**(a+1)-Ae[-j])
        j+=1
    else:
        j+=1
print(s+t)

Submission status: Runtime Error

Solution code:
import numpy as np
import bisect

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

A = np.array(A)
AA = np.array(A)

beki = [2]
while beki[-1]*2 <= 1000000:
    beki.append(beki[-1]*2)

beki = beki[::-1]
ans = 0
ind = 0
for b in beki:
    ind = 0
    for i in range(N-ans*2):

        if len(AA) <= 1:
            break

        tar = b - AA[ind]

        ind1 = bisect.bisect_left(AA,AA[ind],0,len(AA))
        ind2 = bisect.bisect_left(AA,tar,ind1,len(AA))

        if len(AA) > ind2 and AA[ind2] == tar:
            AA = np.delete(AA,ind1)
            AA = np.delete(AA,ind2-1)
            ans += 1

        else:
            ind += 1

        if len(AA) <= 1:
            break
    if len(AA) <= 1:
        break

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N = int(input())
A = list(map(int, input().split()))
#A.sort(reverse=True)

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    pair=2**b - A[i]
    if A.count(pair) >0:
      A[i] = -1
      A[A.index(pair)] = -1
      pairCounter+=1
      break

print(pairCounter)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import copy
import collections

N = int(input())
A = []
for a in input().split():
	A.append(int(a))

A.sort()
A = A[::-1]

collections_A = collections.Counter(A)
#print(collections_A)

max_pair = A[0] + A[1]
min_pair = A[N-2] + A[N-1]

beki_list = []

for i in range(1,32):
	beki = 2**i
	if beki >= min_pair and beki <= max_pair:
		beki_list.append(beki)

beki_list = beki_list[::-1]

count = 0

Acopy = copy.copy(A)
removed_num = []
target_num = 0
a_mem = 0
for target_beki in beki_list:
	for a in A:
		try:
			collections_A[a]
		except KeyError:
			break
		if a >= target_beki/2:
			target_num = target_beki - a
			exist_or_not = (target_num in Acopy)
			if exist_or_not and target_num == a:
				num_of_num = collections_A[target_num]
				#Acopy2 = copy.copy(Acopy)
				#Acopy2.remove(target_num)
				#exist_or_not = (target_num in Acopy2)
				if num_of_num >= 2:
					exist_or_not = True
				else:
					exist_or_not = False
			if exist_or_not:
				Acopy.remove(a)
				Acopy.remove(target_num)
				collections_A.update({a: collections_A[a] - 1})
				collections_A.update({target_num: collections_A[target_num] - 1})
				removed_num += [a, target_num]
				count += 1

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
import bisect

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

A = np.array(A)
AA = np.array(A)

beki = [2]
while beki[-1]*2 <= A[-1]+A[-2]:
    beki.append(beki[-1]*2)

beki = beki[::-1]
ans = 0
ind = 0
for b in beki:
    ind = 0
    for i in range(N-ans*2):

        if len(AA) <= 1:
            break

        tar = b - AA[ind]

        ind1 = bisect.bisect_left(AA,AA[ind],0,len(AA))
        ind2 = bisect.bisect_left(AA,tar,ind1,len(AA))

        if AA[ind2] == tar:
            AA = np.delete(AA,ind1)
            AA = np.delete(AA,ind2-1)
            ans += 1

        else:
            ind += 1

        if len(AA) <= 1:
            break
    if len(AA) <= 1:
        break

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
# A = [3, 11, 14, 5, 13]

A = np.array(A)
ax, ay = np.meshgrid(A, A)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

"""
pairCounter=0
for i in range(N):
  for j in range(N -i -1):
    if A[j+i +1] < 1:
      continue
    if A[i] < 1:
      break
    wa = A[i] + A[j+i +1]
    for b in range(9):
      if 2**b & wa == wa:
        A[i]=-1
        A[j+i +1]=-1
        pairCounter+=1
        break
"""

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    pair=2**b - A[i]
    if A.count(pair) >0:
      A[i] = -1
      A[A.index(pair)] = -1
      pairCounter+=1
      break

print(pairCounter)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
# A = [3, 11, 14, 5, 13]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
powers = [int(2**i) for i in range(1, 33)]

# tmp_bool = np.array([False]*len(A))
# for p in powers:
#     col_bool = np.any(triAA == p, axis=1)
#     triAA[0, col_bool] = 0
#     tmp_bool = np.logical_or(tmp_bool, col_bool)
# print(tmp_bool.sum())

tot = 0
for p in powers:
    tot += (triAA == p).sum()
print(tot)

Submission status: Runtime Error

Solution code:
import numpy as np
import bisect

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

A = np.array(A)
AA = np.array(A)

beki = [2]
while beki[-1]*2 <= A[-1]+A[-2]:
    beki.append(beki[-1]*2)

beki = beki[::-1]
ans = 0
ind = 0
for b in beki:
    for i in range(N):

        if len(AA) <= 1:
            break

        tar = b - AA[ind]

        ind1 = bisect.bisect_left(AA,AA[ind],0,len(AA))
        ind2 = bisect.bisect_left(AA,tar,ind1,len(AA))

        if AA[ind2] == tar:
            AA = np.delete(AA,ind1)
            AA = np.delete(AA,ind2-1)
            ans += 1

        else:
            ind += 1

        if len(AA) <= 1:
            break

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
# A = [3, 11, 14, 5, 13]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
# print(triAA.dtype)
# triAA = triAA.ravel()
# print(triAA)
# np.where(triAA)
tmp_bool = np.array([False]*len(A))
# print(row_bool)
powers = [int(2**i) for i in range(1, 33)]
for p in powers:
    # print(p)
    col_bool = np.any(triAA == p, axis=1)
    triAA[0, col_bool] = 0
    tmp_bool = np.logical_or(tmp_bool, col_bool)
    # total += np.any(triAA == p, axis=0).sum()
print(tmp_bool.sum())
# print(triAA in (1, 2))

Submission status: Runtime Error

Solution code:
import numpy as np

def search_two(A,want,i,j):
    if j<i:
        return -1
    if A[(i+j)//2]==want:
        return (i+j)//2
    elif A[(i+j)//2]>want:
        return search_two(A,want,(i+j)//2+1,j)
    elif A[(i+j)//2]>want:
        return search_two(A,want,i,(i+j)//2-1)

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

A.sort()

A=A[::-1]
count=0
M=N
i=0
while i<M:
    want=2**(int(np.log2(A[i]))+1) - A[i]
    j = search_two(A,want,i+1,M-1)
    if j!=-1:
        A.pop(j)
        M-=1
        count+=1
    i+=1    
print(count)

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
a = list(map(int,input().split()))
a.sort()

c = 0
t = 2**30
while t >= 2:
  j = bisect.bisect_left(a, t//2)
  if j == len(a):
    t = t//2
    continue
  while j < len(a):
    x = a.pop(j)
    i = bisect.bisect_left(a, t-x)
    if i < len(a):
      if a[i] == t-x:
        c += 1
        a.pop(i)
        j -= 1
        continue
    j += 1
print(c)

Submission status: Runtime Error

Solution code:
def bins(a, x):
    left = 0
    right = len(a) - 1
    res = -1e10
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            res = mid
            break
        elif a[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    return res

N = int(input())
A = [int(a) for a in input().split()]

pow2s = [2 ** i for i in range(30)]
A.sort()
cand = [[] for _ in range(int(2e5) + 1)]
for i, a in enumerate(A):
    tmp = [pow2 - a for pow2 in pow2s]
    for t in tmp:
        index = bins(A[i:], t) + i
        if index > 0:
            cand[a].append(t)

res = 0
for x in cand:
    for y in x:
        if cand[y] == []:
            res += 1
            break
print(res)

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxa=max(a)
m=len(bin(maxa))-2
x=[[] for _ in range(m)]
for i in range(n):
    x[len(bin(a[i]))-3].append(a[i])
#print(x)
y=[]
for i in range(m):
    ti=m-1-i
    tx=[]
    for j in range(len(x[ti])):
        tj=len(x[ti])-1-j
        tx=2**(len(bin(x[ti][tj]))-2)-x[ti][tj]
        tk=len(bin(tx))-3
        judge=True
        #print(tx,x[ti][tj])
        if x[ti][tj]==tx:
            y.append(tx)
            continue
        
        tz=bisect.bisect_left(x[tk],tx)
        if tx==x[tk][tz]:
            del x[tk][tz]
        else:
            y.append(x[ti][tj])
y.sort()
ans=0
z=[2**i for i in range(32)]
y.append(0)
#print(y)
j=False
for i in range(len(y)-1):
    if y[i] in z:
        if y[i]==y[i+1]:
            if j:
                j=False
            else:
                j=True
        elif j is False:
            ans+=1
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Runtime Error

Solution code:
def bins(a, x):
    left = 0
    right = len(a) - 1
    res = -1
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            res = mid
            break
        elif a[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    return res

N = int(input())
A = [int(a) for a in input().split()]

pow2s = [2 ** i for i in range(30)]
A.sort()
cand = [[] for _ in range(int(2e5))]
for i, a in enumerate(A):
    tmp = [pow2 - a for pow2 in pow2s]
    tmpa = a
    A[i] = -1e10
    for t in tmp:
        index = bins(A, t)
        if index != -1:
            cand[a].append(t)

res = 0
for i, x in enumerate(cand):
    for y in x:
        if cand[y] == []:
            res += 1
            break
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
# A = [3, 11, 14, 5, 13]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
# print(triAA.dtype)
# triAA = triAA.ravel()
# print(triAA)
# np.where(triAA)
row_bool = np.array([False]*len(A))
# print(row_bool)
powers = [int(2**i) for i in range(1, 33)]
for p in powers:
    # print(row_bool)
    row_bool = np.logical_or(row_bool, np.any(triAA == p, axis=0))
    # total += np.any(triAA == p, axis=0).sum()
print(row_bool.sum())
# print(triAA in (1, 2))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import copy
N = int(input())
A = []
for a in input().split():
	A.append(int(a))

A.sort()
A = A[::-1]

max_A = A[0]
min_A = A[N-1]
max_pair = A[0] + A[1]
min_pair = A[N-2] + A[N-1]

beki_list = []

for i in range(1,32):
	beki = 2**i
	if beki >= min_pair and beki <= max_pair:
		beki_list.append(beki)

beki_list = beki_list[::-1]

count = 0

Acopy = copy.copy(A)
removed_num = []
target_num = 0
a_mem = 0
for target_beki in beki_list:
	for a in A:
		if a >= target_beki/2 and a <= target_beki - min_A:
			for r_num in removed_num:
				if a == r_num:
					break
			target_num = target_beki - a
			exist_or_not = (target_num in Acopy)
			if exist_or_not and target_num == a:
				Acopy2 = copy.copy(Acopy)
				Acopy2.remove(target_num)
				exist_or_not = (target_num in Acopy2)
			if exist_or_not:
				Acopy.remove(a)
				Acopy.remove(target_num)
				removed_num += [a, target_num]
				count += 1

print(count)

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
a = list(map(int,input().split()))
a.sort()

c = 0
t = 2**30
while t >= 2:
  if a[-1]<t//2:
    t = t//2
    continue
  while a[-1] >= t:
    a.pop(-1)
    if len(a) == 0:
      print(c)
      exit()
  i = 0
  j = len(a)-1
  while i < j:
    if a[i]+a[j] < t:
      i += 1
    elif a[i]+a[j] > t:
      j -= 1
    else:
      c += 1
      a.pop(j)
      a.pop(i)
      j -= 2
  t = t//2
print(c)

Submission status: Runtime Error

Solution code:
import bisect

n=int(input())
a=list(map(int,input().split()))

a.sort()
M=a[-1]*2

count=0
for i in range(n):
    while powers<a[i]:
        want=powers*2-a[i]
        l=bisect.bisect_left(a,want)        
        r=bisect.bisect_right(a,want)
        if l<n and a[l]==want:
            count+=(r-l)
        powers*=2

print(count)

Submission status: Runtime Error

Solution code:
import bisect
ans = 0
N = int(input())
a = list(map(int,input().split()))
b = [True for _ in range(N)]
a.sort()
digit = 40
y = 2 ** (digit+1) -1
while len(a)>1:
    if b[-1]==False:
        a.pop(-1)
        b.pop(-1)
        continue
    x = a.pop(-1)
    b.pop(-1)
    while x < 2**digit:
        digit -= 1
        y = 2 ** (digit+1) -1
    z = x^y
    z += 1
    ll =  bisect.bisect_left(a,z)
    rr =  bisect.bisect_right(a,z)
    if rr-ll>0:
        rr -= 1
        while b[rr] == False:
            rr -= 1
        if rr>=ll:
            b[rr] = False
            ans += 1           
print(ans)

Submission status: Runtime Error

Solution code:

import numpy as np
N = int(input())
A = list(map(int, input().split()))
# A = [3, 11, 14, 5, 13]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
# triAA = triAA.ravel()
# print(triAA)
# np.where(triAA)
row_bool = np.array([False]*len(A))
# print(row_bool)
powers = [int(2**i) for i in range(32)]
for p in powers:
    # print(row_bool)
    row_bool = np.logical_or(row_bool, np.any(triAA == p, axis=0))
    # total += np.any(triAA == p, axis=0).sum()
print(row_bool.sum())
# print(triAA in (1, 2))

Submission status: Runtime Error

Solution code:
from collections import Counter

beki2 = [2**i for i in range(31)]
N = int(input())
A = list(map(int, input().split()))

ct = Counter(A)
ans = 0
for i in sorted(ct.keys()):
  for j in beki2:
    k = j - i
    if i != k:
      if k in ct:
        numk = ct[k]
        m = numi if numi < numk else numk
        ans += m
        ct[i] -= m
        ct[k] -= m

for j in beki2:
  if j in ct:
    ans += ct[j] // 2

print(ans)

Submission status: Runtime Error

Solution code:

import numpy as np
N = int(input())
A = list(map(int, input().split()))
# A = [3, 11, 14, 5, 13]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
# triAA = triAA.ravel()
print(triAA)
# np.where(triAA)
row_bool = np.array([False]*len(A))
print(row_bool)
powers = [int(2**i) for i in range(32)]
for p in powers:
    # print(row_bool)
    row_bool = np.logical_or(row_bool, np.any(triAA == p, axis=0))
    # total += np.any(triAA == p, axis=0).sum()
print(row_bool.sum())
# print(triAA in (1, 2))

Submission status: Runtime Error

Solution code:

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

count = 0
for i in range(len(x)):
    for j in range(1, len(x)):
        if i+j > len(x)-1:
            break

        while True:
            print(search)
            div = search / 2
            search = div

            keisan = div * 10
            keisan = str(int(keisan))
            if keisan[-1] != '0':
                break

            if div == 1.0:
                count += 1
                break

print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import copy
N = int(input())
A = []
for a in input().split():
	A.append(int(a))

A.sort()
A = A[::-1]

max_pair = A[0] + A[1]
min_pair = A[N-2] + A[N-1]

beki_list = []

for i in range(1,32):
	beki = 2**i
	if beki >= min_pair and beki <= max_pair:
		beki_list.append(beki)

beki_list = beki_list[::-1]

count = 0

Acopy = copy.copy(A)
removed_num = []
target_num = 0
a_mem = 0
for target_beki in beki_list:
	for a in A:
		for r_num in removed_num:
			if a == r_num:
				break
		if a >= target_beki/2:
			target_num = target_beki - a
			exist_or_not = (target_num in Acopy)
			if exist_or_not and target_num == a:
				Acopy2 = copy.copy(Acopy)
				Acopy2.remove(target_num)
				exist_or_not = (target_num in Acopy2)
			if exist_or_not:
				Acopy.remove(a)
				Acopy.remove(target_num)
				removed_num += [a, target_num]
				count += 1

print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
ct=0

M=max(a)
for i in range(25):
  if 2**i>M:
    x=i
    break
L=[]
for j in range(2**x-1):
  L.append(0)

for j2 in range(n):
  L[a[j2]-1]+=1

for k in range(x,1,-1):
  l1=L[0:2**(k-1)-1]
  l2=L[2**(k-1):2**k]
  l2.reverse()
  if L[2**(k-1)-1]>=2:
    ct+=int(L[2**(k-1)-1]/2)
  for m in range(len(l1)):
    if l1[m]>=1 and l2[m]>=1:
      ct+=min(l1[m],l2[m])
      l1[m]-=min(l1[m],l2[m])
      l2[m]-=min(l1[m],l2[m])
  L=l1
ct+=int(L[0]/2)
print(ct)

Submission status: Runtime Error

Solution code:
from math import *
 
n=int(input())
arr=list(map(int,input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    val2=ceil(log2(arr[i]))
    for j in range(33,val2-1,-1):
        xd=2**j
        if(xd!=2*arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    dict1[arr[i]]-=1
                    break
        
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=2
                break
print(ans)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
A = [int(i) for i in input().split()]

ans = 0
even = []
odd = []

for i in range(N):
    if A[i] % 2 == 0:
        even.append(A[i])
    else:
        odd.append(A[i])

even = sorted(even)
odd = sorted(odd)

even2 = copy.deepcopy(even)
odd2 = copy.deepcopy(odd)

for i in range(len(even)):
    for j in reversed(range((len(even2)))):
        if i >= j:
            break
        num = even[i] + even2[j]
            ans += 1
            del even2[j]
            break

for i in range(len(odd)):
    for j in reversed(range((len(odd2)))):
        if i >= j:
            break
        num = odd[i] + odd2[j]
        if not (num & (num - 1)):
            ans += 1
            del odd2[j]
            break

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())

A=[0 for i in range(10**5+10)]

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

for i in range(len(a)):
    A[a[i]]+=1
    
ans=0

for j in range(len(A)):
    if A[len(A)-1-j]==0:
        pass
    else:
        t=0
        while (len(A)-j-1)>(2**t):
            t+=1
        if A[(2**t)-(len(A)-1-j)]>0:
            ans+=min(A[len(A)-1-j],A[2**t-(len(A)-1-j)])
            A[2**t-(len(A)-1-j)]-=min(A[len(A)-1-j],A[2**t-(len(A)-1-j)])
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
m=len(bin(maxa))-2
x=[[] for _ in range(m)]
for i in range(n):
    x[len(bin(a[i]))-3].append(a[i])
#print(x)
y=[]
for i in range(m):
    ti=m-1-i
    tx=[]
    for j in range(len(x[ti])):
        tj=len(x[ti])-1-j
        tx=2**(len(bin(x[ti][tj]))-2)-x[ti][tj]
        tk=len(bin(tx))-3
        judge=True
        #print(tx,x[ti][tj])
        if x[ti][tj]==tx:
            y.append(tx)
            continue
        for k in range(len(x[tk])):
            if x[tk][k]==tx:
                judge=False
                del x[tk][k]
                break
        if judge:
            y.append(x[ti][tj])
y.sort()
ans=0
z=[2**i for i in range(32)]
y.append(0)
#print(y)
j=False
for i in range(len(y)-1):
    if y[i] in z:
        if y[i]==y[i+1]:
            if j:
                j=False
            else:
                j=True
        elif j is False:
            ans+=1
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Runtime Error

Solution code:

import numpy as np
N = int(input())
A = list(map(int, input().split()))
# A = [1, 2, 3]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
# triAA = triAA.ravel()
# print(triAA)
# print(triAA)
# np.where(triAA)
total = 0
powers = [int(2**i) for i in range(32)]
for p in powers:
    total += np.where(triAA == p, True, False).sum()
print(total)
# print(triAA in (1, 2))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(str, input().split()))
# A = [1, 2, 3]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
# triAA = triAA.ravel()
# print(triAA)
# print(triAA)
# np.where(triAA)
total = 0
powers = [int(2**i) for i in range(32)]
for p in powers:
    total += np.where(triAA == p, True, False).sum()
print(total)
# print(triAA in (1, 2))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
ct=0

M=max(a)
for i in range(25):
  if 2**i>M:
    x=i
    break
L=[]
for j in range(2**x-1):
  L.append(0)

for j2 in range(n):
  L[a[j2]-1]+=1

for k in range(x,1,-1):
  l1=L[0:2**(k-1)-1]
  l2=L[2**(k-1):2**k]
  l2.reverse()
  if L[2**(k-1)-1]%2==0:
    ct+=int(L[2**(k-1)-1]/2)
  for m in range(len(l1)):
    if l1[m]==l2[m]:
      ct+=l1[m]
      l1[m]=0
      l2[m]=0
  L=l1
ct+=int(L[0]/2)
print(ct)

Submission status: Runtime Error

Solution code:
from math import *

n=int(raw_input())
arr=list(map(int,raw_input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    val2=ceil(log(arr[i]))
    for j in range(33,val2-1,-1):
        xd=2**j
        if(xd!=2*arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    break
        
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=1
                break
    dict1[arr[i]]-=1
print(ans)

Submission status: Runtime Error

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

from collections import Counter
counter=Counter(A)

LIST=sorted(list(counter.keys()),reverse=True)

L=len(LIST)

i=0
ANS=0
while i<L:
    #print(i,counter,ANS)
    if counter[LIST[i]]==0:
        i+=1
    else:
        for k in range(33):
            if 2**k<=LIST[i]:
                continue
            if 2**k>LIST[i]*2:
                i+=1
                break
            if counter.get(2**k-LIST[i],0)>0:
                if LIST[i]!=2**k-LIST[i]:                        
                    counter[LIST[i]]-=1
                    counter[2**k-LIST[i]]-=1
                    ANS+=1
                else:
                    if counter[LIST[i]]>=2:
                        counter[list[i]]-=2
                        ANS+=1
                    

print(ANS)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N = int(input())
A = [int(i) for i in input().split()]
A.sort()
ans = 0
bek = []
for i in range(32):
    bek.append(2**i)
    
a = A[:]
memo = 0
for i in range(N-1):
    if len(A) >= 2:
        a = A[:]
        num = A[i+ memo]
        del a[bisect_left(a, num)]
    
        for j in [k-i for k in bek]:
            if j in a:
                ans += 1
                memo -= 2
                A.remove(j)
                A.remove(num)
                break
            
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
balls = list(map(int, input().split()))
balls.sort()

min_max = balls[0] + balls[-1]
two_power = 2
while two_power < min_max:
	two_power *= 2

default_two_power = two_power

counter = 0
for element in balls:
	two_power = default_two_power
	while two_power != 1:
		tmp = two_power - balls[0]
		if tmp < 1:
			two_power /= 2
		elif tmp in balls:
			balls.pop(0)
			balls.remove(tmp)
			counter += 1
			break;
		else:
			two_power /= 2
	else:
		balls.pop(0)


print(counter)

Submission status: Runtime Error

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict
import bisect

sys.setrecursionlimit(3000)

def find(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        # print("### T: i={}, x={}".format(i, x))
        return i
    else:
        # print("### F: i={}, x={}".format(i, x))
        return -1


N = int(input())
A = [int(x) for x in input().split()]
B = []
b = 1
while (b <= 10 ** 10):
    B.append(b)
    b *= 2
A = sorted(A)
P = set()
for i in range(len(A)):
    a = A[i]
    for b in B:
        if b - a >= 0:
            j = find(A, b - a)
            if j >= 0:
                if j > i:
                    P.add((i, j))
                # print("# A[i]:{}, A[j]:{}, i:{}, j:{}".format(A[i], A[j], i, j))

# print(P)
# print(len(P))

L = list(P)


def f(idx, used=set()):
    if idx == len(L) - 1:
        return 1

    n0 = L[idx][0]
    n1 = L[idx][1]
    r1 = 0
    if (not n0 in used) and (not n1 in used):
        used.add(n0)
        used.add(n1)
        r1 = f(idx + 1, used) + 1
        used.remove(n0)
        used.remove(n1)

    r2 = f(idx + 1, used)

    return max(r1, r2)

r = f(0)

print(r)

Submission status: Runtime Error

Solution code:
def f(N, A):
    A.sort()
    A = [a for a in map(bin, A)]
    res = 0
    for i, a in enumerate(A[:-1]):
        tmpa = str(bin(~int(a, 0)))[3:]
        for b in A[i+1:]:
            tmpb = b[-len(a)+2:]
            if tmpb == tmpa:
                res += 1
    return res
 
N = int(input()))
A = [int(a) for a in input.split()]
print(f(N, A), flush=True)

Submission status: Runtime Error

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

A.sort()
m = 2 ** 30
used = set()
ans = 0

def search(ok, ng, n):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if A[mid] < n or (A[mid] == n and mid in used):
        return search(mid, ng, n)
    else:
        return search(ok, mid, n)

for i in range(30):
    m //= 2
    for j in range(n):
        if j in used or A[j] >= m:
            continue
        a = search(-1, n, m - A[j]) + 1
        if a >= n:
            continue
        if A[a] == m - A[j]:
            if a == j:
                if not A[a+1] == A[j]:
                    continue
                a += 1
            used.add(a)
            used.add(j)
            ans += 1

ans2 = 0
used = set()

for i in range(30):
    m *= 2
    for j in range(n):
        if j in used or A[j] >= m:
            continue
        a = search(-1, n, m - A[j]) + 1
        if a >= n:
            continue
        if A[a] == m - A[j]:
            if a == j:
                if not A[a+1] == A[j]:
                    continue
                a += 1
            used.add(a)
            used.add(j)
            ans2 += 1

print(max(ans, ans2))

Submission status: Runtime Error

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict
import bisect


def find(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        # print("### T: i={}, x={}".format(i, x))
        return i
    else:
        # print("### F: i={}, x={}".format(i, x))
        return -1


N = int(input())
A = [int(x) for x in input().split()]
B = []
b = 1
while (b <= 10 ** 10):
    B.append(b)
    b *= 2
A = sorted(A)
P = set()
for i in range(len(A)):
    a = A[i]
    for b in B:
        if b - a >= 0:
            j = find(A, b - a)
            if j >= 0:
                if j > i:
                    P.add((i, j))
                # print("# A[i]:{}, A[j]:{}, i:{}, j:{}".format(A[i], A[j], i, j))

# print(P)
# print(len(P))

L = list(P)


def f(idx, used=set()):
    if idx == len(L) - 1:
        return 1

    n0 = L[idx][0]
    n1 = L[idx][1]
    r1 = 0
    if (not n0 in used) and (not n1 in used):
        used.add(n0)
        used.add(n1)
        r1 = f(idx + 1, used) + 1
        used.remove(n0)
        used.remove(n1)

    r2 = f(idx + 1, used)

    return max(r1, r2)

r = f(0)

print(r)

Submission status: Runtime Error

Solution code:
import bisect

N=int(input())

E=[]
O=[]

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

for i in range(len(a)):
    if a[i]%2==0:
        E.append(a[i])
    else:
        O.append(a[i])
        
E.sort()
O.sort()

ans=0
for e in range(len(E)):
    t=0
    while E[len(E)-1-e]>2**t:
       t=t+1
       #print(t)
    if E[bisect.bisect_left(E,2**t-E[len(E)-1-e])]+E[len(E)-1-e]==2**t:
        ans+=1
        del E[bisect.bisect_left(E,2**t-E[len(E)-1-e])]
        
for o in range(len(O)):
    t=0
    while O[len(O)-1-o]>2**t:
       t=t+1
       #print(t)
    if O[bisect.bisect_left(O,2**t-O[len(O)-1-o])]+O[len(O)-1-o]==2**t:
        ans+=1
        del O[bisect.bisect_left(O,2**t-O[len(O)-1-o])]
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
a = list(map(int,input().split()))
a.sort()

c = 0
for k in range(0,30)[::-1]:
  if a[-1]<2**k:
    continue
  i = 0
  j = len(a)-1
  while i < j:
    if a[i]+a[j] < 2**(k+1):
      i += 1
    elif a[i]+a[j] > 2**(k+1):
      j -= 1
    else:
      c += 1
      a.pop(j)
      a.pop(i)
      j -= 1
print(c)