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: Wrong Answer

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()
    t=int(math.log2(head))+1
    if 2**(t-1)==head:
    #これは、2,4,8とか2のべき乗だけが引っかかる条件
        second=dq.pop()
        if head==second:
        #2のべきでも、きちんと2個存在するならおｋ
            ans+=1
        else:
            dq.appendleft(second)
    else:
        #inが遅すぎるかもしれない。ちょっと高速化
        #上で被りうる奴は排除できている。
        for j in range(len(dq)):
            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にしたことでインデックスも取得できるので。

Submission status: Wrong Answer

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_)>0:
    x,y=0,0
    t_max=int(math.log2(a_[0]*2)+1)
    for t in range(t_max,0,-1):
        x+=a_[0]
        y+=2**t-a_[0]
        if y in a_:
            if x!=y:
                ans+=1
                a_.remove(x)
                a_.remove(y)
                break
            else:
                a_.remove(x)
                break
        if t==1:
            a_.remove(x)
            break
        x,y=0,0 
print(ans)

Submission status: Wrong Answer

Solution code:
def inv(x):
    z=1
    while z<x:
        z<<=1
    return z-x

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

d={}
for x in A:
    if x in d:
        d[x]+=1
    else:
        d[x]=1

l=sorted(d,reverse=True)

ans=0

for x in l:
    if d[x]>0:
        y=inv(x)
        if x==y and d[x]>0:
            ans+=d[x]//2
        elif y in d and d[y]>0:
            ans+=min(d[x],d[y])
            d[y]-=min(d[x],d[y])

print(ans)

Submission status: Wrong Answer

Solution code:
def inv(x):
    z=1
    while z<x:
        z<<=1
    return z-x

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

d={}
for x in A:
    if x in d:
        d[x]+=1
    else:
        d[x]=1

A.sort(reverse=True)

ans=0

for x in A:
    if d[x]>0:
        y=inv(x)
        if x==y and d[x]>0:
            ans+=d[x]//2
        elif y in d and d[y]>0:
            ans+=min(d[x],d[y])
            d[y]-=min(d[x],d[y])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A_odd = [[] for _ in range(32)]
def num2(x):
  cnt =0
  while x%2 ==0:
    x = x//2
    cnt += 1
  return x,cnt
for a in A:
  x,cnt = num2(a)
  A_odd[cnt].append(x)
count = 0
for a in A_odd:
  a.sort()
  l = len(a)
  a_bool = [True]*l
  for i in reversed(range(32)):
    j = 0
    for k in reversed(range(l)):
      if a_bool[k]:
        while j<k-1 and a[j]+a[k]<2**i:
          j += 1
        if a[j]+a[k]==2**i and a_bool[k] and j!= k:
          count += 1
          a_bool[j]=False
          a_bool[k]=False
         
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A_0 = []
A_1 = []
for a in A:
  if a%2 == 0:
    A_0.append(a)
  else:
    A_1.append(a)
cnt = 0
A_0.sort()
A_1.sort()
A_0_bool = [True]*len(A_0)
for i in reversed(range(len(A_0))):
  for j in range(i):
    if bin(A_0[i]+A_0[j])== "0b1"+"0"*(len(bin(A_0[i]+A_0[j]))-3) and A_0_bool[j]:
      A_0_bool[j] = False
      cnt += 1
      break

A_1_bool = [True]*len(A_1)
for i in reversed(range(len(A_1))):
  for j in range(i):
    if bin(A_1[i]+A_1[j])== "0b1"+"0"*(len(bin(A_1[i]+A_1[j]))-3) and A_1_bool[j]:
      A_1_bool[j] = False
      cnt += 1
      break

print(cnt)

Submission status: Wrong Answer

Solution code:
import copy
import bisect

def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()

for i in range(n-1):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and x==a[i+1]:
            ans+=1
            ano_a[c]=-1
            ano_a[c+1]=-1
            a[i+1]=None
            a[i]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                ano_a[c]=-1
                ano_a[-i-1]=-1
                a[i]=None
                a[n-c-1]=None
        a[i]=None
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import bisect

def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()

for i in range(n-1):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and x==a[i+1]:
            ans+=1
            ano_a[c]=-1
            ano_a[c+1]=-1
            a[i+1]=None
            a[i]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                ano_a[c]=-1
                a[i]=None
                a[n-c-1]=None
        a[i]=None
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import bisect

def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()

for i in range(n-1):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and x==a[i+1]:
            ans+=1
            ano_a[c]=-1
            ano_a[c+1]=-1
            a[i+1]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                ano_a[c]=-1
        a[i]=None
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import bisect

def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()
for i in range(n-1):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and a[i+1]==x:
            ans+=1
            ano_a[c]=-1
        elif c>=0:
            if x!=a[i]:
                ans+=1
                ano_a[c]=-1
        a[i]=None
            
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import bisect

def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()
for i in range(n-1):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and a[i+1]==x:
            ans+=1
            a[i]=None
            a[c]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                a[c]=None
                a[i]=None
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import bisect

def index(a, x):
    i = bisect.bisect_right(a, x)

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

Submission status: Wrong Answer

Solution code:
import copy
import bisect

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

Submission status: Wrong Answer

Solution code:
import copy

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return mid


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

Submission status: Wrong Answer

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for b in a:
    if b:
        bi=format(b, 'b')
        x=2**len(bi)-b
        if x==b:
            ans+=1
            b=None

print(ans)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
            
        elif x in a and x!=a[i]:
            ans+=1
            
            a[i]=None
print(ans)

Submission status: Wrong Answer

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 in a:
            ans+=1
            a.remove(x)
        a.pop(0)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#AGC29 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()
f = defaultdict(lambda : 0)
for i in a:
    f[i] = 1
ans = 0
lst = [1 << i for i in range(32)]
for i in a[::-1]:
    if not f[i]:
        continue
    f[i] -= 1
    for j in lst:
        tmp = j - i
        if tmp <= 0:
            continue
        if f[tmp]:
            ans += 1
            f[tmp] -= 1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#AGC29 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()
f = defaultdict(lambda : 0)
for i in a:
    f[i] = 1
ans = 0
lst = [1 << i for i in range(32)]
for i in a[::-1]:
    if not f[i]:
        continue
    f[i] -= 1
    for j in lst:
        tmp = j - i
        if f[tmp]:
            ans += 1
            f[tmp] -= 1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#AGC29 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()
f = defaultdict(lambda : 0)
for i in a:
    f[i] = 1
ans = 0
lst = [1 << i for i in range(32)]
for i in a[::-1]:
    if not f[i]:
        continue
    f[i] -= 1
    for j in lst:
        tmp = j - i
        if tmp <= 0 or tmp > 2*i:
            continue
        if f[tmp]:
            ans += 1
            f[tmp] -= 1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = sorted(LI())
bit_len = (L[-1] + L[-2]).bit_length()
L += [INF]
used = [0] * n
cnt = 0
for i in range(bit_len, 0, -1):
    for j in range(n):
        if used[j]:
            continue
        pair = (1 << i) - L[j]
        pair_ind = bisect_left(L, pair)
        if L[pair_ind] == pair and not used[pair_ind] and pair_ind != j:
            used[j] = used[pair_ind] = 1
            cnt += 1



print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = sorted(LI()) + [INF]
used = [0] * n
cnt = 0
for i in range((10 ** 9).bit_length(), 0, -1):
    for j in range(n):
        if used[j]:
            continue
        pair = (1 << i) - L[j]
        pair_ind = bisect_left(L, pair)
        if L[pair_ind] == pair and not used[pair_ind] and pair_ind != j:
            used[j] = used[pair_ind] = 1
            cnt += 1



print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = Counter(a)

ans = 0
for i in a:
    if c[i] == 0:
        continue
    c[i] -= 1
    k = 1<<((i-1).bit_length())
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = Counter(a)

ans = 0
for i in a:
    if c[i] == 0:
        continue
    c[i] -= 1
    k = 1<<(i-1).bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
C = Counter(A)
keys = set(A)

ans = 0
for a in A:
    target_2_pow = 2 ** a.bit_length()
    b = target_2_pow - a
    if b not in keys:
        continue

    if a != b:
        if C[b] == 0:
            continue
        ans += 1
        C[a] -= 1
        C[b] -= 1
    else:
        if C[b] < 2:
            continue
        ans += 1
        C[a] -= 2

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))

A = sorted(A)
B = sorted(A, reverse=True)
count = 0
maxval = A[N-1]
depth = int(np.log2((maxval-1))+2)
for d in range(1,depth):
    i = 0
    j = 0
    M = len(A)
    endcount = 0
    while 1:
        if M + endcount <= i+j:
            break
        if i==M-1 or j==M-1:
            break
        if A[i] >= 2**d:
            break
        wa = A[i] + B[j]
        if wa > 2**d:
            j += 1
        elif wa < 2**d:
            i += 1
        elif A[i] == B[j] and A[i]!=A[i+1] and B[j]!=B[j+1]:
            break
        else:
            A.remove(A[i])
            B.remove(B[j])
            count += 1
            endcount += 1
            M -= 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))

A = sorted(A)
B = sorted(A, reverse=True)

count = 0
maxval = A[N-1]
depth = int(np.log2((maxval-1))+2)
for d in range(1,depth):
    i = 0
    j = 0
    M = len(A)
    endcount = 0
    while 1:
        if M + endcount <= i+j:
            break
        if i==M-1 or j==M-1:
            break
        if A[i] >= 2**d:
            break
        wa = A[i] + B[j]
        if wa > 2**d:
            j += 1
        elif wa < 2**d:
            i += 1
        elif A[i] == B[i] and A[i]!=A[i+1] and B[j]!=B[j+1]:
            break
        else:
            A.remove(A[i])
            B.remove(B[i])
            count += 1
            endcount += 1
            M -= 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import*
N,*A=map(int, open(0).read().split())
A.sort()
C=Counter(A)
s=0
for a in A[::-1]:
	if C[a]:
		C[a]-=1
	b=2**a.bit_length()-a
	if C[b]:
		C[b]-=1
		s += 1
print(s)

Submission status: Wrong Answer

Solution code:
from collections import Counter


N, *A = map(int, open(0).read().split())

C = Counter(A)

A.sort(reverse=True)

ans = 0
for a in A:
    b = 2 ** a.bit_length() - a
    C[a] -= 1
    C[b] -= 1
    if C[a] >= 0 and C[b] >= 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, *A = map(int, open(0).read().split())

S = set(A)

A.sort(reverse=True)

ans = 0
for a in A:
    b = 2 ** a.bit_length() - a
    if a != b and b in S:
        S.remove(b)
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
d = dict()
u = dict()
ans = 0
a.sort(reverse=True)

for x in a:
  if x not in d:
    d[x] = 0
  d[x] += 1
  
for x in a:
  d[x] -= 1
  if u.get(x,0):
    u[x] -= 1
    continue
  p = (1<<x.bit_length()) - x
  if d.get(p,0):
    d[p] -= 1
    u[p] = u.get(p,0) + 1
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
N = int(input())
A = [int(x) for x in input().split()]
D = defaultdict(int)
for a in A:
  D[a] += 1
cnt = 0
for a in sorted(D.keys(), reverse=True):
  p = 2 ** math.ceil(math.log(a, 2))
  d = p - a
  if a == d:
    cnt += D[a] // 2
    D[a] %= 2
  else:
    m = min(D[a], D[d])
    cnt += m
    D[a] -= m
    D[d] -= m
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
import bisect
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
cnt = 0
pos = 0
while pos < len(A) - 1:
  p = 2 ** math.ceil(math.log(A[pos], 2))
  d = p - A[pos]
  t = bisect.bisect(A[::-1], d, hi=len(A) - pos - 1)
  if A[-t] == d:
    A.pop(-t)
    cnt += 1
  pos += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
import bisect
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
cnt = 0
pos = 0
while pos < len(A) - 1:
  p = 2 ** math.ceil(math.log(A[pos], 2))
  d = p - A[pos]
  t = bisect.bisect(A[::-1], d, hi=len(A) - pos - 1)
  print(p, d, t)
  if A[-t] == d:
    A.pop(-t)
    cnt += 1
  pos += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
import bisect
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
cnt = 0
pos = 0
while pos < len(A):
  p = 2 ** math.ceil(math.log(A[pos], 2))
  d = p - A[pos]
  t = bisect.bisect(A[::-1], d, hi=len(A) - pos)
  if A[-t] == d:
    A.pop(-t)
    cnt += 1
  pos += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect


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

group = {}
for i in range(n):
    ntz = a[i] & (-a[i])
    if ntz not in group:
        group[ntz] = {}
        group[ntz][a[i] // (ntz*2)] = 1
    elif a[i] // (ntz*2) not in group[ntz]:
        group[ntz][a[i] // (ntz*2)] = 1
    else:
        group[ntz][a[i] // (ntz*2)] += 1
      

ans = 0
for ntz in group:
    li = sorted(group[ntz].keys(), reverse = True)
    for num1 in li:
        tmp = len(bin(num1)) - 2
        num2 = num1 ^ (2**tmp - 1)
        # if num2 == num1:
        #    tmp_ans = group[ntz][num1] // 2
        #    ans += tmp_ans
        #   group[ntz][num1] -= tmp_ans * 2
        #   continue
        if num2 in group[ntz]:
            tmp_ans = min(group[ntz][num1], group[ntz][num2])
            ans += tmp_ans
            group[ntz][num1] -= tmp_ans
            group[ntz][num2] -= tmp_ans
print(ans)

Submission status: Wrong Answer

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

group = {}
for i in range(n):
    ntz = a[i] & (-a[i])
    if ntz not in group:
        group[ntz] = {}
        group[ntz][a[i] // (ntz*2)] = 1
    elif a[i] // (ntz*2) not in group[ntz]:
        group[ntz][a[i] // (ntz*2)] = 1
    else:
        group[ntz][a[i] // (ntz*2)] += 1
      
ans = 0
for ntz in group:
    li = sorted(group[ntz].keys(), reverse = True)
    for num1 in li:
        tmp = len(bin(num1)) - 2
        num2 = num1 ^ (2**tmp - 1)
        if num2 == num1:
            tmp_ans = group[ntz][num1] // 2
            ans += tmp_ans
            group[ntz][num1] -= tmp_ans * 2
            continue
        if num2 in group[ntz]:
            tmp_ans = min(group[ntz][num1], group[ntz][num2])
            ans += tmp_ans
            group[ntz][num1] -= tmp_ans
            group[ntz][num2] -= tmp_ans
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    sys.exit()
    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 a not in d:
    continue
  t = power_of_two[bisect_right(power_of_two, a)] - a
  if t not in d:
    continue
  if a != t:
    if d[a] < d[t]:
      i = d[a]
    else:
      i = d[t]
  else:
    if d[a] == 1:
      continue
    i = d[a] // 2
  result += i  
  if d[a] == i:
    del d[a]
  else:
    d[a] -= i
  if d[t] == i:
    del d[t]
  else:
    d[t] -= i
print(result)

Submission status: Wrong Answer

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 a not in d or d[a] == 0:
    continue
  t = power_of_two[bisect_right(power_of_two, a)] - a
  if t not in d or d[t] == 0:
    continue
  if a != t:
    i = min(d[a], d[t])
  else:
    i = d[a] // 2
  if i == 0:
    continue
  result += i
  d[a] -= i
  d[t] -= i
  if a not in d or d[a] == 0:
    break
print(result)

Submission status: Wrong Answer

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
  if t not in d:
    continue
  if d[t] == 0:
    continue
  if a != t:
    i = min(d[a], d[t])
  else:
    i = d[a] // 2
  result += i
  d[a] -= i
  d[t] -= 1
print(result)

Submission status: Wrong Answer

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
  if t not in d:
    continue
  if d[a] != d[t]:
    i = min(d[a], d[t])
  else:
    i = d[a] // 2
  result += i
  d[a] -= i
  d[t] -= 1
print(result)

Submission status: Wrong Answer

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
  if t not in d:
    continue
  if a != t:
    i = min(d[a], d[t])
  else:
    i = d[a] // 2
    if i == 0:
      continue
  result += i
  d[a] -= i
  d[t] -= 1
print(result)

Submission status: Wrong Answer

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
  if t not in d:
    continue
  if a == t and d[a] == 1:
    continue
  i = min(d[a], d[t])
  result += i
  d[a] -= i
  d[t] -= 1
print(result)

Submission status: Wrong Answer

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:
    if x not in d:
      continue
    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
  if prev == result:
    break
print(result)