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:
n=int(input())
lists=list(map(int,input().split()))

from collections import Counter 
dic=dict(Counter(lists))

counter=0
for value in dic.keys():
        for i in range(30,-1,-1):
            if dic[value]>0 and ((2**i-value) in dic.keys() ) and dic[2**i-value]>0:
                M=max(dic[value],dic[2**i-value])
                counter+=M
                dic[value]-=M
                dic[2**i-value]-=M
            if dic[value]==0:
                break

print(counter)

Submission status: Wrong Answer

Solution code:
from math import log2, ceil
from collections import defaultdict

N = int(input())
A = sorted(list(map(int, input().split())))[::-1]

cnt = defaultdict(int)
for a in A:
  cnt[a] += 1

answer = 0
for a in A:
  if cnt[a]:
    i = (1 << ceil(log2(a))) - a
    if cnt[i]:
      cnt[a] -= 1
      cnt[i] -= 1
      answer += 1
      
print(answer)

Submission status: Wrong Answer

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

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

taken = 0
ans = 0
for i in range(N-1,-1,-1):
  if not taken & (1 << i):
    next_power = pow(2, ceil(log2(A[i])))
    to_find = next_power - A[i]
    if not to_find:
      to_find = A[i]

    found = bisect_right(A, to_find, hi=i)
    if found not in [0, N]:
      found -= 1
      if not bool(taken & (1 << found)):
        ans += 1
        taken |= 1 << found

print(ans)

Submission status: Wrong Answer

Solution code:
from math import log2, ceil

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

taken = 0
ans = 0
for i in range(N):
  if not taken & (1 << i):
    next_power = pow(2, ceil(log2(A[i])))
    to_find = next_power - A[i]
    if not to_find:
      to_find = A[i]

    lo, hi = i + 1, N - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      if A[mid] == to_find:
        taken |= (1 << i) | (1 << mid)
        ans += 1
        break
      elif A[mid] < to_find:
        hi =  mid - 1
      else:
        lo = mid + 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
k = 0
ans = 0
import bisect
while 2**k > max(A):
    k += 1
for i in range(k):
    t = 2**k
    for j in range(N):
        s = t - A[j]
        if s <= 0:
            break
        p = bisect.bisect_right(A,s)
        q = bisect.bisect_left(A,s)
        ans += p-q
        if s == A[j]:
            ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
A = [[A[i],0] for i in range(N)]
cnt = 0
for i in range(N-1,0,-1):
    if A[i][1]==0:
        a = A[i][0]
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A,[b,1])
        ind -= 1
        if ind<i and A[ind]==[b,0]:
            A[i][1]=1
            A[ind][1]=1
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
hist = [0 for _ in range(N)]
for i in range(N-1,0,-1):
    if hist[i]==0:
        a = A[i]
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A,b)
        if ind<i and hist[ind]==0:
            hist[i]=1
            hist[ind]=1
            cnt += 1
        elif ind<i and hist[ind]==1:
            ind += 1
            while A[ind]==b and ind<i:
                if hist[ind]==0:
                    hist[i]=1
                    hist[ind]=1
                    cnt += 1
                    break
                ind += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
hist = [0 for _ in range(N)]
for i in range(N-1,0,-1):
    if hist[i]==0:
        a = A[i]
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A[:i],b)
        if ind<i and hist[ind]==0:
            hist[i]=1
            hist[ind]=1
            cnt += 1
        elif ind<i and hist[ind]==1:
            ind += 1
            while A[ind]==b:
                if hist[ind]==0:
                    hist[i]=1
                    hist[ind]=1
                    cnt += 1
                    break
                ind += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
import bisect
def pow_two(x):
  c = 0
  while x:
    x //= 2
    c += 1
  k = 2**c
  return k

n = int(input())
A = sorted(list(map(int, input().split())))
count = dict(Counter(A))
ans = 0
for i in A[::-1]:
  if count[i] == 0:
    continue
  t = pow_two(i)
  k = A[bisect.bisect_left(A, t-i)]
  if t-i == k:
    if i == k:
      if count[i] >= 2:
        count[i] -= 2
        ans += 1
    else:
      if count[k]:
        count[k] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
import bisect
def pow_two(x):
  c = 0
  while x:
    x //= 2
    c += 1
  k = 2**c
  if x*2 == c:
    return -1
  return k

n = int(input())
A = sorted(list(map(int, input().split())))
count = dict(Counter(A))
ans = 0
for i in A[::-1]:
  if count[i] == 0:
    continue
  t = pow_two(i)
  if t == -1:
    continue
  k = A[bisect.bisect_left(A, t-i)]
  if t-i == k and count[k]:
    count[i] -= 1
    count[t-i] -= 1
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
import bisect
import math

n = int(input())
A = sorted(list(map(int, input().split())))
count = dict(Counter(A))
ans = 0
for i in A[::-1]:
  if count[i] == 0:
    continue
  t = 2 ** (int(math.log2(i))+1)
  if 2*i == t:
    continue
  k = A[bisect.bisect_left(A, t-i)]
  if t-i == k and count[k]:
    count[i] -= 1
    count[t-i] -= 1
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
import math
import collections
#奇数同士、偶数同士でしかペアは成立しない
Even=set([A[i] for i in range(N) if A[i] %2 == 0])
Odd=set([A[i] for i in range(N) if A[i] %2==1])
powers =[2**i for i in range(1,int(math.log(max(A),2)+2))]
table=collections.defaultdict(int)
ans=0
for i in range(N):
  table[A[i]]+=1
for x in table:
  while(table[x]>0):
    table[x]-=1
    for y in reversed(powers):
      if y - x in table and table[y-x]>0:
        ans+=1
        table[y-x]-=1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log2
import heapq as hq
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
a = [-a[i] for i in range(n)]
hq.heapify(a)
ans = 0
while a:
  x = hq.heappop(a)
  x = -x
  if c[x]>0:
    y = 2**(int(log2(x))+1)
    if c[y-x]>0:
      ans += 1
      c[x] -= 1
      c[y-x] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log2
import heapq as hq
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
a = [-a[i] for i in range(n)]
hq.heapify(a)
ans = 0
while a:
  x = hq.heappop(a)
  x = -x
  y = 2**(int(log2(x))+1)
  if x*2 == y:
    ans += c[x]//2
    c[x] = c[x]%2
  else:
    if c[y-x]>0:
      ans += 1
      c[x] -= 1
      c[y-x] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log2
import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()
used = [0 for i in range(n+1)]
ans = 0
for i in range(n-1,-1,-1):
  if used[i] == 0:
    used[i] = 1
    x = a[i]
    y = int(log2(x))+1
    if x*2 == 2**y:
      l = bisect.bisect_left(a,x)
      r = bisect.bisect_right(a,x)
      ans += (r-l)//2
      for i in range(l,r):
        used[i] = 1
    else:
      b = bisect.bisect_left(a,2**y-x)
      if b<n and a[b] == 2**y-x:
        if used[b] == 0:
          ans += 1
          used[b] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log2,ceil
import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()
used = [0 for i in range(n+1)]
ans = 0
for i in range(n-1,-1,-1):
  if used[i] == 0:
    x = a[i]
    y = ceil(log2(x))
    b = bisect.bisect_left(a,2**y-x)
    if b<n and a[b] == 2**y-x:
      ans += 1
      used[b] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
size_a = int(input())
a = Counter(int(x) for x in input().split())
keys = list(a.keys())
keys.sort()
pair_cnt = 0
print(a)
while size_a >= 2:
    x = keys[-1]
    if a[x] == 0:
        keys.pop()
        continue
    print('search', x, a[x])
    a[x] -= 1
    size_a -= 1
    if a[x] == 0:
        keys.pop()
    b = 2 ** x.bit_length() - x
    if a[b] > 0:
        a[b] -= 1
        size_a -= 1
        if a[b] == 0:
            del a[b]
        pair_cnt += 1
        print('found')
print(pair_cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
size_a = int(input())
a = Counter(int(x) for x in input().split())
keys = list(a.keys())
keys.sort()
pair_cnt = 0
while size_a >= 2:
    x = keys[-1]
    a[x] -= 1
    size_a -= 1
    if a[x] == 0:
        keys.pop()
    b = 2 ** x.bit_length() - x
    if a[b] > 0:
        a[b] -= 1
        size_a -= 1
        if a[b] == 0:
            del a[b]
        pair_cnt += 1
print(pair_cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)
C = Counter(A)

ans = 0
for a in A:
    pt = 2 ** len(format(a, 'b'))
    C[a] -= 1
    if C[pt - a] >= 1:
        C[pt - a] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = Counter(A)
ans = 0
# 大きい数から見ていく
for i in range(30, 1, -1):
    x = 2 ** i
    for k in C.keys():
        if x-k in C:
            # 同値ペアは別処理
            if k == x-k:
                p = C[k] // 2
                C[k] -= p * 2
                ans += p
            else:
                # 少ない方に合わせてペア作成
                p = min(C[k], C[x-k])
                C[k] -= p
                C[x-k] -= p
                ans += p
print(ans)

Submission status: Wrong Answer

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = Counter(A)
ans = 0
for i in range(30, 1, -1):
    x = 2 ** i
    for k in C.keys():
        if x-k in C:
            p = min(C[k], C[x-k])
            C[k] -= p
            C[x-k] -= p
            ans += p
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort(reverse = True)
    M = max(A)
    d = dict()
    for x in A:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    
    def exp(x):
        l = len(str(bin(x))[2:])
        return 2**l

    ans = 0
    for i in range(N):
        use = A[i]
        if (exp(use)-use) not in d:
            continue
        if d[use] <= 0:
            continue
        if exp(use)-use == use:
            if d[use] >= 2:
                d[use] -= 2
                ans += 1
        else:
            d[use] -= 1
            d[exp(use)-use] -= 1
            ans += 1
            
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort(reverse = True)
    al = [False for _ in range(N)]
    
    def exp(x):
        ans = 1
        while x > ans:
            ans *= 2
        return ans
        
    def ind(x):
        return A.index(x)
        
    ans = 0
    for i in range(N):
        if al[i] == True:
            continue
        use = A[i]
        al[i] = True
        num = exp(A[i]) - A[i]
        if ((num in A) and (al[ind(num)] == False)):
            al[ind(num)] = True
            ans += 1
            
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ball = list(map(int, input().split()))
ball.sort(reverse = True)
dic = {}
for i in range(ball[0]):
    dic[i] = 0
for x in ball:
    dic[x] = 1

ans = 0
for x in ball:
    dic[x] = 0
    y = 2**(x.bit_length()) - x
    if dic[y] == 1:
        ans += 1
        dic[y] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ball = list(map(int, input().split()))
ball.sort(reverse = True)
ok = [True] * N

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if ok[j]:
            if 2**(ball[i].bit_length()) == ball[i] + ball[j]:
                ans += 1
                ok[i] = False
                ok[j] = False
                break
print(ans)

Submission status: Wrong Answer

Solution code:
def power2(n):
    while True:
        if n == 1:
            return True 
        elif n % 2 == 1:
            return False
        else:
            n //= 2

N = int(input())
ball = list(map(int, input().split()))
ball.sort(reverse = True)
ok = [True] * N

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if ok[j]:
            if power2(ball[i]+ball[j]):
                ans += 1
                ok[j] = False
                break
print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    cur = 0; ans = 0
    for i,s in enumerate(S):
        if s=="W":
            ans += i-cur
            cur +=1
    print(ans)
    return

def examB():
    N = I()
    A = LI(); A.sort()
    ans = 0
    d = defaultdict(bool)
    for c,a in enumerate(A[::-1]):
        k = 2 ** 32
        while (k > 0):
            con = bisect.bisect_left(A,k-a)
            if con<N-c-1 and A[con]==k-a and not d[con]:
                ans +=1
                d[con]=True
#                print(con,c)
                break
            k //=2
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    cur = 0; ans = 0
    for i,s in enumerate(S):
        if s=="W":
            ans += i-cur
            cur +=1
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] +=1
    newA = []
    for a in d.keys():
        newA.append(a)
    newA.sort()
    k = 2**32
    ans = 0
    while(k>0):
        for c,a in enumerate(newA[::-1]):
            cur = 0
            if a*2<=k:
                break
            con = bisect.bisect_left(newA,k-a)
            if con<N and d[A[con]]:
                cur = min(d[a],d[k-a])
            ans +=cur
            d[a] -=cur; d[k-a] = 0
        ans += d[k//2]//2
        d[k//2] = 0
        k //=2
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    cur = 0; ans = 0
    for i,s in enumerate(S):
        if s=="W":
            ans += i-cur
            cur +=1
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] +=1
    newA = []
    for a in d.keys():
        newA.append(a)
    newA.sort()
    k = 2**32
    ans = 0
    while(k>0):
        for c,a in enumerate(newA):
            cur = 0
            if a*2>=k:
                break
            con = bisect.bisect_left(newA,k-a)
            if con<N and d[A[con]]:
                cur = min(d[a],d[k-a])
            ans +=cur
            d[a] -=cur; d[k-a] = 0
        ans += d[k//2]//2
        d[k//2] = 0
        k //=2
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

s = [2 ** x for x in range(1, 18)]
N = ri()
A = rl()
A.sort(reverse=True)
used = set()
answer = 0
for i in range(N):
    if A[i] in used:
        continue
    B = A[i+1:]
    for x in s:
        if x - A[i] in B:
            answer += 1
            used.add(x-A[i])

print(answer)
# 19

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter

power2 = [1]
while power2[-1] < 10**9:
    power2.append(power2[-1]*2)

N = int(input())
A = sorted([int(i) for i in input().split()], reverse=True)
C = Counter(A)

ans = 0
for a in A:
    if C[a] == 0:
        continue

    i = bisect.bisect_left(power2, a)
    if C[power2[i]-a] >= 1:
        ans += 1
        C[power2[i]-a] -= 1

    C[a] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import itertools
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while True:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N = I()
A = III()

A.sort()
used = [False]*N
ans = 0

for i in range(N)[::-1]:
    s = math.floor(math.log(2*A[i],2))
    p = bisect_left(A, 2**s-A[i])
    if p<=N-1 and A[p]==2**s-A[i] and p!=i and used[p]==False and used[i]==False:
        ans += 1
        used[p],used[i] = True, True

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,0,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  r = bisect.bisect_left(A[:i+1], b)
  #print(i,a,b,r)
  if r <= i and A[r] == b:
    if a == A[r]:
      ans += C[a]//2
      C[a] -= C[a]//2*2
    else:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,0,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  r = bisect.bisect_left(A[:i], b)
  #print(i,a,b,r)
  if r < i and A[r] == b:
    mn = min(C[a],C[A[r]])
    ans += mn
    C[a] -=  mn
    C[A[r]] -= mn
  elif r == i and A[r] == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(set(A)))

ans = 0
for i in range(len(A)-1,0,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  r = bisect.bisect_left(A[:i], b)
  if r < i and A[r] == b:
    mn = min(C[a],C[A[r]])
    ans += mn
    C[a] -=  mn
    C[A[r]] -= mn
  elif r == i and A[r] == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(set(A)))

ans = 0
for i in range(len(A)-1,0,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  r = bisect.bisect_left(A[:i], b)
  if r < i and A[r] == b:
    mn = min(C[a],C[A[r]])
    ans += mn
    C[a] -=  mn
    C[A[r]] -= mn
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import bisect

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

ans = 0
while(len(A)>1):
  a = A[-1]
  b = (1<<(int(math.log(a,2))+1))-a
  #print(a,b)
  r = bisect.bisect_left(A[:-1], b)
  if r < len(A) and A[r] == b:
    ans += 1
    if r == 0:
      A = A[1:-1]
    elif r == len(A)-2:
      A = A[:r]
    else:
      A = A[:r]+A[r+1:-1]
  else:
    A = A[:-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import bisect

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

ans = 0
while(len(A)>1):
  a = A[-1]
  b = (1<<(int(math.log(a,2))+1))-a
  #print(a,b)
  r = bisect.bisect_left(A[:-1], b)
  if A[r] == b:
    ans += 1
    if r == 0:
      A = A[1:-1]
    elif r == len(A)-2:
      A = A[:r]
    else:
      A = A[:r]+A[r+1:-1]
  else:
    A = A[:-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    D=defaultdict(int)
    for a in A:
        D[a]+=1

    A.sort(reverse=1)
    ans=0
    for a in A:
        k=a.bit_length()
        d=(1<<k)-a
        if(a!=d):
            if(D[d]):
                ans+=1
                D[a]-=1
                D[d]-=1
        else:
            if(D[d]>=2):
                ans+=1
                D[d]-=2
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    D=defaultdict(int)
    for a in A:
        D[a]+=1

    A.sort(reverse=1)
    ans=0
    for a in A:
        k=a.bit_length()
        d=(1<<k)-a
        print(a,d)
        if(a!=d):
            if(D[d]):
                ans+=1
                D[a]-=1
                D[d]-=1
        else:
            if(D[d]>=2):
                ans+=1
                D[d]-=2
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    D=defaultdict(int)
    for a in A:
        D[a]+=1

    A.sort(reverse=1)
    ans=0
    for a in A:
        k=a.bit_length()
        d=(1<<k)-a
        if(a!=d):
            if(D[d]):
                ans+=1
                D[d]-=1
        else:
            if(D[d]>=2):
                ans+=1
                D[d]-=1
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
from collections import*
n,*a=map(int,open(0).read().split())
C=Counter(a)
r=0
for x in sorted(a)[::-1]:
	if C[x]:y=1<<x.bit_length();C[x]-=1;r+=C[y-x]>0;C[y-x]-=1
print(r)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

ans=0
n=I()
a=sorted(LI())[::-1]
m={}
for i in a:
    if i in m:
        m[i]+=1
    else:
        m[i]=1
    
for i in a:
    t=len(bin(i))-2
    s=2**t-i
    if s in m:
        if (s==i and m[s]<=1) or m[s]==0:
            continue
        else:
            m[s]-=1
            m[i]-=1
            ans+=1
    

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

ans=0
n=I()
a=sorted(LI())[::-1]
m={}
for i in a:
    if i in m:
        m[i]+=1
    else:
        m[i]=1
    
for i in a:
    t=len(bin(i))-2
    s=2**t-i
    if s in m:
        if (s==i and m[s]==1) or m[s]==0:
            continue
        else:
            m[s]-=1
            m[i]-=1
            ans+=1
    

print(ans)