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 collections import Counter
n = int(input())
A = list(map(int,input().split()))
A.sort()
C = Counter(A)
ans = 0
for i in range(n-1,-1,-1):
    temp = A[i]
    beki = 1
    if C[temp] == 0:
        continue
    while beki <= temp:
        beki *= 2
    counterpart = beki-temp
    if C[counterpart] > 0 and C[temp] > 0 and counterpart != temp:
        C[counterpart] -= 1
        C[temp] -= 1
        ans += 1
    elif counterpart == temp and C[counterpart] > 1:
        C[counterpart] -= 2
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
A.sort()
C = Counter(A)
ans = 0
for i in range(n-1,-1,-1):
    temp = A[i]
    beki = 1
    while beki <= temp:
        beki *= 2
    counterpart = beki-temp
    if C[counterpart] > 0 and C[temp] > 0 and counterpart != temp:
        C[counterpart] -= 1
        C[temp] -= 1
        ans += 1
    elif counterpart == temp and C[counterpart] > 1:
        C[counterpart] -= 2
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import *
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()
C = Counter(A)
ans = 0
for i in range(N):
    a = A[N-i-1]
    if C[a] == 0:
        continue
    b = pow(2, a.bit_length())
    if C[b-a]-((a<<1) == b) > 0:
        C[a] -= 1
        C[b-a] -= 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

data=defaultdict(int)
for i in range(0,N):
    data[A[i]]+=1

A=[-A[i] for i in range(0,N)]
heapq.heapify(A)
count=0
while A:
    x=-heapq.heappop(A)
    if data[x]!=0:
        data[x]-=1
        y=2**(len(bin(x))-2)-x
        if data[y]!=0:
            data[y]-=1
            count+=1

print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LI()
    a.sort()
    d = defaultdict(int)
    for ai in a:
        d[ai] += 1
    ans = 0
    for j in range(n - 1, -1, -1):
        i = 0
        aj = a[j]
        while aj:
            aj >>= 1
            i += 1
        m = 1 << i
        if d[a[j]]:
            if m - a[j] == a[j]:
                x = d[a[j]]
                d[a[j]] -= x
                ans += x // 2
            else:
                x = m - a[j]
                if bisect_right(a, x) - bisect_left(a, x) and d[x]:
                    x = d[a[j]]
                    y = d[m - a[j]]
                    d[a[j]] -= min(x, y)
                    d[m - a[j]] -= min(x, y)
                    ans += min(x, y)

    print(ans)

    return


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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
count = Counter(a)
a.sort(reverse=True)
ans = 0
for num in a:
    if count[num] == 0:
        continue
    else:
        #numより大きい2のべき乗の数
        p = 2 ** num.bit_length()
        if p - num == num:
            if count[p - num] > 1:
                sub = count[num] // 2
                ans += sub
                count[num] -= sub * 2
        else:
            if count[p - num] > 0:
                sub = min(count[p - num], count[num])
                ans += sub
                count[p-num] -= sub
                count[num] -= sub
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

A.sort(reverse = True)
cnt = Counter(A)

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

    # aより大きい最小の2のべき乗
    p = 2 ** a.bit_length()
    if cnt[p - a]:
        if a == p - a:
            if cnt[a] >= 2:
                ans += 1
                cnt[a] -= 2
        else:
            ans += 1
            cnt[p - a] -= 1
            cnt[a] -= 1

print(ans)

Submission status: Accepted

Solution code:
## 貪欲
# 大きい数xとすると、2べきになるyは一意に定まる
# x < x + y < = 2*x
from collections import defaultdict

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

cnt = 0
for a in As:
    if d[a] == 0:continue
    d[a] -= 1
    n = 0
    while 2**n <= a:
        n += 1
    p = 2**n - a
    if d[p] > 0:
        cnt += 1
        d[p] -= 1

print(cnt)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def f(x):
    pow_2 = 1
    while pow_2 <= x:
        pow_2*=2
    return pow_2-x
def main():
    N=I()
    A=sorted(LI())
    C = Counter(A)
    ans = 0
    for a in A[::-1]:
        pair = f(a)

        if(a!=pair and C[a] and C[pair]):
            ans += 1
            C[a]-=1
            C[pair]-=1
        if(a==pair and C[a]>=2):
            ans += 1
            C[a]-=2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
import collections
d=collections.defaultdict(int)
for i in l:
    d[i]+=1
l.sort(reverse=True)
ans=0
for i in l:
    if d[i]>0:
        d[i]-=1
        if d[2**i.bit_length()-i]>0:
            ans+=1
            d[2**i.bit_length()-i]-=1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from bisect import bisect_right

n = int(input())
a = [int(x) for x in input().split()]
a = sorted(a)

ans = 0
visited = [False]*n

while a:
    s = a.pop()
    if visited.pop():
        continue
    m = 1
    while m <= s:
        m *= 2
    r = bisect_right(a, m-s)
    l = bisect_left(a, m-s)
    for x in range(l, r)[::-1]:
        if not visited[x]:
            visited[x] = True
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0

while A:
    a = A.pop()
    if cnt[a] <= 0:
        continue
    cnt[a] -= 1
    pair = (1 << a.bit_length()) - a
    if cnt[pair] > 0:
        ans += 1
        cnt[pair] -= 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c:
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        # c[b] -= cur
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)
    # print(type(c.keys()))
    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c:
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        # c[b] -= cur
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        # c[b] -= cur
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

    for b in A:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        c[b] -= cur
        c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    A.sort(reverse=True)
    C = Counter(A)
    for a in A:
        if C[a] == 0: continue
        C[a] -= 1
        p = (1 << a.bit_length()) - a
        if p > a: continue
        if p in C and C[p] > 0:
            ans += 1
            C[p] -= 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    A.sort()
    nDict = dict()
    for i, a in enumerate(A):
        if a in nDict: nDict[a] += 1
        else: nDict[a] = 1

    count = 0
    for i in reversed(range(N)):
        if nDict[A[i]] == 0: continue
        k = 1
        while k <= A[i]: k <<= 1
        if k - A[i] in nDict:
            if k - A[i] == A[i] and nDict[k - A[i]] > 1:
                count += 1
                nDict[A[i]] -= 2
            elif k - A[i] != A[i] and nDict[k - A[i]] > 0:
                count += 1
                nDict[A[i]] -= 1
                nDict[k - A[i]] -= 1
    print(count)
        

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import Counter
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    A.sort(reverse=True)
    C = Counter(A)
    for a in A:
        if C[a] == 0: continue
        C[a] -= 1
        p = (1 << a.bit_length()) - a
        if p in C and C[p] > 0:
            ans += 1
            C[p] -= 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for k in range(N-1,-1,-1):
    t = A[k]
    for d in range(1,32):
        if A[0] <= 2**d - t <= A[k]:
            i = bisect.bisect_left(A,2**d-t)
            if A[i] == 2**d-t and k != i:
                ans += 1
                A[k] += 0.01
                A[i] -= 0.01

print(ans)

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 i in a:
  if c[i]==0:
    continue
  pt=2**len(format(i,'b'))
  c[i]-=1
  if c[pt-i]>=1:
    ans+=1
    c[pt-i]-=1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
from collections import Counter
c=Counter(a)
ans=0
for i in a:
  if c[i]==0:continue
  m=1<<i.bit_length()
  c[i]-=1
  if c[m-i]:
    ans+=1
    c[m-i]-=1
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
while A:
    a = A.pop()
    if c[a] <= 0:
        continue
    c[a] -= 1
    Num = 1 << (a.bit_length())
    cand = Num - a  # この値は必ずa以下になるはず
    if c[cand] > 0:
        ans += 1
        c[cand] -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline

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

A.sort()
a = Counter(A)
answer = 0


while A:
    n = A.pop()
    if a[n] == 0:
        continue

    a[n] -= 1
    # 実現可能な最大の2冪
    s = 1 << (2 * n).bit_length()
    while n < s:
        b = s - n
        if a[b] > 0:
            answer += 1
            a[b] -= 1
            break
        s //= 2

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline

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

A.sort()
a = Counter(A)
answer = 0
# 可能な最大の2冪
limit = 1 << ((2 * 10 ** 9 + 1).bit_length() - 1)

while A:
    n = A.pop()
    if a[n] == 0:
        continue

    a[n] -= 1
    s = limit
    while n < s:
        b = s - n
        if a[b] > 0:
            answer += 1
            a[b] -= 1
            break
        s //= 2

print(answer)

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)
count = 0

for i in range(N):
    while C[A[i]]:
        C[A[i]] -= 1
        if C[2**(A[i].bit_length()) - A[i]]:
            C[2**(A[i].bit_length()) - A[i]] -= 1
            count += 1

print(count)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import bisect
n = inn()
a = inl()
done = [False]*n
ofs = [0]*n
cnt = 0
a.sort()
for i in range(n-1,0,-1):
    if done[i]:
        continue
    for j in range(32):
        if 2**j>a[i]:
            break
    x = 2**j-a[i]
    j = bisect.bisect_left(a,x)
    if j>=i:
        continue
    k = j+ofs[j]
    if k<i and a[k]==x:
        done[k] = done[i] = True
        ofs[j] += 1
        cnt += 1
print(cnt)

Submission status: Accepted

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

n = int(input())
A = sorted(map(int, input().split()), reverse=True)
C = Counter(A)
ans = 0
for a in A:
  if not C[a]:
    continue
  r = (1<<a.bit_length()) - a
  if r != a:
    if r in C and C[r] > 0:
      ans += 1
      C[r] -= 1
  else:
    if C[r] >= 2:
      ans += 1
      C[r] -= 1
  C[a] -= 1
print(ans)

Submission status: Accepted

Solution code:

N = int(input())

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

"""

2べきになる条件は？
→片方が2の補数であること

Nが大きい→貪欲的に
最大の奴はそれより小さい奴としかペアを組めない
→大きい奴から貪欲にとっけいけばいける？

いけそうかなぁ
"""

A.sort()
dic = {}
lis = []

for i in range(N):
    
    if i == 0 or A[i-1] != A[i]:
        dic[A[i]] = 1
        lis.append(A[i])
    else:
        dic[A[i]] += 1

lis.reverse()
ans = 0
d2lis = {}
for i in range(32):
    d2lis[2**i] = i

import math

for i in lis:

    if i in d2lis:
        ans += dic[i]//2
        dic[i] %= 2
    else:
        t = 2 ** (int(math.log(i,2)) + 1)
        if t-i in dic:
            ans += min(dic[i],dic[t-i])
            dic[t-i] = max(0, dic[t-i]-dic[i])

print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, *A = map(int, open(0).read().split())
ans = 0
A.sort()
dic = defaultdict(list)
for i, a in enumerate(A):
  dic[a] += [i]
for i in range(N-1,-1,-1):
  a = A[i]
  if dic[a]==[]:
    continue
  dic[a].pop()
  k = 1
  while k<=a:
    k *= 2
  n = k-a
  if dic[n]!=[]:
    dic[n].pop()
    ans += 1
print(ans)

Submission status: Accepted

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

dic = {}
for a in A:
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1
        
A.sort(reverse=True)
ans = 0
for a in A:
    if dic[a] == 0:
        continue
    dic[a] -= 1
    num = pow(2, len(bin(a))-2) - a
    if num in dic and dic[num] > 0:
        ans += 1
        dic[num] -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    N, *A = map(int, open(0).read().split())
    A.sort(reverse=True)
    C = Counter(A)
    ans = 0
    for a in A:
        if C[a] != 0:
            k = (1 << a.bit_length()) - a
            if k in C and C[k] != 0 and not (k == a and C[a] == 1):
                ans += 1
                C[a] -= 1
                C[k] -= 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

N = int(input())
A = list(map(int, input().split()))
L2 = [1]
for i in range(40):
    L2.append(L2[-1]*2)
D = defaultdict(int)
for a in A:
    D[a] += 1
A.sort(reverse=True)
res = 0
for a in A:
    if D[a] < 1:
        continue
    D[a] -= 1
    beki2 = L2[bisect.bisect_right(L2, a)]
    j = beki2 - a
    if D[j] > 0:
        D[j] -= 1
        res += 1

print(res)

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 i in a:
  if c[i]==0:
    continue
  pt=2**len(format(i,'b'))
  c[i]-=1
  if c[pt-i]>=1:
    ans+=1
    c[pt-i]-=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
import copy
from collections import *


N=int(input())
A=list(map(int,input().split()))
idle_max=10**9
peki2=[]
for i in range(1,100):
    a=2**i
    if a<=2*idle_max:
        peki2.append(a)
peki2.sort(reverse=True)
lst=[[],[]]
for a in A:
    if a%2:
        lst[1].append(a)
    else:
        lst[0].append(a)

lst[0].sort(reverse=True)
lst[1].sort(reverse=True)
setlst=[set(lst[0]),set(lst[1])]
Counerlst=[Counter(lst[0]),Counter(lst[1])]

count=0
for l in range(2):
    for n in lst[l]:
        if n in setlst[l]:
            for p in peki2:
                a=p-n

                if a in setlst[l]:
                    if n==a:
                        if Counerlst[l][n]>=2:
                            count+=1
                            Counerlst[l][n]-=2
                            if Counerlst[l][n]==0:
                                setlst[l].remove(n)
                    else:

                        count+=1
                        Counerlst[l][a]-=1
                        Counerlst[l][n]-=1
                        if Counerlst[l][a]==0:
                            setlst[l].remove(a)
                        if Counerlst[l][n]==0:
                            setlst[l].remove(n)
                    break
print(count)

Submission status: Accepted

Solution code:
from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    listb.sort()
    ans=0
    while(len(listb)>0):
        x=listb.pop()
        if mii[x]>0:
            k=1
            while k<=x:
                k*=2
            y=k-x
            if x==y:
                ans+=mii[x]//2
            elif y<x and y in si:
                m=min(mii[x],mii[y])
                ans+=m
                mii[y]-=m
            mii[x]=0
    print(ans)

Submission status: Accepted

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]:
    if ceil(log2(a)) == log2(a):
      i = (1 << (ceil(log2(a)) + 1)) - a
    else:
      i = (1 << ceil(log2(a))) - a

    if i != a:
      if cnt[i]:
        cnt[a] -= 1
        cnt[i] -= 1
        answer += 1
    else:
      if cnt[i] > 1:
        cnt[a] -= 2
        answer += 1
        
print(answer)

Submission status: Accepted

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]
        A[i][1]=1
        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[ind][1]=1
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
import math
import collections
powers =[2**i for i in range(1,int(math.log(max(A),2)+2))]
table=collections.defaultdict(int)
table2=collections.defaultdict(set)
ans=0
for i in range(N):
  table[A[i]]+=1
for x in table:
  for y in reversed(powers):
    if y - x in table:
      table2[x].add(y-x)
        
        
        
table2 =list(table2.items())
table2.sort(key = lambda x:len(x[1]))

for x,y in table2:
  while(table[x]>0):
    table[x]-=1
    for z in y:
      if table[z]>0:
        ans+=1
        table[z]-=1
        break
print(ans)

Submission status: Accepted

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

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]
    if a[x] == 0:
        keys.pop()
        continue
    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: Accepted

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:
    if C[a] == 0:
        continue
    pt = 2 ** len(format(a, 'b'))
    C[a] -= 1
    if C[pt - a] >= 1:
        C[pt - a] -= 1
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

    ans = 0
    for i in range(l):
        a = A[i]
        if exp(a)//2 == a:
            ans += int(d[a]//2)
        else:
            m = min(d[a],d[exp(a)-a])
            ans += m
            d[a] -= m
            d[exp(a)-a] -= m
            
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    ans = 0
    for i in range(l):
        a = A[i]
        if exp(a)//2 == a:
            ans += int(d[a]//2)
        else:
            m = min(d[a],d[exp(a)-a])
            ans += m
            d[a] -= m
            d[exp(a)-a] -= m
            
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
ball = list(map(int, input().split()))
ball.sort(reverse = True)
ok = {}
for x in ball:
    if x in ok:
        ok[x] += 1
    else:
        ok[x] = 1
ans = 0
for x in ball:
    if ok[x] != 0:
        y = 2**(x.bit_length()) - x
        if y in ok:
            if ok[y] != 0:
                if y == x and ok[y] == 1: 
                    continue
                ans += 1
                ok[x] -= 1
                ok[y] -= 1
print(ans)

Submission status: Accepted

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(reverse = True)
    ans = 0
    c = Counter(A)
    for a in A:
        cur = (1 << a.bit_length()) - a
        if c[a]>0 and c[cur]>0:
            if a==cur:
                ans += c[a]//2
                c[a]=0
                continue
            n = min(c[a],c[cur])
            c[a] -= n; c[cur] -= n
            ans += n
#            print(a,cur,c)
    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: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

N = ri()
A = rl()
A.sort(reverse=True)
c = Counter(A)
answer = 0
for x in A:
    target = (1 << x.bit_length()) - x
    while c[x] > 0:
        c[x] -= 1
        if c[target] > 0:
            c[target] -= 1
            answer += 1

print(answer)

Submission status: Accepted

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
    C[a] -= 1

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

print(ans)

Submission status: Accepted

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