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 queue
N=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
B=[2**(len(bin(i))-2) for i in A]
R=[0 for i in range(N)]
D=dict()
for i in range(N):
    if not(A[i] in D):
        D[A[i]]=queue.Queue()
    D[A[i]].put(i)
ans=0
for i in range(N):
    if R[i]==1:
        continue
    if B[i]==2*A[i]:
        if A[i] in D:
            flag=0
            x=0;y=0
            if not(D[A[i]].empty()):
                x=D[A[i]].get()
                flag=1
            if flag==1 and not(D[A[i]].empty()):
                y=D[A[i]].get()
                flag=2
            if flag==2:
                R[x]=1
                R[y]=1
                ans+=1
    else:
        if (B[i]-A[i]) in D:
            if not(D[B[i]-A[i]].empty()):
                it=D[A[i]].get()
                j=D[B[i]-A[i]].get()
                R[i]=1
                R[j]=1
                ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil
from bisect import bisect_left, bisect_right

N = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = [True for _ in range(N)]

ans = 0
for i in list(range(N))[::-1]:
    if not b[i]: continue
    t = a[i]
    flg = False
    for j in list(range(ceil(log2(t)), int(log2(t * 2)) + 1))[::-1]:
        pair = 2 ** j - t
        left = bisect_left(a, pair)
        right = bisect_right(a, pair)
        # print(t, pair, a, b, left, right)
        if left == right:
            if left < N and left != i:
                if a[left] == pair and b[left]:
                    b[left] = False
                    b[i] = False
                    ans += 1
                    flg = True
                    break
        else:
            k = right - 1
            k = min(right - 1, N - 1)
            while k >= max(0, left):
                if a[k] == pair and b[k] and k != i:
                    b[k] = False
                    b[i] = False
                    ans += 1
                    flg = True
                    break
                k -= 1
            if flg:
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import log,floor
N = int(input())
A = list(map(int, input().split()))

# log(10**9 + 10**9)/log(2) = 30.89 < 31
#print(log(2 * 10**9) / log(2))

A.sort(reverse=True)
usedI = [0] * N
cnt = 0

for i in range(N):
  if usedI[i] == 1:
    continue
  #print(i, log(A[i]) / log(2) )
  x = floor(log(A[i]) / log(2)) + 1 #実現可能なべき上
  search_x = 2 ** x - A[i]
  l = i+1
  r = N-1
  while l <= r:
    m = (l+r)//2
    #print(l,r,m)

    if search_x < A[m]:
      l = m if l<m else m+1
    elif search_x > A[m]:
      r = m if m<r else m-1
    else:
      if usedI[m] == 0:
        cnt += 1
        usedI[i] = 1
        usedI[m] = 1
      else:
        isfound = False
        for k in range(m+1,r+1):
          if A[k] != search_x:
              break
          if usedI[k] == 1:
              continue
          isfound = True
          break
        if not isfound:
          for k in range(m-1,l-1,-1):
            if A[k] != search_x:
              break
            if usedI[k] == 1:
              continue
            isfound = True
            break
        if isfound:
          cnt += 1
          usedI[i] = 1
          usedI[k] = 1
      break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

def dfs(v,visited):
  for u in m2[v]:
    if u in visited:
      continue
    visited.add(u)
    if(n2[u]==-1 or dfs(n2[u],visited)):
      n2[u]=v
      return True
  return False

n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
kari=[]
ma=[]
m2=[]
n2=[]
vt=[]
vp=[]
visited=[]
ans=0
for i in range(n):
  kari=[]
  for j in range(20):
    for k in range(bisect.bisect_left(a,2**j-a[i]),bisect.bisect_right(a,2**j-a[i])):
      if(k==i):
        continue
      kari.append(k)
  ma.append(kari)
for i in range(n):
  kari=[]
  for j in range(n):
    if(j in ma[i]):
      kari.append(j+n)
  m2.append(kari)
for i in range(2*n):
  n2.append(-1)
print(sum(dfs(s,set())for s in range(n))//2)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A, t)
    if i >= n:
        return False

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return True
        i += 1

    return False

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        if is_in(t - a, n):
            res += 1
            break
        t >>= 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
import queue
N=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
B=[2**(len(bin(i))-2) for i in A]
R=[0 for i in range(N)]
D=dict()
for i in range(N):
    if not(A[i] in D):
        D[A[i]]=queue.Queue()
    D[A[i]].put(i)
ans=0
for i in range(N):
    if R[i]==1:
        continue
    if (B[i]-A[i]) in D:
        itmp=D[A[i]].get()
        if not(D[B[i]-A[i]].empty()):
            j=D[B[i]-A[i]].get()
            R[i]=1
            R[j]=1
            #print(i,j)
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
temp_len = int(input())
input_nums = [int(i) for i in input().split(" ")]
powers = [2**i for i in range(30)]
def powercount(nums):
    if (nums is None) or len(nums) < 2:
        return 0
    single = nums[0]
    toBePairs = [(i - single) for i in powers if (i - single) > 0]
    pairables = []
    for i in toBePairs:
        if i in nums[1:]:
            tmp = nums[1:]
            tmp.remove(i)
            pairables.append(int(powercount(tmp) + 1))
    pairables.append(powercount(nums[1:]))
    return max(pairables)
print(powercount(input_nums))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.reverse()
def beki(s):
  k = math.log2(s)
  k = int(k) + 1
  return 2**k - s
def nib(x,s):
  a = 0
  b = len(x)-1
  while a <= b:
    c = int((a+b)/2)
    y = x[c]
    if y == s:
      return c
    if y > s:
      a = c+1
    else:
      b = c-1
  return None  
i = 0
c = 0
r = len(a)
while i < r:
  p = beki(a[i]) 
  nb = nib(a[i+1:r],p)
  if nb is not None:
    del a[i+1+nb]
    c += 1
    r -= 1
  i += 1
    
print(c)

Submission status: Time Limit Exceeded

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

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.reverse()
def beki(s):
  k = math.log2(s)
  k = int(k) + 1
  return 2**k - s
def nib(x,s):
  a = 0
  b = len(x)-1
  while a <= b:
    c = int((a+b)/2)
    y = x[c]
    if y == s:
      return c
    if y > s:
      a = c+1
    else:
      b = c-1
  return None  
i = 0
c = 0
r = len(a)
while i < r:
  p = beki(a[i]) 
  q = len(a)
  nb = nib(a[i+1:q],p)
  if nb is not None:
    del a[i+1+nb]
    c += 1
    r -= 1
  i += 1
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0] * n
twins = []
now = 1
while now <= a[-1]:
    now *= 2
    twins.append(now)
for i in range(len(a) - 1, 0, -1):
    tmpa = 0
    if b[i] != 0:
        continue
    for j in range(len(twins) - 1, -1, -1):
        if twins[j] <= a[i]:
            break
        tmpa = twins[j] - a[i]
    for j in range(i - 1, -1, -1):
        if a[j] == tmpa and b[j] == 0:
            b[i] = 1
            b[j] = 1
            break
        elif a[j] < tmpa:
            break
print(b.count(1) // 2)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
a = [int(i) for i in input().split()]

a.sort(reverse=True)

count = 0
for _ in range(N):
    for y in range(1, len(a)):
        if math.log2(a[0]+a[y]) % 1 == 0:
            count += 1
            del a[y]
            break
    del a[0]
    if len(a) < 1:
        break

print(count)

Submission status: Time Limit Exceeded

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

M=max(a)
for i in range(100):
  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()
  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: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.reverse()
def beki(s):
  k = math.log2(s)
  k = int(k) + 1
  return 2**k - s
def nib(x,s):
  a = 0
  b = len(x)-1
  while a <= b:
    c = int((a+b)/2)
    y = x[c]
    if y == s:
      return c
    if y > s:
      a = c+1
    else:
      b = c-1
  return None  
i = 0
c = 0
while i < len(a):
  p = beki(a[i]) 
  q = len(a)
  nb = nib(a[i+1:q],p)
  if nb is not None:
    del a[i+1+nb]
    c += 1
  i += 1
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A, t)
    if i >= n:
        return -1

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        i = is_in(t - a, n)
        if i != -1:
            res += 1
            break
        t >>= 1

print(res)
print("")

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A, t)
    if i >= n:
        return -1

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        i = is_in(t - a, n)
        if i != -1:
            res += 1
            break
        t >>= 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil


def bisect(array, x, left_limit):
    left = left_limit
    right = N
    # print(array, x, left, right)
    while left < right:
        target = (left + right) // 2
        if array[target] == x:
            if b[target]:
                return target
            idx = target - 1
            while array[idx] == x:
                if b[idx] and idx >= left:
                    return idx
                else:
                    idx -= 1
                    if idx < left:
                        break
            idx = target + 1
            while array[idx] == x:
                if b[idx]:
                    return idx
                else:
                    idx += 1
                if idx >= right:
                    break
            return -1
        elif array[target] < x:
            right = target
        else:  # array[target] > x
            left = target + 1
    return -1


N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = [True for _ in range(N)]

ans = 0
for i in range(N):
    if not b[i]: continue
    t = a[i]
    # print(a, b)
    idx = []
    for j in list(range(ceil(log2(t)), int(log2(t * 2)) + 1))[::-1]:
        pair = 2 ** j - t
        # print(t, pair)
        res = bisect(a, pair, i + 1)
        if res != -1:
            b[res] = False
            b[i] = False
            ans += 1
            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()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A[:n], t)
    if i == n:
        return -1

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        i = is_in(t - a, n)
        if i != -1:
            res += 1
            break
        t >>= 1

print(res)

Submission status: Time Limit Exceeded

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

Solution code:
import sys

sys.setrecursionlimit(1000000000)

def powers_of_2(n):
    while True:
        if n%2 == 0:
            n = n/2
        else:
            return False
        if n == 1:
            return True

n = int(input())
a = list(map(int, input().split()))
p = [[] for _ in  range(n)]
b = [True for _ in  range(n)]

for i in range(n-1):
    for j in range(i+1, n):
        if powers_of_2(a[i]+a[j]):
            p[i].append(j)

ans = 0

def pair(_i, b):
    global ans
    _max = 0
    for i in range(_i, n-1):
        if not b[i]:
            continue
        if len(p[i]) == 1:
            ans += 1
            p[i] = []
            b[i] = False
        elif p[i] != []:
            num = 0
            for j in p[i]:
                if b[j]:
                    num += 1
            if num == 1:
                ans += 1
                p[i] = []
                b[i] = False
            else:
                for j in p[i]:
                    if not b[j]:
                        continue
                    b[j] = False
                    _max = max(_max, 1+pair(i+1, b))
                    b[j] = True
    return _max
print(pair(0, b)+ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
N=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
B=[2**(len(bin(i))-2) for i in A]
R=[0 for i in range(N)]
D=dict()
for i in range(N):
    if not(A[i] in D):
        D[A[i]]=queue.Queue()
    D[A[i]].put(i)
ans=0
for i in range(N):
    if R[i]==1:
        continue
    if (B[i]-A[i]) in D:
        flag=1
        if not(D[B[i]-A[i]].empty()):
            itmp=D[A[i]].get()
            j=D[B[i]-A[i]].get()
            #R[i]=1
            R[j]=1
            #print(i,j)
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A, t)
    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    already.add(n)
    a = A[n]
    t = 2 ** (int(math.log2(a)) + 1)

    while t > a:
        i = is_in(t - a, n)
        if i != -1:
            res += 1
            break
        t //= 2

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
two_pow = [2 ** i for i in range(34)]
A = [int(x) for x in input().split()]
t = [True for i in range(N)]
ans = 0
A.sort()
for i in range(N-1,-1,-1):
    if t[i]:
        for j in range(i):
            if t[j] and A[i] + A[j] in two_pow:
                ans += 1
                t[i] = t[j] = False
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > max_a:
        break
    m += 1
used = [False] * n


# def bisect(val, start, end):
#     if start >= end:
#         return None
#     elif start + 1 == end:
#         if a[start] == val:
#             if used[start]:
#                 return None
#             used[start] = True
#             debug("hoge", used)
#             return start
#         else:
#             return None
#     mid = (start + end) // 2
#     if a[mid] == val:
#         if used[mid]:
#             res = bisect(val, mid+1, end)
#             if res is not None:
#                 return res
#             res = bisect(val, start, mid)
#             return res
#         else:
#             used[mid] = True
#             debug("fuga", used)
#             return mid
#     elif a[mid] > val:
#         return bisect(val, start, mid)
#     else:
#         return bisect(val, mid, end)
#     # for i in reversed(range(end)):
#     #     if (not used[i]) and (a[i]  == val):
#     #         used[i] = True
#     #         return i
#     return None


def bisect(val, start, end):
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            debug("hoge", used)
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, start, mid)
            return res
        else:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            used[mid] = True
            return mid
        # if used[mid]:
        #     res = bisect(val, mid+1, end)
        #     if res is not None:
        #         return res
        #     res = bisect(val, start, mid)
        #     return res
        # else:
        #     used[mid] = True
        #     debug("fuga", used)
        #     return mid
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i]  == val):
    #         used[i] = True
    #         return i
    return None


def _find(b, end, e):
    "slow!!!!"
    # debug(b, end, e)
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i] + b == 2**e):
    #         used[i] = True
    #         return i
    # return None


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        debug("found: ", b, j)
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def slow_solve(N, As):
    As.sort()
    pairs = []
    counter = Counter()
    for i, a in enumerate(As):
        for j, aa in enumerate(As[i + 1:]):
            if bin(a + aa).count("1") == 1:
                pairs.append((i, j + i + 1))
                counter.update([i, j + i + 1])
    cost = []
    for p in pairs:
        cost.append((counter[p[0]] + counter[p[1]], p[0], p[1]))

    used = set()
    ans = 0
    for cost_pair in sorted(cost):
        if cost_pair[1] not in used and cost_pair[2] not in used:
            ans += 1
            used.add(cost_pair[1])
            used.add(cost_pair[2])
    return ans


if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(slow_solve(N, As))

Submission status: Time Limit Exceeded

Solution code:
import queue
N=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
B=[2**(len(bin(i))-2) for i in A]
R=[0 for i in range(N)]
D=dict()
for i in range(N):
    if not(A[i] in D):
        D[A[i]]=queue.Queue()
    D[A[i]].put(i)
ans=0
for i in range(N):
    if R[i]==1:
        continue
    if (B[i]-A[i]) in D:
        flag=1
        if not(D[B[i]-A[i]].empty()):
            j=D[B[i]-A[i]].get()
            if i!=j:
                R[i]=1
                R[j]=1
                #print(i,j)
                ans+=1
            else:
                if not(D[B[i]-A[i]].empty()):
                    j=D[B[i]-A[i]].get()
                    R[i]=1
                    R[j]=1
                    #print(i,j)
                    ans+=1
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)

count = 0
end = False
while not end:
    for y in range(1, len(a)):
        if math.log(a[0]+a[y], 2) % 1 == 0:
            count += 1
            del a[y]
            break
    del a[0]
    if len(a) < 1:
        end = True

print(count)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Grand Contest 029
# December 15, 2018
#

def checkTwoPowered(n):
  m = 1
  while True:
    if m < n:
      m *= 2
    elif m == n:
      return True
    else:
      return False

# N = 5
# A = [3, 11, 14, 5, 13]
input()
data = input().split()

A = []
for d in data:
  A.append(int(d))

N = len(A)
A.sort()

score = [0] * len(A)
result = []

for i in range(0, N - 1):
  for j in range(i + 1, N):
    if checkTwoPowered(A[i] + A[j]):
      score[i] += 1
      score[j] += 1
      result += [[i, j]]

for res in result:
  i = res[0]
  j = res[1]
  res.insert(0, score[i] + score[j])

result.sort()
used = [1] * len(A)
count = 0

for sc, i, j in result:
  if used[i] == 1 and used[j] == 1:
    count += 1
    used[i] = 0
    used[j] = 0

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
two_pow = [2 ** i for i in range(34)]
A = [int(x) for x in input().split()]
t = [True for i in range(N)]
ans = 0
A.sort()
for i in range(N-1,-1,-1):
    if t[i]:
        for j in range(i):
            if t[j] == False:
                continue
            if A[i] + A[j] in two_pow:
                ans += 1
                t[i] = t[j] = False
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
G = defaultdict(list)
A = list(map(int, input().split()))
A = sorted(A)
pow2 = [2 ** i for i in range(31)]
for i in range(N):
    for k in pow2:
        indexes = [j for j, x in enumerate(A) if x == k - A[i]]
        for j in indexes:
            G[i].append(N + j)
            G[j].append(N + i)

used = [False] * 2 * N
match = [-1] * 2 * N


def dfs(v):
    global used
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True


ma = 0
for i in range(N):
    if match[i] < 0:
        used = [False] * 2 * N
        if dfs(i):
            ma += 1

print(ma // 2)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(int(math.log2(max(A))) + 1, -1, -1)]

A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A, t)
    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    already.add(n)
    a = A[n]
    for t in [t - a for t in T if a < t <= 2 * a]:
        i = is_in(t, n)
        if i != -1:
            res += 1
            break

print(res)

Submission status: Time Limit Exceeded

Solution code:
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))

N = ri()
A = ria()

def is_beki(n):
  return (n & (n-1)) == 0

rest = []
ret = 0
A.sort(reverse=True)
for a in A:
  for r in rest:
    if is_beki(a+r):
      rest.remove(r)
      ret += 1
      break
  else:
    rest.append(a)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
a_odds = []
a_even = []

for i in range(N):
    if a[i]%2 != 0:
        a_odds.append(a[i])
    else:
        a_even.append(a[i])

a_odds.sort()
a_odds.reverse()
a_even.sort()
a_even.reverse()

count = 0
def judge(a,b):
    n = a+b
    ans = -1
    while(n>0):
        if n==1:
            ans = 0
            break
        elif n%2 == 1:
            ans = 1
            break
        elif n%2 == 0:
            n = n/2
    return ans


while(a_odds!=[]):
    for i in range(len(a_odds)):
        if judge(a_odds[0],a_odds[i])==0 and i!=0:
            count += 1
            a_odds.pop(i)
            break
    a_odds.pop(0)

while(a_even!=[]):
    for i in range(len(a_even)):
        if judge(a_even[0],a_even[i])==0 and i!=0:
            count += 1
            a_even.pop(i)
            break
    a_even.pop(0)


print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    for i in sorted(Ad.copy().keys()):
        if i >= k:
            break
        if 2*i == k:
            ans += Ad[i]//2
            del Ad[i]
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            del Ad[i]
            ans += m
        else:
            H[i] = j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.reverse()
def beki(s):
  k = math.log2(s)
  k = int(k) + 1
  return 2**k - s
i = 0
c = 0
while i < len(a):
  p = beki(a[i]) 
  q = len(a)
  for l in range(i+1,q):
    if a[l] == p:
      del a[l]
      c += 1
      break
    elif a[l] < p:
      break
  i += 1
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
def two_power(m):
  if m < 2:
    return 0
  else:
    return two_power(m//2) + 1
  
def nibun(x, *args):
  l = len(args)
  if l == 0:
    return -float('inf')
  elif args[l // 2] == x:
    return l // 2
  elif args[l // 2] < x:
    b = args[:l //2]
    return nibun(x, *b)
  else:
    b = args[l // 2+1:]
    return l // 2 + 1 + nibun(x, *b)
  
n = int(input())
a = list(map(int, input().split()))

a.sort()
a.reverse()
c = 0
skip = []
for i in range(len(a)):
  if a[i] == -1:
    break
  m = two_power(a[i])
  x = 2 ** (m+1) - a[i]
  b = a[i+1:]
  index = nibun(x, *b)
  if index >= 0:
    c += 1
    a.pop(i + 1 +index)
    a.append(-1)

print(c)

Submission status: Time Limit Exceeded

Solution code:
import math
input()
bitlist = list(map(int,input().split()))

def bitOR(bitlist):
	N = 0
	for i in bitlist:
		N = N | (1<<i)
	return N

N = bitOR(bitlist)
M = math.ceil(math.log2(N))

s = []
bit = N
for i in range(1,N):

	push = []
	for j in range(M):
		if bit & (1<<j):
			push.append(j)
	if len(push) == 2:
		s.append( push )

	if 0 == bit: break
	bit = (bit-1) & N

re = []
for i in s:
	if float.is_integer(math.log2(sum(i))):
		for j in i:
			re.append(j)
print( len(set(re))//2 )

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
G = defaultdict(list)
A = list(map(int, input().split()))
A = sorted(A)
pow2 = [2 ** i for i in range(31)]
for i in range(N):
    for j in range(i + 1, N):
        for k in pow2:
            if i != j and A[i] + A[j] == k:
                G[i].append(N + j)
                G[j].append(N + i)
                break
            if A[i] + A[j] < k:
                break

used = [False] * 2 * N
match = [-1] * 2 * N


def dfs(v):
    global used
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True


ma = 0
for i in range(N):
    if match[i] < 0:
        used = [False] * 2 * N
        if dfs(i):
            ma += 1

print(ma // 2)

Submission status: Time Limit Exceeded

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

A.sort()
m = 2 ** 31
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:
                a += 1
                if a >= n or not A[a] == A[j]:
                    continue
            used.add(a)
            used.add(j)
            ans += 1

ans2 = 0
used = set()
m = 1

for i in range(31):
    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:
                a += 1
                if a >= n or not A[a] == A[j]:
                    continue
            used.add(a)
            used.add(j)
            ans2 += 1

print(max(ans, ans2))