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: Time Limit Exceeded

Solution code:
import math
from collections import deque
N=int(input())
a=list(map(int,input().split()))
dq=deque(sorted(a))
ans=0
while len(dq)>1:#1になった時点で終わり。
    head=dq.pop()
    for n in range(head):
        if head<=2**n:
            t=n
            break
    if 2**t==head:
    #これは、2,4,8とか2のべき乗だけが引っかかる条件
    #このforだと、tは-1しなくていい。
        second=dq.pop()
        if head==second:
        #2のべきでも、きちんと2個存在するならおｋ
            ans+=1
        else:
            dq.append(second)
    else:
        #inが遅すぎるかもしれない。ちょっと高速化
        #上で被りうる奴は排除できている。
        for j in range(1,len(dq)+1):
            if 2**t-head==dq[-j]:
                ans+=1
                dq.remove(dq[-j])
                break
            elif 2**t-head<dq[-j]:
                continue
            else:
                break
                #可能性なしがわかったらすぐ切る！！
print(ans)
#removeって探して削除なので遅い。popに変更してみよう
#forにしたことでインデックスも取得できるので。

#加えた工夫
# dequeにしてremoveをO(1)にした
# log2の計算をforにした

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
a=list(map(int,input().split()))
a_=sorted(a,key=lambda x:-x)
ans=0
while len(a_)>1:#1になった時点で終わり。
    x,y=0,0
    t=int(math.log2(a_[0]))+1
    if 2**(t-1)==a_[0]:
    #これは、2,4,8とか2のべき乗だけが引っかかる条件
        if a_[0]==a_[1]:
        #2のべきでも、きちんと2個存在するならおｋ
            a_.remove(a_[0])
            a_.remove(a_[0])
            ans+=1
        else:
            a_.remove(a_[0])
    else:
        x+=a_[0]
        y+=2**t-a_[0]
        if y in a_:
        #上で被りうる奴は排除できている。
            ans+=1
            a_.remove(x)
            a_.remove(y)
        else:
            a_.remove(a_[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
class BST:
    def __init__(self,number_list):
        self.root=None
        for node in number_list:
            self.insert(node)
    def insert(self,data):
        n=self.root
        if n is None:
            self.root=Node(data)
            return
        else:
            while True:#これ抜けてた。やばい。
                entry=n.data
                if data<entry:
                    if n.left is None:
                        n.left=Node(data)
                        return
                    n=n.left
                elif data>entry:
                    if n.right is None:
                        n.right=Node(data)
                        return
                    n=n.right
                else:
                    n.data=data
                    return
    def search(self,target):
        n = self.root
        if n is None:
            return None
        else:#深さ優先探索
            lst = []
            lst.append(n)
            while len(lst) > 0:
                node = lst.pop()
                if node.data == target:
                    return True
                if node.right is not None:
                    lst.append(node.right)
                if node.left is not None:
                    lst.append(node.left)
            return False
        
import math
N=int(input())
a=list(map(int,input().split()))
t_max=int(math.log2(max(a)*2)+1)
ans=0
for t in range(t_max,0,-1):
    i=0
    while i<len(a):
    #forだとout of rangeしてしまうので。
        x,y=0,0
        bst=BST(a)#二分木も更新しないと。
        if bst.search(2**t-a[i]):
            if a[i]!=2**t-a[i]:
                #同じだったらNG
                ans+=1
                x+=a[i]
                y+=2**t-a[i]
                #IDを共有すると、インデックスがずれる。
                a.remove(x)
                a.remove(y)
        else:
            i+=1 #ペアが見つからなかったときだけ進めばいい。
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        if x==a[i] and a.count(x)>1:
            ans+=1
            a[i]=None
            a[a.index(x)]=None
        elif x in a and x!=a[i]:
            ans+=1
            a[a.index(x)]=None
            a[i]=None
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort()
for _ in range(n):
    if len(a)<2:
        break
    else:
        bi=format(a[-1], 'b')
        x=2**len(bi)-a[-1]
        if x==a[-1] and a.count(x)>1:
            ans+=1
            a.remove(x)
            a.remove(x)
            continue
        elif x in a and x!=a[-1]:
            ans+=1
            a.remove(x)
        a.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for _ in range(n):
    if len(a)<2:
        break
    else:
        bi=format(a[0], 'b')
        x=2**len(bi)-a[0]
        if x==a[0] and a.count(x)>1:
            ans+=1
            a.remove(x)
            a.remove(x)
            continue
        elif x in a and x!=a[0]:
            ans+=1
            a.remove(x)
        a.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as b
n=int(input())
a=sorted(list(map(int,input().split())))
s=n-1
c=0
while s>0:
    t=2**(len(bin(a[s]))-2)
    if t-a[s] in a:
        d=b(a,t-a[s])
        if d<s and a[d]==t-a[s]:
            a.pop(d)
            c+=1
            s-=1
    s-=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as b
n=int(input())
a=sorted(list(map(int,input().split())))
s=n-1
c=0
while s>0:
    t=2**(len(bin(a[s]))-2)
    d=b(a,t-a[s])
    if d<s and a[d]==t-a[s]:
        a.pop(d)
        c+=1
        s-=2
    else:
        s-=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
As = list(map(int, input().split()))
As.sort()
r = 0
while As:
  A = As.pop()
  t = A.bit_length()
  B = (1<<t)-A
  i = bisect.bisect_left(As, B)
  if i < len(As) and As[i] == B:
    As.pop(i)
    r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

maxPow = (1 << (max(A) * 2).bit_length())
cntA = Counter(A)

ans = 0
while maxPow > 0:
    for a in A:
        if maxPow - a == a:
            if cntA[a] >= 2:
                ans += cntA[a] // 2
                cntA[a] %= 2
        elif cntA[a] > 0 and cntA[maxPow - a] > 0:
            ans += 1
            cntA[a] -= 1
            cntA[maxPow - a] -= 1
    maxPow //= 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
alist = list(sorted(d.keys(), reverse = True))
amax = alist[0]
t = 1
power_of_two = []
while t < 2 * amax:
  t *= 2
  power_of_two.append(t)
result = 0
for a in alist:
  if d[a] == 0:
    continue
  t = power_of_two[bisect_right(power_of_two, a)] - a
  while True:
    if t not in d or d[t] == 0:
      break
    if a != t:
      i = min(d[a], d[t])
    else:
      i = d[a] // 2
    result += i
    d[a] -= i
    d[t] -= i
    if d[a] == 0:
      break
print(result)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
t = 1
valids = []
while t < 2 * 10 ** 9:
  t *= 2
  valids.append(t)
result = 0
while True:
  prev = result
  keys = list(d.keys())
  keys.sort(reverse = True)
  for x in keys:
    t = valids[bisect_right(valids, x)] - x
    if t not in d:
      continue
    if x == t and d[x] == 1:
      continue
    result += 1
    if d[x] == 1:
      del d[x]
    else:
      d[x] -= 1
    if d[t] == 1:
      del d[t]
    else:
      d[t] -= 1
    break
  if prev == result:
    break
print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

a.sort()

b = [0]*n
ans = 0

for i in range(n):
    if b[-i-1]==0:
        c = 2**(len(bin(a[-i-1]))-2)-a[-i-1]
        d = bisect.bisect_left(a,c)
        e = bisect.bisect_right(a,c)
        if a[d]==c:
            for j in range(d,e):
                if b[j]==0 and j!=n-i-1:
                    ans += 1
                    b[-i-1]=1
                    b[j]=1
                    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
dic={}
for val in arr:
  if val not in dic:
    dic[val]=1
  else:
    dic[val]+=1
ans=0
for val in arr:
  for i in range(40):
    if val<2**i:
      persuit=2**i
      break
  if persuit-val==val:
    if val in dic:
      if dic[val]>=2:
        ans+=1
        dic[val]-=2
        if dic[val]==0:
          del dic[val]
      else:
        continue
    else:
      continue
  else:
    if val in dic and persuit-val in dic:
      ans+=1
      dic[val]-=1
      if dic[val]==0:
        del dic[val]
      dic[persuit-val]-=1
      if dic[persuit-val]==0:
        del dic[persuit-val]
    else:
      continue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

alist.sort()
#print(alist)

flist=[False]*N
answer=0
for i in reversed(range(N)):
  if flist[i]:
    continue
  
  p1=alist[i]
  p2=2**math.ceil(math.log(p1+1,2))-p1
  #print(p1,p2)
  
  index1 = bisect.bisect_left(alist,p2,0,i+1)  
  index2 = bisect.bisect_right(alist,p2,index1,i+1)  
  #print(index1,index2)
  for j in range(index1,index2):
    if j != i and not flist[j]:
      flist[i]=True
      flist[j]=True
      answer+=1
      break
  
#print(flist)    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

alist.sort()
#print(alist)

flist=[False]*N
answer=0
for i in reversed(range(N)):
  if flist[i]:
    continue
  
  p1=alist[i]
  p2=2**math.ceil(math.log(p1+1,2))-p1
  #print(p1,p2)
  
  index1 = bisect.bisect_left(alist,p2)  
  index2 = bisect.bisect_right(alist,p2)  
  #print(index1,index2)
  for j in range(index1,index2):
    if j != i and not flist[j]:
      flist[i]=True
      flist[j]=True
      answer+=1
      break
  
#print(flist)    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

alist.sort()
#print(alist)

flist=[False]*N
answer=0
for i in reversed(range(N)):
  if flist[i]:
    continue
  
  p1=alist[i]
  p2=2**math.ceil(math.log(p1+1,2))-p1
  #print(p1,p2)
  
  index1 = bisect.bisect_left(alist,p2)  
  index2 = bisect.bisect_right(alist,p2)  
  #print(index1,index2)
  for j in range(index1,index2):
    if j != i and not flist[j]:
      flist[i]=True
      flist[j]=True
      answer+=1
      break
  
#print(flist)    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

alist.sort()
#print(alist)

answer=0
while(True):
  if len(alist) <= 1:
    break
  
  p1=alist.pop()
  p2=2**math.ceil(math.log(p1+1,2))-p1
  
  index1 = bisect.bisect_left(alist,p2)  
  if index1 != bisect.bisect_right(alist,p2):
    alist.pop(index1)
    answer+=1
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
a = sorted(list(map(int,input().split())))
k = 0
while len(a) >= 2:
  m = a.pop(-1)
  v = 1
  while v <= m:
    v *= 2
  r = v-m
  i = bisect.bisect_left(a,r)
  if i < len(a) and a[i] == r:
    a.pop(i)
    k += 1
print(k)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N - 1, 0, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A, comp, 0, i - 1)
        while True:
            if A[j] == comp:
                if used[j] == 0:
                    ans += 1
                    used[j] = 1
                    break
                else:
                    if j + 1 < i:
                        j += 1
                    else:
                        break
            else:
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N - 1, 0, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log2(A_i + 1)) - A_i
        j = bisect.bisect_left(A, comp, 0, i - 1)
        while True:
            if A[j] == comp:
                if used[j] == 0:
                    ans += 1
                    used[j] = 1
                    break
                else:
                    if j + 1 < i:
                        j += 1
                    else:
                        break
            else:
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                p = min(d[pow2[k] - a[i]], d[a[i]])
                num += p
                d[pow2[k] - a[i]] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                p = min(d[pow2[k] - a[i]], d[a[i]])
                num += p
                d[pow2[k] - a[i]] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    for k in range(30, -1, -1):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                p = min(d[pow2[k] - a[i]], d[a[i]])
                num += p
                d[pow2[k] - a[i]] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(61):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    for k in range(60, -1, -1):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                num += 1
                d[pow2[k] - a[i]] -= 1
                d[a[i]] -= 1
                break
        else:
            if d[a[i]] >= 2:
                num += 1
                d[a[i]] -= 2
                break
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(61):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    for k in range(60):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                num += 1
                d[pow2[k] - a[i]] -= 1
                d[a[i]] -= 1
                break
        else:
            if d[a[i]] >= 2:
                num += 1
                d[a[i]] -= 2
                break
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [2 ** i for i in range(61)]
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    for k in range(60):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                num += 1
                d[pow2[k] - a[i]] -= 1
                d[a[i]] -= 1
                break
        else:
            if d[a[i]] >= 2:
                num += 1
                d[a[i]] -= 2
                break
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [2 ** i for i in range(61)]
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    for k in range(60):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                num += 1
                d[pow2[k] - a[i]] -= 1
                d[a[i]] -= 1
        else:
            if d[a[i]] >= 2:
                num += 1
                d[a[i]] -= 2
print(num)

Submission status: Time Limit Exceeded

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

from itertools import permutations

ans = 0

for x in permutations(a):
    cnt = 0
    for i in range(n//2):
        y = sum(x[2*i:2*i+2])
        if y&(y-1)==0:
            cnt += 1
    if cnt > ans:
        ans = cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)

ans = 0
for item in a[::-1]:
    if ca[item] == 0:
        continue
    for i in range(31, 0, -1):
        inv = (1 << i) - item
        if inv < 0:
            continue
        if ca[inv] > 0 and item != inv:
            ans += 1 
            ca[inv] -=1
            ca[item] -=1
            break
        if ca[inv] > 1 and item == inv:
            ans += 1 
            ca[inv] -= 2
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
A=[int(i) for i in input().split()]
A.sort(reverse=True)
B=[]
for a in A:
  B.append(a)
count=0
for i in range(n):
  cur=A[i]
  if cur in B:
    B=B[1:]
    k=int(math.log2(cur))+1
    pair=2**k-cur
    if pair in B:
      B.remove(pair)
      count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
A=[int(i) for i in input().split()]
B=[]
for a in A:
  B.append(a)
A.sort(reverse=True)
count=0
for i in range(n):
  cur=A[i]
  if cur in B:
    B.remove(cur)
    k=int(math.log2(cur))+1
    pair=2**k-cur
    if pair in B:
      B.remove(pair)
      count+=1
print(count)

Submission status: Time Limit Exceeded

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

from bisect import bisect_left
T = 30

def index(a, x):
	'Locate the leftmost value exactly equal to x'
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return None

cnt = 0

while len(A)>0:
	a = A.pop()
	for t in range(T,0,-1):
		if 2**t<a:
			break
		elif a<2**(t-1):
			continue
		else:
			b = 2**t-a
			ib = index(A, b)
			if ib!=None:
				del A[ib]
				cnt += 1
			else:
				continue
		
print(cnt)

Submission status: Time Limit Exceeded

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

from bisect import bisect_left
T = 30

def index(a, x):
	'Locate the leftmost value exactly equal to x'
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return None

cnt = 0

while len(A)>0:
	a = A.pop()
	for t in range(T,0,-1):
		if 2**t<a:
			break
		else:
			b = 2**t-a
			ib = index(A, b)
			if ib!=None:
				del A[ib]
				cnt += 1
			else:
				continue
		
print(cnt)

Submission status: Time Limit Exceeded

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

from bisect import bisect_left
T = 30

def index(a, x):
	'Locate the leftmost value exactly equal to x'
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return None

cnt = 0

while len(A)>0:
	a = A.pop()
	for t in range(T+1):
		if 2**t<a:
			continue
		else:
			b = 2**t-a
			ib = index(A, b)
			if ib!=None:
				del A[ib]
				cnt += 1
			else:
				continue
		
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
tmp = 1
beki = []
while tmp < 2*10**9:
	tmp *= 2
	beki.append(tmp)

ans = 0
i = 0
while i < len(A)-1:
	j = i+1
	while j < len(A):
		# print(i, j, len(A), A[i], A[j])
		if A[i]+A[j] in beki:
			ans += 1
			A.pop(j)
			i += 1
			j = i+1
		else:
			j += 1
	i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
tmp = 1
beki = []
while tmp < 2*10**9:
	tmp *= 2
	beki.append(tmp)

ans = 0
for i in range(N):
	for j in range(i+1, N):
		if A[i]+A[j] in beki:
			ans += 1
			A[j] = 10**10
			break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  x=reversed_num(number.pop())+1
  if len(number)==0:
    break
  y=bisect.bisect_left(number,x)
  if x>number[-1]:
    y-=1
  if number[y] ==x:
    number.pop(y)
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  x=reversed_num(number[-1])+1
  number.pop()
  if x in number:
    number.remove(x)
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  if reversed_num(number[-1])+1 in number and number[-1]!=reversed_num(number[-1])+1:
    number.remove(reversed_num(number[-1])+1)
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  x=reversed_num(number.pop())+1
  if x in number:
    number.remove(x)
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def reversed_num(num):
    num_len=len(bin(num))-2
    f= 2**num_len-1
    return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
    x= reversed_num(number.pop(-1))+1
    if x in number:
        number.remove(x)
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A = sorted(A, reverse=True)
    maxA = A[0]
    cntA = [0 for i in range(maxA+1)]
    for a in A:
        cntA[a] += 1

    ans = 0
    ones = (1 << 31) - 1
    for a in A:
        if cntA[a] == 0:
            continue
        cntA[a] -= 1
        #print('a =',a)
        b = (1 << a.bit_length()) - a
        if cntA[b] > 0:
            cntA[b] -= 1
            ans += 1
    return ans

print(solve())

#  1  1  7   9
#     3  5   11
#        13
#     15
#  2  6  10
#     14
#  4  4  12
#
#  8

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A = sorted(A, reverse=True)
    maxA = A[0]
    cntA = [0 for i in range(maxA+1)]
    for a in A:
        cntA[a] += 1

    ans = 0
    ones = (1 << 31) - 1
    for a in A:
        if cntA[a] == 0:
            continue
        cntA[a] -= 1
        #print('a =',a)
        while True:
            b = (ones ^ a) + 1
            #print('b =',b)
            if b <= a:
                break
            ones >>= 1
            if ones == 0:
                return ans
        if cntA[b] > 0:
            cntA[b] -= 1
            ans += 1
    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

ans = 0
while len(A) > 1:
    pow2 = 1 << (len(bin(A[-1])) - 2)
    idx = bisect_left(A, pow2 - A[-1])
    if A[idx] + A[-1] == pow2 and idx != len(A) - 1:
        A.pop(idx)
        ans += 1
    A.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

ans = 0
while len(A) > 1:
    pow2 = 1 << (len(bin(A[-1])) - 2)
    idx = bisect_left(A, pow2 - A[-1])
    if A[idx] + A[-1] == pow2 and idx != len(A) - 1:
        A.pop(idx)
        ans += 1
    A.pop(-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

ans = 0
while len(A) > 1:
    pow2 = 1 << (len(bin(A[-1])) - 2)
    idx = bisect_left(A, pow2 - A[-1])
    if A[idx] + A[-1] == pow2 and idx != len(A) - 1:
        A.pop(idx)
        ans += 1
    A.pop(-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------------------
# Name:        module2
# Purpose:
#
# Author:      ysakamot
#
# Created:     15/12/2018
# Copyright:   (c) ysakamot 2018
# Licence:     <your licence>
#-------------------------------------------------------------------------------

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    A = []
    input_raw = read_func().strip().split()
    for i in range(N):
        A.append(int(input_raw[i]))

    pair_count = 0
    already_set = set([])
    for t in range(31, 0, -1):
        x = 2**t
        count_dict = {}
        for i in range(N):
            if i in already_set:
                continue
            if x - A[i] <= 0:
                continue
            if x - A[i] in count_dict and len(count_dict[x - A[i]]) > 0:
                pair_count += 1
                j = count_dict[x - A[i]].pop()
                already_set.add(i)
                already_set.add(j)
            else:
                if A[i] not in count_dict:
                    count_dict[A[i]] = [i]
                else:
                    count_dict[A[i]].append(i)

    print pair_count

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A_arr = list(map(int, input().split()))

A_arr = sorted(A_arr, reverse=True)
C_arr = Counter(A_arr)

count = 0
while len(A_arr) != 0:
    v_max = A_arr.pop(0)
    C_arr[v_max] -= 1
    v_pair = 2**v_max.bit_length() - v_max
    if C_arr[v_pair] != 0:
        A_arr.remove(v_pair)
        C_arr[v_pair] -= 1
        count += 1
    else:
        pass

print(count)

Submission status: Time Limit Exceeded

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

A_arr = sorted(A_arr, reverse=True)
two_arr = []
for i in range(1,31):
    two_arr.append(2**i)

count = 0
while len(A_arr) != 0:
    v_max = A_arr.pop(0)
    v_pair = 2**v_max.bit_length() - v_max
    if v_pair in A_arr:
        A_arr.remove(v_pair)
        count += 1
    else:
        pass

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
two = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648}
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] in two:
            a[j] = float("inf")
            ans += 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import time
import math
n=int(input())
a=input()
s=a.split(" ")
s=[int(x) for x in s]
s.sort()
count=0
for i in range(n):
    if len(s)<2:
        break
    x=s.pop(len(s)-1)
    y=2**(int(math.log(x,2))+1)-x
    low = 0
    high = len(s) - 1
    
    while low <= high:
        mid = (low + high) // 2 
        guess = s[mid]
        if guess == y:
            s.pop(mid)
            count+=1
            break
        elif guess < y:
            low = mid + 1
        elif guess > y:
            high = mid - 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import time
import math
n=int(input())
a=input()
s=a.split(" ")
s=[int(x) for x in s]
s.sort()
count=0
for i in range(n):
    if len(s)<2:
        break
    x=s.pop(len(s)-1)
    y=2**(int(math.log(x,2))+1)-x
    low = 0
    high = len(s) - 1
    
    while low <= high:
        mid = (low + high) // 2 
        guess = s[mid]
        if guess == y:
            s.pop(mid)
            count+=1
            break
        elif guess < y:
            low = mid + 1
        elif guess > y:
            high = mid - 1

print(count)