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:
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

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

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

from bisect import bisect_left

N = I()
A = III()
A.sort()

val = []
num = []
before = 0
for a in A:
    if a != before:
        val.append(a)
        num.append(1)
        before = a
    else:
        num[-1] += 1

ans = 0

for i in range(N)[::-1]:
    s = math.floor(math.log(2*A[i],2))
    p = bisect_left(val,2**s-A[i])
    if A[i]==2**s-A[i]:
        if num[p]>=2:
            ans += 1
            num[p] -= 2
    else:
        j = bisect_left(val,A[i])
        if p<=len(val)-1:
            if val[p]==2**s-A[i] and num[j] and num[p]:
                ans += 1
                num[j] -= 1
                num[p] -= 1

print(ans)

Submission status: Accepted

Solution code:
import math
import bisect
import collections

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

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

Submission status: Accepted

Solution code:
import math
n = int(input())
l = sorted(list(map(int,input().split())))
c = 0
b = {}
for i in range(len(l)):
    if l[i] in b:
        b[l[i]] += 1
    else:
        b[l[i]] = 1

for i in range(len(l) - 1, -1, -1):
    if  b[l[i]] == 0:
        continue
    t = l[i]
    b[l[i]] -= 1
    s = 2 ** math.floor(math.log2(t))
    st = 2*s - t 
    if l == []:
        break
    if st in b and b[st] > 0:
        b[2 * s - t] -= 1
        c += 1
print(c)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def upper_pow2(n):
    ret = 1
    while n > 0:
        ret <<= 1
        n >>= 1
    return ret


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
d = dict()
for x in a:
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ans = 0
for x in a:
    if d[x] <= 0:
        continue
    if x & (x - 1):
        t = upper_pow2(x) - x
        if t in d and d[t] > 0:
            d[x] -= 1
            d[t] -= 1
            ans += 1
    else:
        if d[x] >= 2:
            d[x] -= 2
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_right as br
    from collections import Counter as ct
    check=[]
    i=1
    while i<=10**10:
        check.append(i)
        i*=2
    n=int(input())
    c=ct(list(map(int,input().split())))
    c_l=sorted(list(c.keys()),reverse=True)
    ans=0
    for i in c_l:
        j=check[br(check,i)]-i
        if i==j:
            ans+=c[i]//2
        else:
            ans+=min(c[i],c[j])
            c[j]-=min(c[i],c[j])
    print(ans)
main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]

c = Counter(A)
b = sorted(c.keys())

ret = 0
for j in range(len(c) - 1, -1, -1) :
    i = 2
    while c[b[j]] > 0 and i - b[j] <= b[j] :
        if b[j] != i - b[j] :
            if c[b[j]] > 0 and c[i-b[j]] > 0 :
                M = min(c[b[j]], c[i-b[j]])
                ret += M
                c[b[j]] -= M
                c[i-b[j]] -= M
        else :
            if c[b[j]] > 1 :
                ret += c[b[j]] // 2
                c[b[j]] %= 2
        i *= 2
    
print(ret)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 32)]))
    C = Counter(A)
    ans = 0
    A.sort(reverse=True)
    for k in A:
        if C[k] <= 0:
            continue
        C[k] -= 1
        r = (1 << k.bit_length()) - k
        if C[r] > 0:
            ans += 1
            C[r] -= 1

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 2*(10**5)
    # # A = [random.randint(1, 10**9) for _ in range(N)]
    # A = list(range(1, N+1))
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()

x=a[0];ctn=1;l=[];l2=[]
for i in range(1,n):
  if x==a[i]:
    ctn+=1
  else:
    l.append([x,ctn])
    l2.append(x)
    x=a[i]
    ctn=1
l.append([x,ctn])
l2.append(x)

b=[2**i for i in range(1,50)]

ct=0
for i in range(len(l2)-1,-1,-1):
  x=math.floor(math.log2(l2[i]))
  x=b[x]-l2[i]
  y=bisect.bisect_left(l2,x)
  if l2[y]==x:
    if l2[y]!=l2[i]:
      m=min(l[i][1],l[y][1])
    else:
      m=l[i][1]//2
    l[i][1]-=m
    l[y][1]-=m
    ct+=m
print(ct)

Submission status: Accepted

Solution code:
import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
x=a[0]
ctn=1
l=[]
l2=[]
for i in range(1,n):
  if x==a[i]:
    ctn+=1
  else:
    l.append([x,ctn])
    l2.append(x)
    x=a[i]
    ctn=1
l.append([x,ctn])
l2.append(x)

b=[]
for i in range(1,50):
  b.append(2**i)

ct=0
for i in range(len(l2)-1,-1,-1):
    x=math.floor(math.log2(l2[i]))
    x=b[x]-l2[i]
    y=bisect.bisect_left(l2,x)
    if l2[y]==x:
      if l2[y]!=l2[i]:
        m=min(l[i][1],l[y][1])
      else:
        m=l[i][1]//2
      l[i][1]-=m
      l[y][1]-=m
      ct+=m
print(ct)

Submission status: Accepted

Solution code:
import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(1,50):
  b.append(2**i)
ct=0
check=[1]*n
for i in range(n-1,-1,-1):
  if a[i]==1:
    break
  if check[i]==1 and a[i] not in b:
    check[i]=0
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    z=bisect.bisect_right(a,x)
    t=bisect.bisect_left(check[y:z],1)+y
    if t!=z:
      check[t]=0
      ct+=1

ctb=0
w=1
for i in range(n):
  if a[i] in b or a[i]==1:
    if a[i]==w:
      if check[i]==1:
        ctb+=1
    else:
      ct+=ctb//2
      w=a[i]
      if check[i]==1:
        ctb=1
      else:
        ctb=0
  else:
    ct+=ctb//2
    ctb=0
ct+=ctb//2

print(ct)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
p=max(a)*2
chk=[pow(2,i) for i in range(1,32)]
ans=0
for i in a[::-1]:
    if d[i]>0:
        d[i]-=1
        for j in chk[::-1]:
            if j-i in d and d[j-i]>0:
                d[j-i]-=1
                ans+=1
                break
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
p=max(a)*2
chk=[pow(2,i) for i in range(1,32) if pow(2,i)<=p]
ans=0
for i in a[::-1]:
    if d[i]>0:
        d[i]-=1
        for j in chk[::-1]:
            if j-i in d and d[j-i]>0:
                d[j-i]-=1
                ans+=1
                break
print(ans)

Submission status: Accepted

Solution code:
n = int(input().strip())
data = list(reversed(sorted(map(int, input().split()))))

cnt = {x: 0 for x in data}
for x in data:
    cnt[x] += 1

ans = 0
t = 2 ** 30
for x in data:
    while t // 2 > x:
        t = t // 2
    while cnt[x] > 0:
        cnt[x] -= 1
        if t-x in cnt and cnt[t-x] > 0:
            cnt[t-x] -= 1
            ans += 1

print (ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.append(-float("inf"))
n = len(A)

A.sort()
s = 2
while s <= A[-1]+A[-2]:
    s *= 2
s //= 2

U = [0] * n

ans = 0
while s > 0:
    ll = 0
    rr = n-1
    while rr >= 1 and s <= A[rr]:
        rr -= 1
    while rr >= 1 and rr-ll >= 2:
        # print("rr",rr,"ll",ll)
        t = s - A[rr]

        # print("s",s,"t",t)
        l = ll
        r = rr-1
        m = (r+l)//2
        while r-l > 1:
            # print("r",r,"l",l,"m",m)
            if A[m] >= t:
                r = m
            else:
                l = m
            m = (r+l)//2
        if A[l+1] == t:
            ans += 1
            U[l+1] = 1
            U[rr] = 1
            # print(ans)
            A[l+1] = -float("inf")
        ll = l
        rr -= 1
        # print(A)
    s //= 2

    B = []
    for i in range(len(A)):
        if U[i] == 0:
            B.append(A[i])
    A = B
    n = len(A)
    U = [0] * n
print(ans)

Submission status: Accepted

Solution code:

import bisect

"""
def wantp(n):

    wq = []
    while p[n] != n:
        wq.append(n)
        n = p[n]

    for i in wq:
        p[i] = n

    return n
"""


N = int(input())

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

A = []
AS = []
for i in range(N):
    if len(A) == 0:
        A.append(B[0])
        AS.append(1)
    else:
        if A[-1] == B[i]:
            AS[-1] += 1
        else:
            A.append(B[i])
            AS.append(1)


"""
p = [i for i in range(N)]
rank = [1] * N
"""
ans = 0

for i in range(len(A)):

    i = len(A) - 1 - i
    now = 2 ** 33

    while A[i] * 2 < now:
        now //= 2

    ind = bisect.bisect_left(A,now-A[i])

    if A[ind] + A[i] == now:

        if ind == i:
            ans += AS[i] // 2
            AS[i] = AS[i] % 2

        else:
            ans += min(AS[i],AS[ind])
            AS[ind] = max(AS[ind] - AS[i] , 0)



    #print (now,na,ind)

print (ans)

Submission status: Accepted

Solution code:
#pypyと実行時間比較
#最大要素の相手は一意?

from collections import Counter
n = int(input())
a = list(map(int, input().split( )))
a_c = Counter(a)

a.sort(reverse = True)
ans = 0
for i in range(n):
    if not a_c[a[i]]:
        continue
    a_c[a[i]] -= 1
    t = (1<<a[i].bit_length()) - a[i]
    if t in a_c:#1つしか残っていないときに誤ってペアができていた
        if a_c[t]:
            a_c[t] -= 1
            #a_c[a[i]] -= 1#こっちも減らす
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
#最大要素の相手は一意?

from collections import Counter
n = int(input())
a = list(map(int, input().split( )))
a_c = Counter(a)

a.sort(reverse = True)
ans = 0
for i in range(n):
    if not a_c[a[i]]:
        continue
    a_c[a[i]] -= 1
    t = (1<<a[i].bit_length()) - a[i]
    if t in a_c:#1つしか残っていないときに誤ってペアができていた
        if a_c[t]:
            a_c[t] -= 1
            #a_c[a[i]] -= 1#こっちも減らす
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))


#処理内容
def main():
	#前処理
	N = int(input())
	A = getlist()
	D = defaultdict(int)
	for i in A:
		D[i] += 1
	L = []
	for i in D:
		L.append(i)
	L = sorted(L)
	#print(L)
	
	#貪欲
	ans = 0
	for i in range(len(L)):
		a = L[-1 - i]
		if a == 2 ** (a.bit_length() - 1):
			ans += int(D[a] // 2)
		else:
			b = 2 ** a.bit_length() - a
			m = min(D[a], D[b])
			ans += m
			D[a] -= m
			D[b] -= m

	#出力
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
xs = [int(w) for w in input().split()]

counter = Counter(xs)

descent = sorted(xs, reverse=True)

def minimal_greater_power(x):
    b = len("{0:b}".format(x))
    return 2 ** b

ans = 0

for x in descent:
    if x not in counter:
        continue
    if counter[x] == 0:
        continue

    counter[x] -= 1

    pair = minimal_greater_power(x) - x
    if pair not in counter:
        continue
    if counter[pair] == 0:
        continue

    ans += 1
    counter[pair] -= 1

print(ans)

Submission status: Accepted

Solution code:
import collections
import bisect
n= int(input())
a=list(map(int, input().split()))
c=collections.Counter(a)
ans=0
des=sorted(a,reverse=True)
# asc=sorted(a)

for i in des:
    if c[i]>0:
        bi=format(i, 'b')
        x=2**len(bi)-i
        c[i]-=1
        if c[x]>0:
            c[x]-=1
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
d = dict()
ans = 0
for x in a:
  if x not in d:
    d[x] = 0
  d[x] += 1
for x in a:
  t = (1<<x.bit_length()) - x
  f = (d.get(t,0) and d.get(x,0))
  if t == x:
    f = (d.get(t,0) >= 2)
  if f:
    d[x] -= 1
    d[t] -= 1
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

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

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
a_=sorted(a,key=lambda x:-x)
ans=0
from collections import Counter
c=Counter(a_)
for i in a_:
    if c[i]==0:
        continue
    c[i]-=1
    for n in range(i):
        if i<2**n:
            t=n
            break
        elif i==2**n:
            t=n+1
            break
    j=2**t-i
    if j in c and c[j]>0:
        ans+=1
        c[j]-=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
a_=sorted(a,key=lambda x:-x)
ans=0
from collections import Counter
c=Counter(a_)
for i in a_:
    if c[i]==0:
        continue
    c[i]-=1
    m=1<<i.bit_length()
    j=m-i
    if j in c and c[j]>0:
        ans+=1
        c[j]-=1
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
    c[i] -= 1
    k = 1<<i.bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 1
print(ans)

Submission status: Accepted

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

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

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

l=sorted(d,reverse=True)

ans=0

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import Counter
c=Counter(A)
r=0
from math import log2
for n in sorted(list(c),reverse=True):
    m=2**int(log2(n)+1)
    if m==2*n:
        r+=c[n]//2
    else:
        r+=min(c[n],c[m-n])
        c[m-n]=max(c[m-n]-c[n],0)
print(r)

Submission status: Accepted

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

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

A.sort()
C = Counter(A)

ans = 0
for i in reversed(range(N)):
    a = A[i]
    inv = 2**(a.bit_length())-a
    if a == inv:
        if C[a] >= 2:
            C[a] -= 2
            ans += 1
    elif inv in C.keys():
        if C[inv] >= 1 and C[a] >= 1:
            C[a] -= 1
            C[inv] -= 1
            ans += 1

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import*
from bisect import*
p=[1]
for _ in range(30):p+=p[-1]*2,
n,*a=map(int,open(0).read().split())
d=Counter(a)
c=0
for b in sorted(a)[::-1]:
  if d[b]<1:continue
  d[b]-=1
  x=p[bisect(p,b)]-b
  if d[x]:
    d[x]-=1
    c+=1
print(c)

Submission status: Accepted

Solution code:
from collections import*
from bisect import*
p=[1]
for _ in range(30):p+=p[-1]*2,
n,*a=map(int,open(0).read().split())
d=Counter(a)
c=0
for i,b in enumerate(sorted(a)[::-1]):
  if d[b]<1:continue
  d[b]-=1
  x=p[bisect(p,b)]-b
  if d[x]:
    d[x]-=1
    c+=1
print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict as d
n=int(input())
a=sorted(list(map(int,input().split())))
b=d(int)
for i in a:
    b[i]+=1
s=n-1
c=0
while s>0:
    if b[a[s]]>0:
        t=2**(len(bin(a[s]))-2)
        b[a[s]]-=1
        if b[t-a[s]]>0:
            b[t-a[s]]-=1
            c+=1
    s-=1
print(c)

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
    c[i] -= 1
    k = 1<<i.bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
if N == 1:
  print(0)
  exit(0)
A = list(map(int, input().split()))
A.sort()
b = (A[-1] + A[-2]).bit_length()
#print(b)
vis = set()
res = 0
for t in range(b, -1, -1):
  s = 2 ** t
  r = N - 1
  #print(t)
  for l in range(N):
    if l in vis: continue
    if l >= r: break
    while l < r:
      #print(l, r, "s", s)
      if r in vis:
        r -= 1
        continue
      if A[l] + A[r] < s:
        break
      elif A[l] + A[r] > s:
        r -= 1
        if r in vis:
          r -= 1
      else:
        res += 1
        vis.add(l)
        vis.add(r)
        break
print(res)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import defaultdict


def main():
    _ = int(input())
    a = list(sorted(map(int, input().split())))
    dicta = defaultdict(lambda: 0)
    for _a in a:
        dicta[_a] += 1
    
    ans = 0
    for da in reversed(a):
        if dicta[da] <= 0:
            continue
        dicta[da] -= 1
        aa2 = 1
        while da >= aa2:
            aa2 *= 2
        
        if aa2-da in dicta and dicta[aa2-da] > 0:
            dicta[aa2-da] -= 1
            ans += 1
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

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

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect


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

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

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    s = input()
    ans = 0
    w = 0
    for i in range(len(s)):
        if s[i] == "W":
            ans += i-w
            w += 1
    print(ans)
    return

#B
def B():
    n = I()
    a = LI()
    f = defaultdict(lambda : 0)
    a.sort(key = lambda x:-x)
    ans = 0
    m = 32
    k = [1<<i for i in range(m)]
    for i in a:
        for j in k:
            i_ = j-i
            if i_ <= 0:continue
            if f[i_]:
                f[i_] -= 1
                ans += 1
                break
        else:
            f[i] += 1
    print(ans)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
import os
import sys
from collections import Counter

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

# グラフの最大マッチングだと辺の数多すぎ
# 大きい数から見ていくとまだ見てない数のうちペアになれる数が1つに定まる

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

Submission status: Accepted

Solution code:
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
result = 0
for a in list(sorted(d.keys(), reverse = True)):
  if a not in d:
    continue
  t = (1 << a.bit_length()) - a
  if t not in d:
    continue
  if a != t:
    if d[a] < d[t]:
      i = d[a]
    else:
      i = d[t]
  else:
    if d[a] == 1:
      continue
    i = d[a] // 2
  result += i  
  if d[a] == i:
    del d[a]
  else:
    d[a] -= i
  if d[t] == i:
    del d[t]
  else:
    d[t] -= i
print(result)

Submission status: 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))
result = 0
for a in alist:
  if a not in d:
    continue
  t = (1 << a.bit_length()) - a
  if t not in d:
    continue
  if a != t:
    if d[a] < d[t]:
      i = d[a]
    else:
      i = d[t]
  else:
    if d[a] == 1:
      continue
    i = d[a] // 2
  result += i  
  if d[a] == i:
    del d[a]
  else:
    d[a] -= i
  if d[t] == i:
    del d[t]
  else:
    d[t] -= i
print(result)

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

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

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

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