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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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
  while True:
    if t not in d or d[t] == 0:
      break
    if a == t and d[a] == 1:
      break
    result += 1
    d[a] -= 1
    d[t] -= 1
    if a not in d or d[a] == 0:
      break
print(result)

Submission status: Accepted

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:
    continue
  t = power_of_two[bisect_right(power_of_two, a)] - a
  while True:
    if t not in d:
      break
    if a == t and d[a] == 1:
      break
    result += 1
    if d[a] == 1:
      del d[a]
    else:
      d[a] -= 1
    if d[t] == 1:
      del d[t]
    else:
      d[t] -= 1
    if a not in d:
      break
print(result)

Submission status: Accepted

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
amax = max(d.keys())
t = 1
power_of_two = []
while t < 2 * amax:
  t *= 2
  power_of_two.append(t)
result = 0
keys = list(sorted(d.keys(), reverse = True))
for a in keys:
  if a not in d:
    continue
  t = power_of_two[bisect_right(power_of_two, a)] - a
  while True:
    if t not in d:
      break
    if a == t and d[a] == 1:
      break
    result += 1
    if d[a] == 1:
      del d[a]
    else:
      d[a] -= 1
    if d[t] == 1:
      del d[t]
    else:
      d[t] -= 1
    if a not in d:
      break
print(result)

Submission status: Accepted

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
amax = max(d.keys())
t = 1
valids = []
while t < 2 * amax:
  t *= 2
  valids.append(t)
result = 0
keys = list(sorted(d.keys(), reverse = True))
for a in keys:
  if a not in d:
    continue
  t = valids[bisect_right(valids, a)] - a
  while True:
    if t not in d:
      break
    if a == t and d[a] == 1:
      break
    result += 1
    if d[a] == 1:
      del d[a]
    else:
      d[a] -= 1
    if d[t] == 1:
      del d[t]
    else:
      d[t] -= 1
    if a not in d:
      break
print(result)

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
d = {}
amax = 0
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
amax = max(d.keys())
t = 1
valids = []
while t < 2 * amax:
  t *= 2
  valids.append(t)
result = 0
while True:
  prev = result
  keys = list(sorted(d.keys(), reverse = True))
  for x in keys:
    if x not in d:
      continue
    t = valids[bisect_right(valids, x)] - x
    while True:
      if t not in d:
        break
      if x == t and d[x] == 1:
        break
      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 x not in d:
        break
  if prev == result:
    break
print(result)

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
d = {}
amax = 0
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
amax = max(d.keys())
t = 1
valids = []
while t < 2 * amax:
  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
    while True:
      if t not in d:
        break
      if x == t and d[x] == 1:
        break
      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 x not in d:
        break
  if prev == result:
    break
print(result)

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
d = {}
amax = 0
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
  amax = max(amax, a)
t = 1
valids = []
while t < 2 * amax:
  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
    while True:
      if t not in d:
        break
      if x == t and d[x] == 1:
        break
      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 x not in d:
        break
  if prev == result:
    break
print(result)

Submission status: Accepted

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
    while True:
      if t not in d:
        break
      if x == t and d[x] == 1:
        break
      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 x not in d:
        break
  if prev == result:
    break
print(result)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
*A, = map(int,input().split())
B = {}
for a in A:B[a] = B.get(a,0) + 1
B = sorted(map(list,B.items()))
bl = bisect.bisect_left

ans = 0
while B:
    b,n = B.pop()
    c = (1<<(len(bin(b))-2)) - b
    if c==b :
        ans += n//2
        continue
    i = bl(B,[c,0])
    if i>=len(B): continue
    if B[i][0] == c:
        m = min(n,B[i][1])
        ans += m
        B[i][1] -= m
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

a.sort()
c = Counter(a)

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

Submission status: Accepted

Solution code:
import bisect

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

aa.sort()

a = [aa[0]]
b = [1]

for i in range(1,n):
    if a[-1]==aa[i]:
        b[-1]+=1
    else:
        a.append(aa[i])
        b.append(1)

ans = 0

for i in range(len(a)):
    while b[-i-1]!=0:
        c = 2**(len(bin(a[-i-1]))-2)-a[-i-1]
        d = bisect.bisect_left(a,c)
        if a[d]==c:
            if b[d]>1:
                ans += 1
                b[-i-1] -= 1
                b[d] -= 1
            elif b[d]==1 and a[d]!=a[-i-1]:
                ans += 1
                b[-i-1] -= 1
                b[d] -= 1
            else:
                break
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
import bisect
import itertools
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
d = defaultdict(int)

for key, value in itertools.groupby(a):
    d[key] = len(list(value))

ans = 0
for i in range(N):
    now = a[i]
    if d[now] > 0:
        pair = 2**((now).bit_length()) - now
        if now == pair:
            if d[pair] >= 2:
                ans += 1
                d[pair] -= 2
        elif d[pair] > 0:
            ans += 1
            d[now] -= 1
            d[pair] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A.sort()
d = defaultdict(int)
for a in A:
    d[a] += 1

cnt = 0
for a in reversed(A):
    if d[a] > 0:
        d[a] -= 1
        pair = (1 << a.bit_length()) - a
        if d[pair] > 0:
            cnt += 1
            d[pair] -= 1
print(cnt)

Submission status: Accepted

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

from collections import Counter

# 最大値は相手が決まる -> greedy

N = int(input())
A = [int(x) for x in input().split()]

counter = Counter(A)
A.sort()

answer = 0
for x in A[::-1]:
    while counter[x] > 0:
        counter[x] -= 1
        target = (1 << x.bit_length()) - x
        if counter[target] > 0:
            counter[target] -= 1
            answer += 1

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
dic = defaultdict(int)
for a in A:
    dic[a] += 1

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
dic={}
for val in arr:
  if val not in dic:
    dic[val]=1
  else:
    dic[val]+=1
arr2=[]
for i in range(40):
  arr2.append(2**i)
ans=0
for val in arr:
  pos=bisect_left(arr2,val)
  if val==arr2[pos]:
    persuit=arr2[pos+1]
  else:
    persuit=arr2[pos]
  if persuit-val==val:
    if val in dic:
      if dic[val]>=2:
        ans+=1
        dic[val]-=2
        if dic[val]==0:
          del dic[val]
      else:
        continue
    else:
      continue
  else:
    if val in dic and persuit-val in dic:
      ans+=1
      dic[val]-=1
      if dic[val]==0:
        del dic[val]
      dic[persuit-val]-=1
      if dic[persuit-val]==0:
        del dic[persuit-val]
    else:
      continue
print(ans)

Submission status: Accepted

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



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

    M = int(10**9)
    bitOfM = M.bit_length()

    X = {}
    Y = [set() for _ in range(bitOfM+1)]

    for a in A:
        if not a in X:
            X[a] = 1
            Y[a.bit_length()].add(a)
        else:
            X[a] += 1

    c = 0

    for i in range(bitOfM, 0, -1):
        P = 1<<(i-1)
        
        if P in X:
            c += X[P]//2

        for a in Y[i]:
            if a == P:
                continue

            a2 = 2*P - a
            if a2 in X:
                c2 = min(X[a], X[a2])
                c += c2
                X[a2] -= c2


    print(c)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import log
N=int(input())
A=list(map(int,input().split()))
dict=defaultdict(int)
for a in A:
    dict[a]+=1
A.sort(reverse=True)
ans=0
for a in A:
    if dict[a]==0:
        continue
    c=int(log(a,2))
    b=~a & ((1<<(c+1)) -1)
    b+=1
    dict[a]-=1
    if dict[b]:
        ans+=1
        dict[b]-=1
    else:
        dict[a]+=1
print(ans)

Submission status: Accepted

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


N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set = []
num = []
a_cur = float('inf')
for a in A:
    if a != a_cur:
        A_set.append(a)
        num.append(1)
        a_cur = a
    else:
        num[-1] += 1

ans = 0
for i in range(len(A_set) - 1, -1, -1):
    if num[i] > 0:
        A_i = A_set[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A_set, comp, 0, i)
        while True:
            if A_set[j] == comp:
                if num[j] > 0:
                    if i != j:
                        ans += min(num[j], num[i])
                        num[j] = max(num[j] - num[i], 0)
                        break
                    elif num[j] >= 2:
                        add = num[j] // 2
                        ans += add
                        num[j] = num[j] % 2
                        break
                    else:
                        break
                else:
                    break
            else:
                break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        inv = pow2[k] - a[i]
        if inv < 0 or inv > a[i]:
            continue
        if inv != a[i]:
            if d[inv] > 0 and d[a[i]] > 0:
                p = min(d[inv], d[a[i]])
                num += p
                d[inv] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)

Submission status: Accepted

Solution code:
import bisect
import collections
def f(n):
  return n.bit_length()
n=int(input())
A=[int(i) for i in input().split()]
D=dict(collections.Counter(A))
C=sorted(list(D.keys()))
ans=0
for i in range(len(C)):
  pair=2**f(C[-(i+1)])-C[-(i+1)]
  k=bisect.bisect_left(C,pair)
  if C[k]==pair:
    if k==len(C)-(i+1):
      ans+=D[pair]//2
      D[pair]%=2
    else:
      aa=min(D[pair],D[C[-(i+1)]])
      ans+=aa
      D[pair]-=aa
      D[C[-(i+1)]]-=aa
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)
max_a = a[-1] 

ans = 0
for item in a[::-1]:
    if ca[item] == 0:
        continue
    for i in range(31, 0, -1):
        inv = (1 << i) - item
        if inv < 0 or inv > max_a:
            continue
        if item == inv:
            if ca[inv] > 1:
                ans += 1 
                ca[inv] -= 2
                break
        else:
            if ca[inv] > 0:
                ans += 1 
                ca[inv] -=1
                ca[item] -=1
                break
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    A = LI()

    MA = defaultdict(int)
    # 目標値をO(1)で見つけるために辞書に格納
    for a in A:
        MA[a] += 1

    key_n = list(MA.keys())
    key_n.sort()
    key_n.reverse()

    res = 0
    p = 30
    for x in key_n:
        # すでにペアを作るために使用してしまっている時はパス
        if not MA[x]:
            continue

        # 残っているボールの中で一番大きな値xを選ぶと，そのボールを使って表せる2べきの値x + yは1つに定まる
        # x + 1 <= x + y < 2x
        # 2べきの比は2であるのに対して，x + 1と2xの比は2未満だから
        while 2 * x < 2 ** p:
            p -= 1

        if x + 1 <= 2 ** p:
            y = 2 ** p - x
            if not MA[y]:
                continue

            if x == y:
                _add = MA[x] // 2
            else:
                _add = min(MA[x], MA[y])

            res += _add
            MA[x] -= _add
            MA[y] -= _add

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
F = sys.stdin
N = int(F.readline().strip("\n"))
A = list(map(int, F.readline().strip("\n").split()))
A.sort()

pair_sum = 0
A_dict = dict()
for a in A:
    if a not in A_dict: A_dict[a] = 1
    else: A_dict[a] += 1

for i in reversed(range(1, N)):
    if A_dict[A[i]] > 0:
        nowA = A[i]
        temp_a = A[i]
        k = 0
        while temp_a > 0:
            temp_a //= 2
            k += 1
        opposite = 2 ** k - nowA
        if opposite in A_dict:
            if opposite == nowA and A_dict[opposite] > 1:
                pair_sum += 1
                A_dict[opposite] -= 2
            elif opposite != nowA and A_dict[opposite] > 0:
                pair_sum += 1
                A_dict[opposite] -= 1
                A_dict[nowA] -= 1

print(pair_sum)

Submission status: Accepted

Solution code:
N  =  int(input())
A  =  list(map(int, input().split()))
A.sort(reverse = True)
d  =  {}
cnt = 0

for a in A:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
    
for i in range(N):
    if d[A[i]] == 0:
        continue
        
    d[A[i]] -= 1
    
    temp = 2 ** A[i].bit_length() - A[i]
    
    if temp in d and d[temp] > 0:
        cnt += 1
        d[temp]  -= 1
        
print(cnt)

Submission status: Accepted

Solution code:
n  =  int(input())
a  =  list(map(int, input().split()))
a.sort(reverse = True)
d  =  {}
count = 0

for x in a:
    if x not in d: d[x] = 0
    d[x] += 1
    
for i in range(len(a)):
    if d[a[i]] == 0:
        continue
        
    d[a[i]] -= 1
    
    y = 2**a[i].bit_length() - a[i]
    
    if y in d and d[y] > 0:
        count += 1
        d[y]  -= 1
        
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import bisect
from collections import defaultdict

N = int(input())
X = sorted(list(map(int, input().rstrip().split(' '))), reverse=False)
included_X = defaultdict(int)
pow_2 = [2**i for i in range(1, 50)]

for x in X:
    included_X[x] += 1

count = 0
for i, x in enumerate(X[::-1]): 
    if included_X[x] > 0:
        index = bisect.bisect_left(pow_2, x + 1)
        if pow_2[index] - x == x:
            if included_X[pow_2[index] - x] > 1:
                included_X[pow_2[index] - x] -= 2
                count += 1
        else:
            if included_X[pow_2[index] - x] > 0:
                included_X[pow_2[index] - x] -= 1
                included_X[x] -= 1
                count += 1
         
print(count)

Submission status: Accepted

Solution code:
from collections import Counter

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

# 最大の整数が書かれているボールから順に貪欲的にペアを作成する。
C = Counter(A)
ans = 0
for m in sorted(C, reverse=True):
    p = (1 << m.bit_length()) - m
    if m == p:
        ans += C[m] // 2
    elif p in C:
        k = min(C[m], C[p])
        ans += k
        C[p] -= k

# 出力
print(ans)

Submission status: Accepted

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

ans = 0
for a in sa:
    p = 2**(len(bin(a))-2)
    rem = p - a
    if a == rem:
        v = ctr[a] // 2
    else:
        v = min(ctr[a], ctr[rem])
    ans += v
    ctr[a] -= v
    ctr[rem] -= v
print(ans)

Submission status: Accepted

Solution code:
n  =  int(input())
a  =  list(map(int, input().split()))
a.sort(reverse = True)
d  =  {}
count = 0

for x in a:
    if x not in d: d[x] = 0
    d[x] += 1
    
for i in range(len(a)):
    if d[a[i]] == 0:continue
        
    d[a[i]] -= 1
    
    y = 2**a[i].bit_length() - a[i]
    
    if y in d and d[y] > 0:
        count += 1
        d[y]  -= 1
        
print(count)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
from collections import Counter
dic = Counter(a)
ans = 0
for k in range(len(a)-1,-1,-1):
    if dic[a[k]]==0:
        continue
    dic[a[k]] -= 1
    t = 2**a[k].bit_length()-a[k]
    if dic[t]:
        dic[t] -= 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

def binum(num):
	number_len = len(bin(num))-2
	f = 2**number_len -1
	return (num^f)+1

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

while len(A) > 0:
	k = A.pop()
	if len(A) == 0:
		break
	if int(k) != k:
		continue
	x = binum(k)
	if x > A[-1]:
		continue
	if A[bisect.bisect_left(A,x)] == x:
		A[bisect.bisect_left(A,x)] -= 0.5
		cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import bisect

def number(num):
  #0bのぶんを引きます
  number_len = len(bin(num))-2
  #numと同じ桁数で各桁が全て1である数を求めます。
  f = 2**number_len - 1
  #排他的論理和をとって1を足したものを返します
  return (num^f)+1

n=int(input())
line=list(map(int,input().split()))
#sortを忘れないようにしてください
line.sort()

count=0

while len(line)>0:
  #最後の数を取ってくる(最後尾なのでO(1)で済む)
  k=line.pop()
  #lineに要素が存在しないならループから抜ける
  if len(line)==0:
    break
  #整数でないならその数は存在しないと同義なので処理を行わない
  if int(k) != k:
    continue
  x=number(k)
  #もしlineの最大値よりxが大きければ条件を満たすxは存在しないので処理を行わない
  if x>line[-1]:
    continue
  #その数が存在するならば、その数をlistから消去して、カウントする
  if line[bisect.bisect_left(line,x)]==x:
    #0.5を引くことでremoveの代わりとする
    line[bisect.bisect_left(line,x)] -= 0.5
    count+=1

print(count)

Submission status: Accepted

Solution code:
import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  k=number.pop()
  if len(number)==0:
    break
  if k==int(k):
    x=reversed_num(k)+1
    y=bisect.bisect_left(number,x)
    if x>number[-1]:
      y-=1
    if number[y] ==x:
      number[y]-=0.5
      count+=1
print(count)

Submission status: Accepted

Solution code:
import sys
import collections

def solve():
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A = sorted(A, reverse=True)
    maxA = A[0]
    cntA = collections.Counter(A)

    ans = 0
    for a in A:
        if cntA[a] == 0:
            continue
        cntA[a] -= 1
        #print('a =',a)
        b = (1 << a.bit_length()) - a
        if cntA[b] > 0:
            cntA[b] -= 1
            ans += 1
    return ans

print(solve())

#  1  1  7   9
#     3  5   11
#        13
#     15
#  2  6  10
#     14
#  4  4  12
#
#  8

Submission status: Accepted

Solution code:
import bisect
inpl = lambda: list(map(int,input().split()))
_ = int(input())
A = sorted(inpl())
Anlist = []
ap = 0
for a in A:
  if a > ap:
    Anlist.append([a,1])
    ap = a
  else:
    Anlist[-1][1] += 1

A = [ a for a,n in Anlist ]
N = len(Anlist)

ans = 0
for i in range(1,N+1):
  if Anlist[-i][1] == 0:
    continue
  
  p = len(bin(A[-i]))-3
  B = (1 << (p+1)) - A[-i]
  if A[-i] == B:
    ans += Anlist[-i][1]//2
  else:
    m = bisect.bisect_left(A,B,0,N-i)
    if m < N-i and A[m] == B:
      pairs = min(Anlist[m][1],Anlist[-i][1])
      ans += pairs
      Anlist[m][1] -= pairs

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    if len(A) < 2: break
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
                    
print(ans)

Submission status: Accepted

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    A = []
    input_raw = read_func().strip().split()
    for i in range(N):
        A.append(int(input_raw[i]))

    pair_count = 0
    already_set = set([])
    for t in range(31, 0, -1):
        x = 2**t
        count_dict = {}
        for i in range(N):
            if i in already_set:
                continue
            if x - A[i] <= 0:
                continue
            if x - A[i] in count_dict and len(count_dict[x - A[i]]) > 0:
                pair_count += 1
                j = count_dict[x - A[i]].pop()
                already_set.add(i)
                already_set.add(j)
            else:
                if A[i] not in count_dict:
                    count_dict[A[i]] = [i]
                else:
                    count_dict[A[i]].append(i)

    print pair_count

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A_arr = sorted(A_arr, reverse=True)
C_arr = Counter(A_arr)

count = 0
for i in range(N):
    v_max = A_arr[i]
    if C_arr[v_max] == 0:
        continue
    C_arr[v_max] -= 1
    v_pair = 2**v_max.bit_length() - v_max
    if C_arr[v_pair] > 0:
        C_arr[v_pair] -= 1
        count += 1
    else:
        pass

print(count)

Submission status: Accepted

Solution code:
import collections

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


def func1(a, r, rnext):
    p = a.popleft()
    q = a.pop()
    ans = 0
    a1 = collections.deque()
    while True:
        if p + q == r:
            ans += 1
            try:
                p = a.popleft()
            except:
                break
            try:
                q = a.pop()
            except:
                if p < rnext:
                    a1.append(p)
                break
        elif p + q > r:
            try:
                q = a.pop()
            except:
                if p < rnext:
                    a1.append(p)
                break
        else:
            a1.append(p)
            try:
                p = a.popleft()
            except:
                if q < rnext:
                    a1.append(q)
                break
    return ans, a1


if N == 1:
    print(0)
    exit(0)
t = int.bit_length(A[-1] + A[-2])
r = 2 ** t
rnext = 2 ** (t - 1)
anser = 0
a = A

while True:
    ans, a1 = func1(a, r, rnext)
    anser += ans
    if len(a1) < 2:
        break
    a = a1
    t -= 1
    r = rnext
    rnext = 2 ** (t - 1)

print(anser)

Submission status: Accepted

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 x in a:
    if c[x] == 0:
        continue
    temp = (1 << x.bit_length()) - x
    c[x] -= 1
    if temp in c.keys():
        if c[temp] > 0:
            c[temp] -= 1
            ans += 1

print(ans)

Submission status: Accepted

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

A.sort(reverse=True)

dic = {}
for i in range(N):
    if A[i] in dic:
        dic[A[i]] += 1
    else:
        dic[A[i]] = 1
 
res = 0
for i in range(N):
    if A[i] in dic:
        n = 0
        tmp = A[i]
        while True:
            if tmp == 0:
                break
            tmp //= 2
            n += 1

        if 2 ** n - A[i] in dic:
            if 2 ** n - A[i] == A[i] and dic[A[i]] < 2:
                pass
            else:
                res += 1
                dic[2 ** n - A[i]] -= 1
                if dic[2 ** n - A[i]] == 0:
                    dic.pop(2 ** n - A[i])

        dic[A[i]] -= 1
        if dic[A[i]] == 0:
            dic.pop(A[i])
        
print(res)

Submission status: Accepted

Solution code:
def hersCode(L, n):
  ok = len(L) - 1
  ng = 0
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] > n:
      ok = mid
    else:
      ng = mid
  return ok

def hersCode2(L, n):
  ok = 0
  ng = len(L)
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] < n:
      ok = mid
    elif L[mid] == n:
      if TF[mid]:
        ok = mid
      else:
        ng = mid
    else:
      ng = mid
  return ok

N = int(input())

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

D = [pow(2, i) for i in range(31)]
TF = [True for i in range(N + 1)]
Ans = 0
A = [-1e11] + A
for i in range(len(A) - 1, 1, -1):
  if TF[i]:
    k = D[hersCode(D, A[-1])] - A[-1]
    del A[-1]
    t = hersCode2(A, k)
    if A[t] == k:
      TF[t] = False
      Ans += 1
  else:
    del A[-1]

print(Ans)