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 sys import stdin
from bisect import bisect_left

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = ds_in()

A_list.sort()

ans = 0
while len(A_list) > 1:
    max_a = A_list.pop()
    if bin(max_a)[3:].find('1') == -1:
        if max_a == A_list[-1]:
            A_list.pop()
            ans += 1
    else:
        cand = 2 ** len(bin(max_a)[2:]) - max_a
        idx = bisect_left(A_list, cand)
        if cand == A_list[idx]:
            A_list.pop(idx)
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
pow2_set = reversed([ 1<<i for i in range(36)])
ans = 0

for pow2 in pow2_set:
    l,r = 0,N-1
    while l < r:
        count += 1
        if A[l] + A[r] < pow2:
            l += 1
        elif A[l] + A[r] == pow2:
            if used[l] == 0 and used[r] == 0:
                ans += 1
                used[l],used[r] = 1,1
            else:
                if used[l] == 1:
                    l += 1
                if used[r] == 1:
                    r -= 1
        else:
            r -= 1

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

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

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

ans = 0
ind = 0
for b in beki[::-1]:
    ind = 0
    ind_max = len(A)
    while ind < ind_max and len(A) > 0:
        tar = b - A[ind]
        if tar < 0:
            break
        else:
            ind1 = ind
            ind2 = bisect.bisect_left(A,tar,ind1,len(A))

            if ind2 <= len(A):
                dam = A.pop(ind1)
                dam = A.pop(ind2-1)
                ans += 1

            else:
                ind += 1

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

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

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

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

ans = 0
ind = 0
for b in beki[::-1]:
    ind = 0
    ind_max = len(A)
    while ind < ind_max and len(A) > 0:
        tar = b - A[ind]
        if tar < 0:
            break
        elif tar in A:
            ind1 = bisect.bisect_left(A,A[ind],0,len(A))
            ind2 = bisect.bisect_left(A,tar,ind1,len(A))

            dam = A.pop(ind1)
            dam = A.pop(ind2-1)
            ans += 1

        else:
            ind += 1

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

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def log2(n):
  if n < 2:
    return 0
  else:
    return 1 + log2(n // 2)

n = int(input())
a_list = list(map(int, input().split()))
d = defaultdict(int)
a_list.sort()

for a in a_list:
  d[a] += 1

a_list = list(set(a_list))
c = 0
for a in a_list:
  m = log2(a, 2)
  x = 2 ** (m+1) - a
  if x == a:
    c += d[a] // 2
    d[a] -= d[a] // 2
  else:
    c += min(d[x], d[a])
    d[x] -= min(d[x], d[a])

print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
buf=[]
buf=input().split()
A=[]
for i in range(N):
    A.append(int(buf[i]))
A.sort()
c=0
g=0
index=[i for i in reversed(range(0,32))]
loop=[i for i in range(N-1)]
for i in index:
    sum=1<<i
    left=0
    right=N-1-g
    for j in loop:
        if right>0 and left<right :
            if (A[left]+A[right])==sum:
                A.remove(A[left])
                A.remove(A[right])
                right -= 2
                c=c+1
                g+=2
            elif(A[left]+A[right])>sum:
                right=right-1
            else:
                left=left+1
print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
buf=[]
buf=input().split()
A=[]
for i in range(N):
    A.append(int(buf[i]))
A.sort()
c=0
g=0
index=[i for i in reversed(range(0,32))]
loop=[i for i in range(N-1)]
for i in index:
    sum=1<<i
    left=0
    right=N-1-g
    for j in loop:
        if left<right:
            if (A[left]+A[right])==sum:
                A.remove(A[left])
                A.remove(A[right])
                right -= 2
                c=c+1
                g+=2
            elif(A[left]+A[right])>sum:
                right=right-1
            else:
                left=left+1
print(c)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = sorted((int(i) for i in input().split()), reverse=True)

k = 2**int(math.log(A[0], 2) + 1)

def f(A, k):
    if len(A) == 1:
        return 0

    v = A[0]

    while k >= 2*v:
        k //= 2
    w = k - v

    if w in A[1:]:
        print(k, "=", v, "+", w)
        A.remove(w)
        r = 1
    else:
        r = 0

    return r + f(A[1:], k)
print(f(A, k))

Submission status: Runtime Error

Solution code:
def judge(x):
    while(x>1):
        if x%2 != 0:
            return 0
        x/=2
    return 1

N=int(input())
buf=[]
buf=input().split()
A=[]
for i in range(N):
    A.append(int(buf[i]))
A.sort()
A.reverse()
c=0
g=0
for i in range(N-1):
    if i<N-1-g:
        for j in range(i+1,N-g):
            if A[i]!=-1 and  A[j]!=-1:
                if judge(A[i]+A[j])==1:
                    A.remove(A[i])
                    A.remove(A[j])
                    g=g+1
                    c=c+1
                    break
print(c)

Submission status: Runtime Error

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

A.sort(reverse=True)
B = [2**int(math.log(i, 2)+1) - i for i in A]

c = 0
for i, v in enumerate(B[:-1]):
    print(i, v, A[i+1:])
    if v in A[i+1:]:
        c += 1
        A.remove(v)
print(c)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))[-1::-1]
c = Counter(A)
ans = 0
for a in A:
    b = (1<<m.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
pow2_set = reversed([ 1<<i for i in range(25)])
ans = 0
for pow2 in pow2_set:
    l,r = 0,N-1
    while l < r:
        if A[l] + A[r] < pow2:
            l += 1
        elif A[l] + A[r] == pow2:
            if used[l] == 0 and used[r] == 0:
                ans += 1
                used[l],used[r] = 1,1
            else:
                if used[l] == 1:
                    l += 1
                if used[r] == 1:
                    r += 1
        else:
            r -= 1

print(ans)

Submission status: Runtime Error

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

A.sort()
m = 1 << 30
used = [False] * n
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 used[mid]):
        return search(mid, ng, n)
    else:
        return search(ok, mid, n)

for i in range(30):
    for j in range(n):
        if A[j] >= m:
            break
        if used[j]:
            cotinue
        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[a] = True
            used[j] = True
            ans += 1
    m >>= 1

print(ans)

Submission status: Runtime Error

Solution code:
import collections
 
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  for j in range(30):
    if(2**j>i):
      k=2**j-i
      break
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
a = [(i, int(v)) for i, v in enumerate(input().split())]
b = list(itertools.combinations(a,2))
c = []
h = []
for i, v in enumerate(b):
    if math.log2(b[i][0][1] + b[i][1][1]) % 1 == 0:
        c.append(b[i])
import copy
if len(c) <= 1:
    h.append(len(c))
elif len(c) >= 2:
    for i in range(len(c)):
        d = copy.deepcopy(c)
        d.remove(c[i])
        count = 0
        for v in range(len(c) - 1):
            e = (c[i][0][0] != d[v][0][0])
            f = (c[i][1][0] != d[v][1][0])
            if(e == True and f == True):
                count += 1
        h.append(count + 1)
print(max(h) if max(h) <= int(math.floor(len(a) / 2)) else math.floor(len(a) / 2))

Submission status: Runtime Error

Solution code:
a = [(i, int(v)) for i, v in enumerate(input().split())]
b = list(itertools.combinations(a,2))
c = []
for i, v in enumerate(b):
    if math.log2(b[i][0][1] + b[i][1][1]) % 1 == 0:
        c.append(b[i])
import copy
h = [0]
if len(c) >= 2:
    for i in range(len(c)):
        d = copy.deepcopy(c)
        d.remove(c[i])
        count = 0
        for v in range(len(c) - 1):
            e = (c[i][0][0] != d[v][0][0])
            f = (c[i][1][0] != d[v][1][0])
            if(e == True and f == True):
                count += 1
        h.append(count)
print(max(h) + 1)

Submission status: Runtime Error

Solution code:
a = [(i, int(v)) for i, v in enumerate(input().split())]
b = list(itertools.combinations(a,2))
c = []
for i, v in enumerate(b):
    if math.log2(b[i][0][1] + b[i][1][1]) % 1 == 0:
        c.append(b[i])
import copy
h = []
for i in range(len(c)):
    d = copy.deepcopy(c)
    d.remove(c[i])
    count = 0
    for v in range(len(c) - 1):
        e = (c[i][0][0] != d[v][0][0])
        f = (c[i][1][0] != d[v][1][0])
        if(e == True and f == True):
            count += 1
    h.append(count)
print(max(h) + 1)

Submission status: Runtime Error

Solution code:
a = [(0, 3),(1, 11),(2, 14),(3, 5),(4, 13)]
a = [(i, int(v)) for i, v in enumerate(input().split())]
b = list(itertools.combinations(a,2))
c = []
for i, v in enumerate(b):
    if math.log2(b[i][0][1] + b[i][1][1]) % 1 == 0:
        c.append(b[i])
import copy
h = []
for i in range(len(c)):
    d = copy.deepcopy(c)
    d.remove(c[i])
    count = 0
    for v in range(len(c) - 1):
        e = (c[i][0][0] != d[v][0][0])
        f = (c[i][1][0] != d[v][1][0])
        if(e == True and f == True):
            count += 1
    h.append(count)
print(max(h) + 1)

Submission status: Runtime Error

Solution code:
import bisect
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
 
res = 0
for i in range(n - 1 , -1, -1):
    if a[i] == int(a[i]):#判定
        b = 1
        while b <= a[i]:
            b =b*2
 
        j = bisect.bisect_left(a, b - a[i])
        if i > j:
            if b - a[i] == a[j]:
                c += 1
                a[j] = a[j] - 0.5
                a[i] = a[i] + 0.5
print(res)

Submission status: Runtime Error

Solution code:
import bisect
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
 
res = 0
for i in range(n - 1 , -1, -1):
    if a[i] == int(a[i]):#判定
        b = 1
        while b <= A[i]:
            b =b*2
 
        j = bisect.bisect_left(A, b - A[i])
        if i > j:
            if b - a[i] == a[j]:
                c += 1
                a[j] = a[j] - 0.5
                a[i] = a[i] + 0.5
print(res)

Submission status: Runtime Error

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

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):
    beki=2**b
    if beki > A[i]:
      pair=beki - 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 collections
 
n=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  for j in range(20):
    if(2**j>i):
      k=2**j-i
      break
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import collections
 
n=int(input())
a=list(map(int, input().split()))
a.sort()
a.reverse()
c=collections.Counter(a)
ans=0
for i in a:
  for j in range(20):
    if(2**j>i):
      k=2**j-i
      break
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  vector<int>A(N);
  for(int &a:A)cin>>a;
  sort(A.begin(),A.end(),greater<int>());
  map<int,int>m;
  int ans=0;
  for(int a:A){
    if(m.count(a)&&m[a]>0)m[a]--,ans++;
    else m[(1<<(32-__builtin_clz(a)))-a]++;
  }
  cout<<ans<<endl;
}

Submission status: Runtime Error

Solution code:
from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
#t.sort()


u = [0 for i in range(len(t))]

#print(a)        
#print(t)
sum = 0
for i in range (len(a)-1,-1,-1):
    k = bisect_left(a,t[i])
    #print(t[i],k)
    if a[k] == t[i] and k < i:
        #print(a[i],t[i],i)
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
        u[k] += 1
print(sum)

Submission status: Runtime Error

Solution code:
from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
#t.sort()


u = [0 for i in range(len(t))]

#print(a)        
#print(t)
sum = 0
for i in range (len(a)-1,-1,-1):
    k = bisect_left(a,t[i])
    print(t[i],k)
    if a[k] == t[i] and k < i:
        #print(a[i],t[i],i)
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
        u[k] += 1
#print(sum)

Submission status: Runtime Error

Solution code:
from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.sort(reverse=True)


u = [0 for i in range(len(t))]

#print(a)        
#print(t)
sum = 0
for i in range (len(a)-1,-1,-1):
    k = bisect_left(a,t[i])
    #print(t[i],k)a
    if a[k] == t[i] and k < i:
        #print(a[i],t[i],i)
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
        u[k] += 1
print(sum)

Submission status: Runtime Error

Solution code:
from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.sort(reverse=True)


u = [0 for i in range(len(t))]

#print(a)        
#print(t)
sum = 0
for i in range (len(a)-1,-1,-1):
    k = bisect_left(a,t[i])
    #print(t[i],k)
    if a[k] == t[i] and u[k] == 0 and k < i:
        #print(a[i],t[i],i)
        sum += 1
        u[k] += 1
print(sum)

Submission status: Runtime Error

Solution code:
from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.sort(reverse=True)


u = [0 for i in range(len(t))]

#print(a)        
#print(t)
sum = 0
for i in range (len(a)-1,-1,-1):
    k = bisect_left(a,t[i])
    #print(t[i],k)
    if a[k] == t[i] and u[k] == 0 and k != i:
        #print(a[i],t[i],i)
        sum += 1
        u[k] += 1
print(sum)

Submission status: Runtime Error

Solution code:
from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.reverse()

u = [0 for i in range(len(t))]

#print(a)        
#print(t)
sum = 0
for i in range (len(a)-1,-1,-1):
    k = bisect_left(a,t[i])
    #print(t[i],k)
    if a[k] == t[i] and u[k] == 0 and k != i:
        #print(a[i],t[i],i)
        sum += 1
        u[k] += 1
print(sum)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
Ae1=[]
Ao1=[]
for i in range(N):
    if A[i]%2==0:
        Ae1.append(A[i])
    else:
        Ao1.append(A[i])
if Ao1!=[]:
    s=0
    Ao=sorted(Ao1,reverse=True)
    i=0
    while i<=len(Ao)-1:
        a=int(math.log2(Ao[i]))
        a1=2**(a+1)-Ao[i]
        if a1 in Ao[i+1:]:
            s+=1
            Ao.pop(bisect.bisect_left(Ao,a1)
            i+=1
        else:
            i+=1
else:
    s=0
if Ae1!=[]:
    t=0
    Ae=sorted(Ae1,reverse=True)
    j=0
    while j<=len(Ae)-1:
        b=int(math.log2(Ae[j]))
        b1=2**(b+1)-Ae[j]
        if b1 in Ae[j+1:]:
            t+=1
            Ae.pop(bisect.bisect_left(Ae,b1)
            j+=1
        else:
            j+=1
else:
    t=0
print(s+t)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
a = list(map(int, input().split()))
if n==1:
	print("0")
else:
	ans = 0
	a.sort()
	i = 2
	while i<=a[n-2]+a[n-1]:
		if i<a[0]+a[1]:
			i *= 2
			continue
		memo = 0
		j = 0
		while a[j]<=i/2:
			if j>0 and a[j]==a[j-1]:
				ans += memo
				j += 1
				continue
			left = bisect.bisect_left(a, i-a[j])
			if a[left]!=i-a[j]:
				memo = 0
				j += 1
				continue
			right = bisect.bisect_right(a, i-a[j])
			if a[j]==i/2:
				ans += int((right-left)*(right-left-1)/2)
				j += right-left
			else:
				memo = right-left
				ans += memo
				j += 1
		i *= 2
	print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.reverse()
a.sort(reverse=True)

c = {}
for aa in a:
    if aa in c:
        c[aa] += 1
    else:
        c[aa] = 1

#print(t)
#print(a)        
#print(c)

sum = 0
i = 0

for i in range(len(a)-1):

    if t[i] in c :
        #print("\t",a[i],t[i])
        if c[t[i]] > 0 :
            if c[t[i]] == 1 and a[i] == t[i]:
                pass
            else:
                #print("\t",a[i],t[i])                
                sum += 1
                c[t[i]] -= 1
print(sum)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for i in reversed(range(n)):
    if memo[a[i]] == 0:
        continue
    if memo[1 << (len(bin(a[i])) - 2) - a[i]] == 0:
        continue
    memo[a[i]] -= 1
    memo[1 << (len(bin(a[i])) - 2) - a[i]] -= 1
    count += 1

print(count)

Submission status: Runtime Error

Solution code:
import math
from collections import defaultdict

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()
    used = [False] * n

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        if used[cur]:
            continue
        num = nums[cur]
        power_of_2 = 1 << math.ceil(math.log2(num))

        pair = power_of_2 - num

        if nums_cnt[pair] != 0:
            nums_cnt[pair] -= 1
            used[pair] = True
            cnt += 1


        '''
        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            #print('continue',pair, idx)
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums, used)
        '''

    print(cnt)

    return

main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()
    used = [False] * n

    num_bin_digits = [1 << len(f"{x:b}") for x in nums]
    cnt = 0

    for cur in reversed(range(n)):
        if used[cur]:
            continue

        num = nums[cur]
        power_of_2 = num_bin_digits[cur]
        pair = power_of_2 - num
        idx = -1
        if pair in nums[:cur]:
            idx = nums.index(pair)

        if idx != -1 and not used[idx]:
            used[idx] = True
            cnt += 1

    print(cnt)
    return

main()

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):
    if(dict1[arr[i]]>0):
        val2=int(ceil(log(arr[i],2)))
        xd=2**val2
        if(xd!=2*arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    dict1[arr[i]]-=1
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=2
    #print(dict1)
print(ans)

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=int(ceil(log(arr[i],2)))
        xd=2**val2
        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:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.reverse()
a.sort(reverse=True)

c = {}
for aa in a:
    if aa in c:
        c[aa] += 1
    else:
        c[aa] = 1

sum = 0
i = 0

u = [0 for i in range(len(a))]

for i in range(len(a)-1):

    if t[i] in c :
        if c[t[i]] > 0 :
            if c[t[i]] == 1 and a[i] == t[i]:
                pass
            else:
                sum += 1
                c[t[i]] -= 1
        
print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.reverse()
a.sort(reverse=True)

c = {}
for aa in a:
    if aa in c:
        c[aa] += 1
    else:
        c[aa] = 1

sum = 0
i = 0

u = [0 for i in range(len(a))]

for i in range(len(a)-1):

    if u[i] > 0:
        continue

    if t[i] in c :
        if c[t[i]] > 0 :
            sum += 1
            c[t[i]] -= 1
        
print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.reverse()
a.sort(reverse=True)

#print(t,a)
sum = 0
i = 0

u = [0 for i in range(len(a))]

for i in range(len(a)-1):

    if u[i] > 0:
        continue

    first = i+1
    last = len(a)-1
    found = False
 
    while first<=last and not found:
        midpoint = (first + last)//2
        if a[midpoint] == t[i] and u[midpoint] <= 0 and midpoint != i:
            found = True
            sum += 1
            u[midpoint] +=1
        else:
            if t[i] > a[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
print(sum)

Submission status: Runtime Error

Solution code:
def b_powers_of_two(N, A):
    # 参考: https://beta.atcoder.jp/contests/agc029/submissions/3804857
    from bisect import bisect_left
    a = sorted(A)
    ans = 0
    for j in range(N - 1, -1, -1):
        # b > a[j]となるような最小のb(これは2の冪乗である)を探す
        b = 1
        while b <= a[j]:
            b <<= 1

        k = bisect_left(a, b - a[j])
        if k < j and (b - a[j] == a[k]):
            # a[k] <= a[j] であり、かつ、a[j] + a[k] = b(2の冪乗)
            # となるペア(j, k)が見つかれば、貪欲にペアにしてよい。
            # (a[j] を放置すると、ペアにできる可能性がある整数が少なくなり、得にならない)
            ans += 1
            # 整数でなくしておいて、ペアに使えないようにする。
            # ペアのうち、要素番号が大きい方は足し、小さい方は引いておくと、
            # 同じ値が複数あったときも二部探索で以前にペアにした整数を
            # ピックアップすることがなくなる。
            a[j] += 0.1
            a[k] -= 0.1

    return ans

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

#print(t,a)
sum = 0
i = 0

u = [0 for i in range(len(a))]

for i in range(len(a)-1):

    if u[i] > 0:
        continue

    first = i+1
    last = len(a)-1
    found = False
 
    while first<=last and not found:
        midpoint = (first + last)//2
        if a[midpoint] == t[i] and u[i] <= 0:
            found = True
            sum += 1
            a.pop(midpoint)
            u[i] +=1
        else:
            if t[i] > a[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
    
print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

#print(t,a)
sum = 0
i = 0

u = [0 for i in range(len(a))]

for i in range(len(a)-1):

    if u[i] > 0:
        continue

    for j in range(i+1,len(a)):
        if a[j] == t[i] and u[j] <= 0:
            sum += 1
            u[j] += 1
    #print(a)
    
print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

sum = 0
i = 0

u = [0 for i in range(len(a))]

for i in range(len(a)-1):

    for j in range(i+1,len(a)):
        if a[j] == t[i] and u[j] <= 0:
            sum += 1
            u[j] += 1
    #print(a)
    
print(sum)