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 sys
readline = sys.stdin.readline

# 残った数の中で最大の数とペアになれる（可能性のある）数は一意に決まる。
# 15に15以下の数を足して作れる2べきは16だけ、32は作れない。
# 8 * 2 < 15 * 2 < 16 * 2だから。
# 大きいほうから見ていって、ペアになれる数を特定出来たらペアにする。
# 以下を別々で持つ
# ・大きい順の管理
# ・探している数へのO(1)での到達と、残数管理（同じ数が複数回出てくる可能性があるため）

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

from collections import defaultdict

balls_count = defaultdict(int) # 個数の管理

import heapq as hq
balls_q = [] # ボールを大きい順に入れていく

for a in A:
  balls_count[a] += 1
  hq.heappush(balls_q, -a)

def get_pair_num(x): # xとペアになれる数を探す
  tar = 2
  while tar < x:
    tar *= 2
  return tar - x

ans = 0
while balls_q:
  ball = -(hq.heappop(balls_q))
  if balls_count[ball] == 0: # すでに使用済みのボールである
    continue
  # 取り出した時点で、このあとペアにするか破棄するかのどちらかである。
  # 同じボールを取り出すことのないよう、この時点で1引いておく
  balls_count[ball] -= 1
  pair = get_pair_num(ball)
  if balls_count[pair] > 0:
    ans += 1
    balls_count[pair] -= 1
  # pushしないからheapqでなくてよかったな・・・

print(ans)

Submission status: Wrong Answer

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

# 残った数の中で最大の数とペアになれる（可能性のある）数は一意に決まる。
# 15に15以下の数を足して作れる2べきは16だけ、32は作れない。
# 8 * 2 < 15 * 2 < 16 * 2だから。
# 大きいほうから見ていって、ペアになれる数を特定出来たらペアにする。
# 以下を別々で持つ
# ・大きい順の管理
# ・探している数へのO(1)での到達と、残数管理（同じ数が複数回出てくる可能性があるため）

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

from collections import defaultdict

balls_count = defaultdict(int) # 個数の管理

import heapq as hq
balls_q = [] # ボールを大きい順に入れていく

for a in A:
  balls_count[a] += 1
  hq.heappush(balls_q, -a)

def get_pair_num(x): # xとペアになれる数を探す
  tar = 1
  while tar < x:
    tar *= 2
  return tar - x

ans = 0
while balls_q:
  ball = -(hq.heappop(balls_q))
  if balls_count[ball] == 0: # すでに使用済みのボールである
    continue
  # 取り出した時点で、このあとペアにするか破棄するかのどちらかである。
  # 同じボールを取り出すことのないよう、この時点で1引いておく
  balls_count[ball] -= 1
  pair = get_pair_num(ball)
  if balls_count[pair] > 0:
    ans += 1
    balls_count[pair] -= 1
  # pushしないからheapqでなくてよかったな・・・

print(ans)

Submission status: Wrong Answer

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

# 残った数の中で最大の数とペアになれる（可能性のある）数は一意に決まる。
# 15に15以下の数を足して作れる2べきは16だけ、32は作れない。
# 8 * 2 < 15 * 2 < 16 * 2だから。
# 大きいほうから見ていって、ペアになれる数を特定出来たらペアにする。
# 以下を別々で持つ
# ・大きい順の管理
# ・探している数へのO(1)での到達と、残数管理（同じ数が複数回出てくる可能性があるため）

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

from collections import defaultdict

balls_count = defaultdict(int) # 個数の管理

import heapq as hq
balls_q = [] # ボールを大きい順に入れていく

for a in A:
  balls_count[a] += 1
  hq.heappush(balls_q, -a)

def get_pair_num(x): # xとペアになれる数を探す
  tar = 2
  while tar < x:
    tar *= 2
  return tar - x

ans = 0
while balls_q:
  ball = hq.heappop(balls_q)
  if balls_count[-ball] == 0: # すでに使用済みのボールである
    continue
  # 取り出した時点で、このあとペアにするか破棄するかのどちらかである。
  # 同じボールを取り出すことのないよう、この時点で1引いておく
  balls_count[-ball] -= 1
  pair = get_pair_num(-ball)
  if balls_count[pair] > 0:
    ans += 1
    balls_count[pair] -= 1
  # pushしないからheapqでなくてよかったな・・・

print(ans)

Submission status: Wrong Answer

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

# 残った数の中で最大の数とペアになれる（可能性のある）数は一意に決まる。
# 15に15以下の数を足して作れる2べきは16だけ、32は作れない。
# 8 * 2 < 15 * 2 < 16 * 2だから。
# 大きいほうから見ていって、ペアになれる数を特定出来たらペアにする。
# 以下を別々で持つ
# ・大きい順の管理
# ・探している数へのO(1)での到達と、残数管理（同じ数が複数回出てくる可能性があるため）

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

from collections import defaultdict

balls_count = defaultdict(int) # 個数の管理

import heapq as hq
balls_q = [] # ボールを大きい順に入れていく

for a in A:
  balls_count[a] += 1
  hq.heappush(balls_q, -a)

def get_pair_num(x): # xとペアになれる数を探す
  tar = 2
  while tar < x:
    tar *= 2
  return tar - x

ans = 0
while balls_q:
  ball = hq.heappop(balls_q)
  # 取り出した時点で、このあとペアにするか破棄するかのどちらかである。
  # 同じボールを取り出すことのないよう、この時点で1引いておく
  balls_count[ball] -= 1
  pair = get_pair_num(-ball)
  if balls_count[pair] > 0:
    ans += 1
    balls_count[pair] -= 1
  # pushしないからheapqでなくてよかったな・・・

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

N = int(input())
A = list(map(int,input().split()))
#B = set(A)
for i in A:
  dic[i] +=1

beki = [1]
for i in range(32): #30に変更
  temp = beki[-1]
  beki.append(temp*2)
#print(beki)
L = [[] for _ in range(N)]
for i in range(N):
  for t in beki:
    now = t-A[i]
    if A[i] == now and dic[now] >=2:
      L[i].append(now)
    elif A[i] != now and now>0 and now in dic:
      L[i].append(now)
  L[i].append(A[i]) #自分を足しておく

L.sort(key=len)
#print(L)
#print(dic)
ans = 0
for i in range(N):
  now = L[i].pop()
  #print(L[i],dic)
  for num in L[i]:
    if num in dic:
      if num == now and dic[now] > 1:
        dic[num] -=2
        ans += 1
        break
      elif num != now and dic[num] > 0 and dic[now] > 0:
        dic[num] -= 1
        dic[now] -= 1
        ans += 1
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

N = int(input())
A = list(map(int,input().split()))
B = set(A)
for i in A:
  dic[i] +=1

beki = [1]
for i in range(30): #30に変更
  temp = beki[-1]
  beki.append(temp*2)
#print(beki)
L = [[] for _ in range(N)]
for i in range(N):
  for t in beki:
    now = t-A[i]
    if A[i] == now and dic[now] >2:
      L[i].append(now)
    elif A[i] != now and now>0 and now in dic:
      L[i].append(now)
  L[i].append(A[i]) #自分を足しておく

L.sort(key=len)
#print(L)
#print(dic)
ans = 0
for i in range(N):
  now = L[i].pop()
  #print(L[i])
  for num in L[i]:
    if num in dic:
      if num == now and dic[now] > 1:
        dic[num] -=2
        ans += 1
        break
      elif num != now and dic[num] > 0 and dic[now] > 0:
        dic[num] -= 1
        dic[now] -= 1
        ans += 1
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

N = int(input())
A = list(map(int,input().split()))
B = set(A)
for i in A:
  dic[i] +=1

beki = [1]
for i in range(30): #30に変更
  temp = beki[-1]
  beki.append(temp*2)
#print(beki)
L = [[] for _ in range(N)]
for i in range(N):
  for t in beki:
    now = t-A[i]
    if A[i] == now and dic[now] >2:
      L[i].append(now)
    elif A[i] != now and now>0 and now in dic:
      L[i].append(now)
  L[i].append(A[i]) #自分を足しておく

L.sort(key=len)
#print(L)
#print(dic)
ans = 0
for i in range(N):
  now = L[i].pop()
  #print(L[i])
  for num in L[i]:
    if num in dic:
      if num == now and dic[now] > 1:
        dic[num] -=2
        ans += 1
        continue
      elif num != now and dic[num] > 0 and dic[now] > 0:
        dic[num] -= 1
        dic[now] -= 1
        ans += 1
        continue

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n = getN()
    nums = getList()
    stock = defaultdict(int)
    for num in nums:
        stock[num] += 1
    ans = 0
    for i in range(32, -1, -1):
        tgt = 2 ** i
        # print(tgt)
        d = defaultdict(int)
        for num in nums:
            d[num - tgt] += 1
        # print(d)
        for dk in d.keys():
            if dk == 0:
                a = stock[dk] // 2
                ans += a
                stock[dk] -= 2 * a
            elif dk > 0:
                # print(dk)
                if -dk in d:
                    # print("--")
                    # print(stock, dk, tgt)
                    a = min(stock[dk + tgt], stock[-dk + tgt])
                    ans += a
                    stock[dk + tgt] -= a
                    stock[-dk + tgt] -= a


    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n = getN()
    nums = getList()
    stock = defaultdict(int)
    for num in nums:
        stock[num] += 1
    ans = 0
    for i in range(10, -1, -1):
        tgt = 2 ** i
        # print(tgt)
        d = defaultdict(int)
        for num in nums:
            d[num - tgt] += 1
        # print(d)
        for dk in d.keys():
            if dk == 0:
                a = stock[dk] // 2
                ans += a
                stock[dk] -= 2 * a
            elif dk > 0:
                # print(dk)
                if -dk in d:
                    # print("--")
                    # print(stock, dk, tgt)
                    a = min(stock[dk + tgt], stock[-dk + tgt])
                    ans += a
                    stock[dk + tgt] -= a
                    stock[-dk + tgt] -= a


    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

N = int(input())
A = list(map(int,input().split()))
B = set(A)
for i in A:
  dic[i] +=1

beki = [1]
for i in range(30): #30に変更
  temp = beki[-1]
  beki.append(temp*2)
#print(beki)
L = [[] for _ in range(N)]
for i in range(N):
  for t in beki:
    now = t-A[i]
    if now>0 and now != A[i] and now in B:
      L[i].append(now)
  L[i].append(A[i]) #自分を足しておく

L.sort(key=len)
#print(L)
ans = 0
for i in range(N):
  now = L[i].pop()
  for num in L[i]:
    if num in dic and dic[now] > 0 and dic[num] > 0:
      dic[now] -= 1
      dic[num] -= 1
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
#N = 2
#A = [4,4,12,13]

A.sort()
cnt = Counter(A)
keys = sorted(cnt.keys(), reverse=True)

ans = 0
for a in keys:
    p = len(bin(a)) - 2
    t = (1 << p) - a
    if a < t:
        break
    if a == t:
        ans += cnt[a]//2
        break
    if t in cnt:
        d = min(cnt[t],cnt[a])
        ans += d
        cnt[t] -= d
        cnt[a] -= d
print(ans)

Submission status: Wrong Answer

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

A.sort()
cnt = Counter(A)
keys = sorted(cnt.keys(), reverse=True)

ans = 0
for a in keys:
    p = len(bin(a)) - 2
    t = (1 << p) - a
    if a < t:
        break
    if a == t:
        ans += cnt[a]//2
        break
    if t in keys:
        d = max(cnt[t],cnt[a])
        ans += d
        cnt[t] -= d
        cnt [a] -= d
print(ans)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = list(map(int,ipt().split()))
    a.sort(reverse=True)
    d = defaultdict(int)
    ans = 0
    for i in a:
        if d[i]:
            ans += 1
        else:
            nl = len(format(i,"b"))
            d[(i^(2**(nl)-1))+1] += 1

    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = list(map(int,ipt().split()))
    a.sort(reverse=True)
    d = defaultdict(int)
    ans = 0
    for i in a:
        if d[i]:
            ans += 1
        nl = len(format(i,"b"))
        d[(i^(2**(nl)-1))+1] += 1

    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))

ans=0
howmuch=[[] for i in range(30)]
for num in lists:
    c=0
    while num%2==0:
        num=num//2
        c+=1
    howmuch[c].append(num)
for i in range(30):
    if len(howmuch[i])<=1:
        pass
    else:
        dic=dict(Counter(howmuch[i]))
        for some in howmuch[i]:
            for j in range(1,30):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

def main():
    n = int(input())
    A = list(map(int,input().split()))

    A.sort()
    ch = [True] * n


    beki = []
    c = 1
    for _ in range(31):
        beki.append(c)
        c *= 2

    # print(beki)

    ans = 0
    for i in range(n-1,-1,-1):
        if ch[i]:
            a = A[i]
            j = bisect.bisect_left(beki,a)
            t = beki[j] - a
            k = bisect.bisect_left(A[:i],t)
            if A[k] == t:
                ch[k] = False
                ans += 1

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

def main():
    MOD = 10**9+7
    n = int(input())
    A = list(map(int,input().split()))

    A.sort()
    ch = [True] * n


    beki = []
    c = 1
    for _ in range(31):
        beki.append(c)
        c *= 2

    # print(beki)

    ans = 0
    for i in range(n-1,-1,-1):
        a = A[i]
        j = bisect.bisect_left(beki,a)
        t = beki[j] - a
        k = bisect.bisect_left(A[:i],t)
        if A[k] == t:
            # print(a,beki[j],t)
            ans += 1

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()

    power = []
    c = 1
    for _ in range(31):
        power.append(c)
        c *= 2

    count = 0
    dp = [True] * n
    for ｋ in range(n-1,0,-1):
        if dp[k] == True:
            i = bisect.bisect_left(power,A[k])
            t = power[i]
            j = bisect.bisect_left(A[:k],t-A[k])
            if A[j] == t-A[k] and dp[j] == True:
                count += 1
                dp[j] = False
        # print(count)

    print(count)

main()

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()

    power = []
    c = 1
    for _ in range(31):
        power.append(c)
        c *= 2

    count = 0
    dp = [True] * n
    for ｋ in range(n-1,0,-1):
        if dp[k] == True:
            i = bisect.bisect_left(power,A[k])
            t = power[i]
            j = bisect.bisect_left(A[:k],t-A[k])
            if A[j] == t-A[k]:
                count += 1
                dp[j] = False
        # print(count)

    print(count)

main()

Submission status: Wrong Answer

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

from collections import defaultdict
d = defaultdict(int)

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

ans=0
for num in sorted(d,reverse=True):
    while d[num]>=1:
        d[num]-=1

        now=1
        while now<=num:
            now*=2

        cand = now - num
        print(num,cand)

        if d[cand]>=1:
            d[cand]-=1
            ans+=1
        else:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())),reverse=1)
from collections import Counter as co
d=co(l)
ans=0
for i in l:
    x=pow(2,i.bit_length())-i
    if d[i]and x in d and d[x]:
        if x!=i:d[x]-=1;ans+=1
        elif d[i]>=2:d[i]-=2;ans+=1
print(ans)

Submission status: Wrong Answer

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

nibeki = [2**(i+1) for i in range(31)]

ALL = set()
c = 0
for a in A:
    if a in ALL:
        c += 1
    pair = set([j -a for j in nibeki if j-a > 0])
    ALL = ALL|pair

print(c)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from bisect import bisect_right

pow2 = [2]
for i in range(29):
  pow2.append(pow2[-1]*2)

N = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
  if a in d:
    d[a] += 1
  else:
    d[a] = 1

A = [-a for a in A]
heapify(A)
ans = 0
while A:
  a = - heappop(A)
  if d[a] == 0:
    continue
  pair = pow2[bisect_right(pow2, a)] - a
  if pair in d and d[pair] > 0:
    ans += 1
    d[pair] -= 1
    d[a] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from bisect import bisect_left

pow2 = [2]
for i in range(29):
  pow2.append(pow2[-1]*2)

N = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
  if a in d:
    d[a] += 1
  else:
    d[a] = 1

A = [-a for a in A]
heapify(A)
ans = 0
while A:
  a = - heappop(A)
  if d[a] == 0:
    continue
  pair = pow2[bisect_left(pow2, a)] - a
  if pair in d and d[pair] > 0:
    ans += 1
    d[pair] -= 1
    d[a] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
pow2 = [2]
for i in range(29):
  pow2.append(pow2[-1]*2)

pow2 = pow2[::-1]
d = {}
ans = 0
for a in A:
  flag = True
  for p in pow2:
    pair = p - a
    if pair <= 0:
      break
    if pair in d and d[pair] > 0:
      ans += 1
      flag = False
      d[pair] -= 1
      break
  if flag:
    if a in d:
      d[a] += 1
    else:
      d[a] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
cnt=0
maxa=max(a)
while 2**cnt<2*maxa:
    cnt+=1
    # print(2**cnt)

lsta=[0]*n
ans=0
for i in range(1,cnt+1):
    dic=defaultdict(list)
    for j in range(n):
        if 2**i>a[j] and lsta[j]==0:
            if dic[a[j]]!=[]:
                lsta[j]=-1
                lsta[dic[a[j]].pop()]=-1
                ans+=1
            else:
                dic[2**i-a[j]].append(j)
    # print(dic)
# print(lsta)
# ans=-sum(lsta)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import log2

def find(x):
    f = 2**(int(log2(x))+1)-x
    if f <= x:
        return f
    return 0

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
c = Counter(a)
ans = 0

for i in range(n):
    f = find(a[i])
    if f == a[i]:
        if c[f] > 1:
            c[f] -= 2
            ans += 1
    elif c[f] > 0:
        c[f] -= 1
        c[a[i]] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import log2

def find(x):
    return 2**(int(log2(x))+1)-x

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
c = Counter(a)
ans = 0

for i in range(n):
    f = find(a[i])
    if f == a[i]:
        if c[f] > 1:
            c[f] -= 2
            ans += 1
    elif c[f] > 0:
        c[f] -= 1
        c[a[i]] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import Counter

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

power = 1
powers = [1]
while power <= 10 ** 9:
    power *= 2
    powers.append(power)

a.sort()
c = Counter(a)

ans = 0
for e in a[::-1]:
    i = bisect_left(powers, e)
    target = powers[i]

    if target == 2 * e:
        if c[e] >= 2:
            c[e] -= 2
            ans += 1

    else:
        if c[e] and c[target-e]:
            c[e] -= 1
            c[target-e] -= 1
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
n = 1
m = max(A)
while n <= 2 * m:
    n *= 2
n //= 2
ans = 0
while n > 0:
    for a in A:
        if cnt[a] == 0:
            continue
        b = n - a
        if cnt[b] > 0:
            c = min(cnt[a], cnt[b])
            cnt[a] -= c
            cnt[b] -= c
            ans += c
    n //= 2
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)
cnt = Counter(a)
ans = 0

def make(x):
    num = 1
    while num <= x:
        num *= 2
    return num

for i in range(n):
    cnt[a[i]] -= 1
    x = make(a[i])
    if cnt[x - a[i]] > 0:
        ans += 1
        cnt[x - a[i]] -= 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)
cnt = Counter(a)
ans = 0

def make(x):
    num = 1
    while num < x:
        num *= 2
    return num

for i in range(n):
    cnt[a[i]] -= 1
    x = make(a[i])
    if cnt[x - a[i]] > 0:
        ans += 1
        cnt[x - a[i]] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,*A = map(int, open(0).read().split())
Cnt = Counter(A)
m = 2**31
ans = 0
for i in range(31,0,-1):
  for k in Cnt.keys():
    if Cnt[k]==0:
      continue
    if k==m-k:
      if Cnt[m-k]>1:
        Cnt[k] -= 2
        ans += 1
    else:
      if Cnt[m-k]>0:
        Cnt[k] -= 1
        Cnt[m-k] -= 1
        ans += 1
  m >>= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,*A = map(int, open(0).read().split())
Cnt = Counter(A)
m = 2**31
ans = 0
for i in range(31,0,-1):
  for k in Cnt.keys():
    if Cnt[k]==0:
      continue
    if Cnt[m-k]>0:
      Cnt[k] -= 1
      Cnt[m-k] -= 1
      ans += 1
  m >>= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
d={}
for i in A:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
a=0
for i in range(1,31):
    t=2**i
    if t//2 in d:
        a+=d[t//2]*(d[t//2]-1)//2
    for n,v in d.items():
        if n>=t//2:
            break
        if t-n in d:
            a+=v*d[t-n]
print(a)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=sorted(list(map(int,input().split())))
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    find = twosum(i)
    if d[i] <= 0:
        continue
    d[i] -= 1
    if d[find] <= 0:
        continue
    ans += 1
    d[i] -= 1
    d[find] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=sorted(list(map(int,input().split())))
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    find = twosum(i)
    if d[find] <= 0 or d[i] <= 0:
        continue
    ans += 1
    d[i] -= 1
    d[find] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=sorted(list(map(int,input().split())))
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    if not d[i] > 0:
        continue
    find = twosum(i)
    if not d[find] > 0:
        continue
    ans += 1
    d[i] -= 1
    d[find] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=list(map(int,input().split()))
a.sort()
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    if d[i] <= 0:
        continue
    find = twosum(i)
    if d[find] <= 0:
        continue
    ans += 1
    d[i] -= 1
    d[find] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import defaultdict
dic = defaultdict(int)
for x in a:
    dic[x] += 1
ans = 0
for num in a[::-1]:
    if dic[num] <= 0:
        continue
    nerai = 1
    while num>=nerai:
        nerai *= 2
    nerai -= num
    if dic[nerai] <= 0:
        continue
    ans += 1
    dic[num] -= 1
    dic[nerai] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import defaultdict
dic = defaultdict(int)
for x in a:
    dic[x] += 1
ans = 0
for num in a[::-1]:
    if dic[num] <= 0:
        continue
    nerai = 1
    numcalc = num
    while numcalc:
        numcalc//=2
        nerai *= 2
    num = nerai - num
    if dic[num] <= 0:
        continue
    ans += 1
    dic[num] -= 1
    dic[nerai-num] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import defaultdict
dic = defaultdict(int)
for x in a:
    dic[x] += 1
ans = 0
for num in a[::-1]:
    if dic[num] <= 0:
        continue
    nerai = 1
    numcalc = num - 1
    while numcalc:
        numcalc//=2
        nerai *= 2
    num = nerai - num
    if dic[num] <= 0:
        continue
    ans += 1
    dic[num] -= 1
    dic[nerai-num] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import defaultdict
dic = defaultdict(int)
for x in a:
    dic[x] += 1
ans = 0
for num in a[::-1]:
    if dic[num] <= 0:
        continue
    nerai = 1
    numcalc = num - 1
    while numcalc:
        numcalc//=2
        nerai *= 2
    num = nerai - num
    if not num in dic or dic[num] == 0:
        continue
    ans += 1
    dic[num] -= 1
    dic[nerai-num] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
dic = {}
for x in a:
    if not x in dic:
        dic[x] = 1
    else:
        dic[x] += 1
ans = 0
for num in a[::-1]:
    if dic[num] <= 0:
        continue
    nerai = 1
    numcalc = num - 1
    while numcalc:
        numcalc//=2
        nerai *= 2
    num = nerai - num
    if not num in dic or dic[num] == 0:
        continue
    ans += 1
    dic[num] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
dic = {}
for x in a:
    if not x in dic:
        dic[x] = 1
    else:
        dic[x] += 1
dic_sorted = sorted(dic.items(),reverse = True)
ans = 0
for num, kosu in dic_sorted:
    nerai = 1
    numcalc = num - 1
    while numcalc:
        numcalc//=2
        nerai *= 2
    num = nerai - num
    if not num in dic or dic[num] == 0:
        continue
    ans += min(kosu,dic[num])
    dic[num] -= min(kosu,dic[num])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n = int(input())
a = sorted(list(map(int, input().split())))
d = defaultdict(int)
for i in a:
  d[i] += 1
ans = 0
for i in a[::-1]:
  d[i] -= 1
  find = twosum(i)
  if d[find] > 0 and d[i] >= 0:
    ans += 1
    d[i] -= 1
    d[find] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def twosum(n):
  now = 2
  while n > now:
    now *= 2
  return now - n
n = int(input())
a = sorted(list(map(int, input().split())))
d = defaultdict(int)
for i in a:
  d[i] += 1
ans = 0
for i in a[::-1]:
  find = twosum(i)
  if d[find] > 0 and d[i] > 0:
    ans += 1
    d[i] -= 1
    d[find] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def twosum(n):
  now = 2
  while n > now:
    now *= 2
  return now - n
n = int(input())
a = sorted(list(map(int, input().split())))
d = defaultdict(int)
for i in a:
  d[i] += 1
ans = 0
for i in a[::-1]:
  d[i] -= 1
  find = twosum(i)
  if d[find] > 0:
    ans += 1
    d[find] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def get_smallest_power_of_2_over_N(N):
    i=2
    while i<N:
        i*=2
    return i

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


A = sorted(A)

ans=0
D=Counter(A)

for i in reversed(range(N)):
    pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
    if D[A[i]]<=0:
        continue
    if pair_val==A[i] and D[pair_val]>=2 or pair_val!=A[i] and  D[pair_val]>=1:
        ans+=1
        D[pair_val]-=1
        D[A[i]]-=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def get_smallest_power_of_2_over_N(N):
    i=2
    while i<N:
        i*=2
    return i

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


A = sorted(A)

ans=0
D=Counter(A)

for i in reversed(range(N)):
    pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
    if pair_val==A[i] and D[pair_val]>1 or pair_val!=A[i] and  D[pair_val]>0:
        ans+=1
        D[pair_val]-=1
        D[A[i]]-=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def get_smallest_power_of_2_over_N(N):
    i=2
    while i<N:
        i*=2
    return i

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


A = sorted(A)

ans=0
D=defaultdict(int)

for a in A:
    D[a]+=1

for i in reversed(range(N)):
    if D[A[i]]<=0:
        continue
    else:
        pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
        if pair_val==A[i] and D[pair_val]>1 or D[pair_val]>0:
            ans+=1
            D[pair_val]-=1
            D[A[i]]-=1

print(ans)