Problem:


Score : 600 points

Problem Statement

Takahashi has N balls with positive integers written on them. The integer written on the i-th ball is A_i.
He would like to form some number of pairs such that the sum of the integers written on each pair of balls is a power of 2.
Note that a ball cannot belong to multiple pairs.
Find the maximum possible number of pairs that can be formed.

Here, a positive integer is said to be a power of 2 when it can be written as 2^t using some non-negative integer t.

Constraints

1 \leq N \leq 2\times 10^5

1 \leq A_i \leq 10^9

A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible number of pairs such that the sum of the integers written on each pair of balls is a power of 2.

Sample Input 1

3
1 2 3

Sample Output 1

1

We can form one pair whose sum of the written numbers is 4 by pairing the first and third balls.
Note that we cannot pair the second ball with itself.

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2



Sample input:
3
1 2 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
from math import log2

if __name__ == "__main__":    
    n = int(input())
    l = list(map(int, input().split()))
    b = [0] * len(l)
    a = 0
    for i in range(len(l)):
        for j in range(i+1,len(l)):
            if b[j] != 0:
                continue
            if log2(l[i] + l[j]) == int(log2(l[i] + l[j])):
                b[j] = 1
                a += 1
    print(a)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=set(a)
r=0
for i in range(n):
    if a[i] not in s: break
    pair = 2**math.ceil(math.log2(a[i]))-a[i]
    if pair in s:
        s.remove(a[i])
        s.remove(pair)
        r+=1
        continue
    if i<n-1 and pair==0 and a[i+1]==a[i]:
        s.remove(a[i])
        r+=1
print(r)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

A.sort()
m = 2 ** 30
used = set()
ans = 0

def search(ok, ng, n):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if A[mid] < n or (A[mid] == n and mid not in used):
        return search(mid, ng, n)
    else:
        return search(ok, mid, n)

for i in range(30):
    m //= 2
    for j in range(n):
        if j in used or A[j] > m:
            continue
        a = search(-1, n, m - A[j])
        if A[a] == m - A[j]:
            if a == j:
                if not A[a+1] == A[j]:
                    continue
                a += 1
            used.add(a)
            used.add(j)
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc 029 B
"""

from collections import Counter

n = int(input())
ali = list(map(int, input().split()))
ali.sort(reverse=True)

c = Counter(ali)
print(c)
ans = 0


def pow2(n):
    m = n
    tmp = 1
    while m > 0:
        tmp = tmp << 1
        m = m >> 1
    return tmp


while bool(c):
    m = list(c.elements())[0]
    n = pow2(m) - m
    print(m, n)
    c[m] -= 1
    c += Counter()
    if n in c:
        c[n] -= 1
        ans += 1
    c += Counter()

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
two_list = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072,
            262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
            33554432, 67108864, 134217728, 268435456, 536870912]

count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1

    else:
        items[a] = 1

for a in A_list:
    if items[a] >= 1:
        items[a] -= 1
        for t in two_list:
            m = t -a
            if m in items:
                if items[m] >= 1:
                    count += 1
                    items[m] -= 1
print(count)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1]
c = collections.Counter(a)

beki2 = [2**i for i in range(1,30)]

cnt = 0

for i in a:
    for j in beki2:
        if j-i > amax:
            break
        if j-i in c:
            if j-i == i or c[j-i] == 0:
                continue
            cnt += 1
            c[j-i] -= 1

print(cnt//2)

Submission status: Wrong Answer

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

import bisect

n=int(input())
a = [int(i) for i in input().split()]
a.sort()
check = [0]*n
print(a)

ans=0

while(a):
    c=a.pop()
    d=c
    keta=0
    while(d!=0):
        d=d//2
        keta +=1
    x = 2**keta - c
#    print(c,x)
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        ans += 1
#        print(a[i],c,"xxx")
        a.remove(x)



print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split(' ')))
patterns = []
for i in range(N):
    for j in range(N):
        if i == j: continue
        bits = A[i] + A[j]
        while bits != 0b0:
            right = bits & 0b1
            if right != 0b0:
                if bits == right:
                    patterns.append((i, j))
                break
            bits >>= 1
used = set()
for i, j in reversed(patterns):
    if i not in used and j not in used:
        used.add(i)
        used.add(j)
print(len(used)//2)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import Counter
N = int(input())
A = list(map(int , input().split()))
# A.sort()
beki = {2**i for i in range(37)}
beki_rlist = list(reversed([2**i for i in range(37)]))


def guchoku():
    max_ans = 0
    for tmp_a in itertools.permutations(A):
        tmp_ans = 0
        for i in range(len(A)//2):
            if tmp_a[2*i]+tmp_a[2*i+1] in beki:
                tmp_ans+=1
        max_ans = max(tmp_ans,max_ans)
    return max_ans


# print(guchoku())
# print("---")
ans = 0
c = Counter(A)
for i in sorted(c.keys()):
    for tmp in beki_rlist:
        if c[i]==0:
            break
        elif tmp == i*2:
            ans += c[i]//2
            c[i]-= c[i]//2 *2
        elif c[tmp-i]:
            val = min(c[i],c[tmp-i])
            c[i] -=val
            c[tmp-i]-=val
            ans +=val
print(ans)
# print(c)

Submission status: Wrong Answer

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


def main():
    """Function."""
    n = int(input())
    a = list(map(int, input().split()))

    beki = [2**x for x in range(30)]
    # o_list, e_list = [0 for _ in range(n)], [0 for _ in range(n)]
    o_list, e_list = [], []
    for i in range(n):
        if a[i] % 2 == 0:
            e_list.append(a[i])
        else:
            o_list.append(a[i])

    counter = 0
    o_set, e_set = set(), set()
    for i in range(len(o_list)):
        if i in o_set:
            continue
        for j in range(len(o_list)):
            if j in o_set:
                continue

            if i == j:
                continue

            else:
                if o_list[i] + o_list[j] in beki:
                    o_set.add(i)
                    o_set.add(j)
                    counter += 1

    for i in range(len(e_list)):
        if i in e_set:
            continue
        for j in range(len(e_list)):
            if j in e_set:
                continue

            if i == j:
                continue

            else:
                if e_list[i] + e_list[j] in beki:
                    e_set.add(i)
                    e_set.add(j)
                    counter += 1
    print(counter)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import log2
from bisect import bisect_left


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
avail = [True for _ in range(len(A))]

count = 0
for i in range(len(A) - 1, -1, -1):
    if not avail[i]:
        continue
    comp = getComp(A[i])
    j = bisect_left(A, comp)
    if i != j and A[j] == comp and avail[j]:
        avail[i] = False
        avail[j] = False
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())
aaa = list(map(int, input().split()))
rd = defaultdict(list)
ma = 0
for i, a in enumerate(aaa):
    rd[a].append(i)
    ma = max(ma, a)

ma2 = 2
while ma2 <= ma:
    ma2 <<= 1

edges = [set() for _ in range(n)]
for a, i_list in rd.items():
    tmp_set = set()
    k = 2
    while k <= ma2:
        if k > a:
            b = k - a
            if b in rd:
                tmp_set.update(rd[b])
        k <<= 1
    if not tmp_set:
        continue
    tmp_list = sorted(tmp_set)
    l = 0
    for i in i_list:
        while tmp_list[l] <= i:
            l += 1
            if l >= len(tmp_list):
                break
        else:
            edges[i] = set(tmp_list[l:])
        break


def dfs(v, visited):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False


matched = [-1] * n

print(sum(dfs(s, set()) for s in range(n)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
d = {} # d[i] = number of i
ans = 0
for i in A:
	for j in range(31, 0, -1):
		x = 2 ** j - i
		if x in d and d[x] > 0:
			ans = ans + 1
			d[x] -= 1
			break
	else:
		d[i] = d.get(i, 0) + 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
G = defaultdict(list)
A = list(map(int, input().split()))
A = sorted(A)
for i in range(N):
    for k in range(30):
        if 2 ** k - A[i] in A:
            j = A.index(2 ** k - A[i])
            G[i].append(N + j)
            G[j].append(N + i)

used = [False] * 2 * N
match = [-1] * 2 * N


def dfs(v):
    global used
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True


ma = 0
for i in range(N):
    if match[i] < 0:
        used = [False] * 2 * N
        if dfs(i):
            ma += 1

print(ma // 2)

Submission status: Wrong Answer

Solution code:
def two_power(m):
  if m < 2:
    return 0
  else:
    return two_power(m//2) + 1

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

a.sort()
a.reverse()
c = 0
skip = []
for i in range(len(a)):
  if i in skip:
    continue
  m = two_power(a[i])
  if 2 ** (m+1) - a[i] in a:
    j = a.index(2 ** (m+1) - a[i])
    if j not in skip:
      c += 1
      skip.append(j)
    
print(c)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=set(a)
r=0
for i in range(n):
    if a[i] not in s: break
    pair = 2**math.ceil(math.log2(a[i]))-a[i]
    if pair in s:
        s.remove(a[i])
        s.remove(pair)
        r+=1
print(r)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
count = 0
for i in range(N):
    if A[i]>0:
        for j in range(i+1,N):
            if A[j] > 0:
                X = A[i] + A[j]
                X = bin(X)
                if X.count("1")==1:
                    count+=1
                    A[j] = 0
print(count)

Submission status: Wrong Answer

Solution code:
input()
l = list(map(int, input().split()))
cnt = 0
for i in l:
    if i % 2:
        cnt+=1
print(cnt//2)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())

E=[]
O=[]

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

for i in range(len(a)):
    if a[i]%2==0:
        E.append(a[i])
    else:
        O.append(a[i])
        
E.sort()
O.sort()

ans=0
for e in range(len(E)):
    t=0
    while E[len(E)-1-e]>2**t:
       t=t+1
       #print(t)
    if E[bisect.bisect_left(E,2**t-E[len(E)-1-e])]+E[len(E)-1-e]==2**t:
        ans+=1
        E[bisect.bisect_left(E,2**t-E[len(E)-1-e])]+=0.5
        
for o in range(len(O)):
    t=0
    while O[len(O)-1-o]>2**t:
       t=t+1
       #print(t)
    if O[bisect.bisect_left(O,2**t-O[len(O)-1-o])]+O[len(O)-1-o]==2**t:
        ans+=1
        O[bisect.bisect_left(O,2**t-O[len(O)-1-o])]+=0.5
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
listA = list(map(int, input().split()))
if n == 1:
    print(0)
else:
    listA.sort()
    listA.reverse()
    sumM = listA[0]+ listA[1]
    maxB = 32
    while maxB > 0:
        if 2**maxB > sumM:
            maxB-=1
        else:
            break
    
    counter=0
    index = maxB
    while index > 0:
        index2=0
        while index2 < len(listA)//2+1:
            if 2**index-listA[index2] < listA[index2]+1 and listA[index2]!=0:
                if 2**index-listA[index2] in listA:
                    targetI = listA.index(2**index-listA[index2])
                    if targetI != index2:
                        listA[index2] = 0
                        listA[targetI] = 0
                        counter+=1
            elif 2**index-listA[index2] > listA[index2]:
                break
            index2+=1
        index-=1
    print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse = True)
cnt = 0
for i in range(1,31)[::-1]:
    for j in range(n):
        if 2**(i-1) <= a[j] < 2**i:
            for k in range(j+1,n):
                if a[j] + a[k] == 2**i:
                    cnt += 1
                    break
        else:
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()


A_list = [int(a) for a in A.split()]
A_list.sort()
beki_list = [2 ** i for i in range(1, 31)]
ret = 0
for i, a in enumerate(A_list[:-1]):
    counter = [b for b in A_list[i+1:] if b - a in beki_list]
    if len(counter) > 0:
        ret += 1
        A_list.remove(max(counter))
print(str(ret))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
def list_dif(l1, l2):
    result = l1.copy()
    for v in l2:
        if v in result:
            result.remove(v)
    return result
H = defaultdict(lambda: [])
N = int(input())
A = sorted(inpl())
ans = 0
for j in range(29,0,-1):
    k = 2**j
    t = []
    H = defaultdict(lambda: [])
    for i in A:
        if k <= i:
            break
        if H[k-i]:
            t.append(H[k-i].pop())
            t.append(i)
            ans += 1
        else:
            H[i].append(i)
    A = list_dif(A, t)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

c = 0
for i in range(N - 1 , -1, -1):
    if A[i] == int(A[i]):
        b = 1
        while b <= A[i]:
            b <<= 1

        j = bisect.bisect_left(A, b - A[i])
        if b - A[i] == A[j]:
            c += 1
            A[j] = A[j] - 0.5
            A[i] = A[i] + 0.5

print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, *A = map(int, open(0).read().split())
A.sort()
C = Counter(A)
pow2 = [2 ** i for i in range(1, 32)][::-1]
ans = 0
for p2 in pow2:
    for a in A:
        if a > p2:
            break
        if C[a] == 0:
            continue
        if p2 - a in C:
            if p2 == 2 * a:
                tmp = C[a] // 2
                ans += tmp
                C[a] -= tmp
            else:
                tmp = min(C[p2 - a], C[a])
                ans += tmp
                C[p2 - a] -= tmp
                C[a] -= tmp
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

c = 0
for i in range(N - 1 , -1, -1):
    b = 1
    while b <= A[i]:
        b <<= 1
    
    j = bisect.bisect_left(A, b - A[i])
    if b - A[i] == A[j]:
        c += 1
        A[j] = A[j] - 0.5
        A[i] = A[i] + 0.5

print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
xs = [int(x) for x in input().split()]
d = Counter(xs)

res = 0
for i in range(30, 0, -1):
    val = 2 ** i
    for k in list(d):
        if d.get(k, 0) > 0 and d.get(val - k, 0) > 0:
            pairs = min(d[k], d[val - k])
            res += pairs
            d[k] -= pairs
            d[val-k] -= pairs
    d = {k:v for k, v in d.items() if v > 0}
print(res)

Submission status: Wrong Answer

Solution code:
import bisect

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

c = 0
for i in range(N - 1 , -1, -1):
    b = 1
    while b <= A[i]:
        b <<= 1
    
    j = bisect.bisect_left(A, b - A[i])
    if b - A[i] == A[j]:
        c += 1
        A[j] = A[j] - 0.5

print(c)

Submission status: Wrong Answer

Solution code:
def binarySearch(arr, l, r, x): 
	while l <= r: 
		mid = l + (r - l)//2;   
		if arr[mid] == x: 
			return mid 
		elif arr[mid] < x: 
			l = mid + 1
		else: 
			r = mid - 1
	return -1
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
vis=[False]*(len(arr))
po=[]
for i in range(31):
	po.append(2**i)
c=0
for i in range(n):
	x=arr[i]
	y=po[0]
	for j in range(len(po)):
		if arr[i]<po[j]:
			y=po[j]
			z=po[j]-arr[i]
			xx=binarySearch(arr,0,n-1,z)
			if xx!=-1 and xx>i:
				c+=1
				# print(arr[i],arr[xx])
				break
print(c)

Submission status: Wrong Answer

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

U = [0]*N
j = 0
ans = 0
for i in range(N-1, -1, -1):
    if U[i]:
        continue
    b = 2**(A[i]).bit_length()
    while j < i and (U[j] or A[j] + A[i] < b):
        j += 1
    if j < i and A[j] + A[i] == b:
        ans += 1
        U[j] = 1
print(ans)

Submission status: Wrong Answer

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

U = [0]*N
j = 0
ans = 0
for i in range(N-1, -1, -1):
    if U[i]:
        continue
    b = 2**(A[i]).bit_length()
    while j < i and (U[j] or A[j] + A[i] < b):
        j += 1
    if j < i and A[j] + A[i] == b:
        ans += 1
        U[j] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
def search(arr,key):
	start=0
	end=len(arr)-1
	while start<=end:
		mid=(start+end)//2
		if arr[mid]==key:
			return mid
		elif arr[mid]>key:
			end=mid-1
		else:
			start=mid+1 
	return -1
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
vis=[False]*(len(arr))
po=[]
for i in range(31):
	po.append(2**i)
c=0
for i in range(n):
	x=arr[i]
	y=po[0]
	for j in range(len(po)):
		if arr[i]<po[j]:
			y=po[j]
			z=po[j]-arr[i]
			xx=search(arr,z)
			if xx!=-1 and xx>i:
				c+=1
				# print(arr[i],arr[xx])
				break
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
d = defaultdict(list)
n = int(input())
l = sorted(list(map(int,input().split())))
for i,j in enumerate(l):
    d[j].append(i)

used = [0]*n
ans = 0
for i in range(n-1,-1,-1):
    if used[i]:
        continue
    x = 2**(l[i].bit_length())
    y = x-l[i]
    if y in d:
        for j in d[y]:
            if used[j] == 0 and j != i:
                used[j] = 1
                ans += 1
                used[i] = 1
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for v in a:
        if v in dic:
            dic[v] += 1
        else:
            dic[v] = 1
    key = [v for v in dic.keys()]
    key.sort(reverse=True)
    ans = 0
    for v in key:
        num = dic[v]
        if num > 0:
            for i in reversed(range(1, 35)):
                target = 2**i
                if 2*v < target or target < v:
                    continue
                u = target - v
                if v == u:
                    z = dic[v]//2
                    ans += z
                    dic[v] -= 2*z
                elif u in dic:
                    x, y = dic[v], dic[u]
                    z = 0
                    if x < y:
                        z = x
                    else:
                        z = y
                    dic[v] -= z
                    dic[u] -= z
                    ans += z
                if dic[v] == 0:
                    break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import log
n = int(input())
A = list(map(int, input().split()))
num = {}
for a in A:
	if a in num:
		num[a] += 1
	else:
		num[a] = 1

ans = 0
cnt = int(log(max(A), 2)) + 5 
for i in range(cnt, 0, -1):
	b = {}
	for x in num:
		if 2 ** i - x in b:
			b[2 ** i - x] += 1
		else:
			b[2 ** i - x] = 1
	for x in num:
		if x in b and num[x] > 0:
			if x * 2 == 2 ** i:
				ans += num[x] // 2
				num[x] %= 2
			else:
				small = min(num[x], num[2 ** i - x])
				ans += small
				num[x] -= small
				num[2 ** i - x] -= small
print(ans)

Submission status: Time Limit Exceeded

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

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    D[A[-1-i]]-=1
    for j in range(1,50):
      d=2**j
      if A[-1-i]<d:
        e=d-A[-1-i]
        break
    if D[e]>0:
      cnt+=1
      D[e]-=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを作る
    adj = defaultdict(list)
    for a in DISTINCT_A:
        for e in range(MAX_EXP + 1):
            b = pow2[e] - a
            if a <= b:
                break
            if counter[b] == 0:
                continue
            adj[a].append(b)
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        for b in adj[a]:
            cnt = min(counter[a], counter[b])
            ans += cnt
            counter[a] -= cnt
            counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを作る
    adj = defaultdict(list)
    for a in DISTINCT_A:
        for e in range(MAX_EXP + 1):
            b = pow2[e] - a
            if counter[b] == 0:
                continue
            if a > b:
                adj[a].append(b)
            elif a < b:
                adj[b].append(a)
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        for b in adj[a]:
            cnt = min(counter[a], counter[b])
            ans += cnt
            counter[a] -= cnt
            counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(set(A))
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを作る
    adj = defaultdict(list)
    for a in DISTINCT_A:
        for e in range(MAX_EXP + 1):
            b = 2**e - a
            if counter[b] == 0:
                continue
            if a > b:
                adj[a].append(b)
            elif a < b:
                adj[b].append(a)
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        for b in adj[a]:
            cnt = min(counter[a], counter[b])
            ans += cnt
            counter[a] -= cnt
            counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = 2**e
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)  # 大きい順に並べておく
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを作る
    adj = defaultdict(list)
    for a in A:
        for e in range(MAX_EXP + 1):
            b = 2**e - a
            if counter[b] == 0:
                continue
            if a > b:
                adj[a].append(b)
            elif a < b:
                adj[b].append(a)
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in A:
        for b in adj[a]:
            cnt = min(counter[a], counter[b])
            ans += cnt
            counter[a] -= cnt
            counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = 2**e
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
used = [False] * n
ans = 0
for i in reversed(range(n)):
    if used[i]:
        continue
    m = A[i]
    used[i] = True
    t = m.bit_length()
    pair = 2**t - m
    l = bisect_left(A, pair)
    r = bisect_right(A, pair)
    if r - l > 0:
        for j in range(l, r):
            if used[j]:
                continue
            else:
                ans += 1
                used[j] = True
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = sorted(map(int, input().split()))

used = [False] * N

ans = 0
for i in range(31, 0, -1):
    power_of_two = 1 << i
    l = 0
    r = N - 1
    while True:
        while l < N and used[l]:
            l += 1
        while r >= 0 and used[r]:
            r -= 1
        if l >= r:
            break

        if As[l] + As[r] == power_of_two:
            used[l] = True
            used[r] = True
            l += 1
            r -= 1
            ans += 1
        elif As[l] + As[r] < power_of_two:
            l += 1
        else:
            r -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

cnt = {}
for x in a:
    if x in cnt:
        cnt[x] += 1
    else:
        cnt[x] = 1

ans = 0
for i in range(n - 1, -1, -1):
    for d in range(30, -1, -1):
        k = bisect.bisect_left(a, (1 << d) - a[i])
        if k < n and a[i] + a[k] == (1 << d) and (a[i] == a[k] and cnt[a[i]] >= 2 or a[i] != a[k] and cnt[a[i]] >= 1 and cnt[a[k]] >= 1):
            ans += 1
            cnt[a[i]] -= 1
            cnt[a[k]] -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
ar = list(map(int,input().split(" ")))
ar = sorted(ar,reverse=True)
br = [2]
i = 1
while True:
    if br[-1] > ar[0] + ar[1]:
        break
    i += 1
    br.append(2 ** i)
i = 0
j = 1
count = 0
while True:
    if ar[i] + ar[j] in br:
        del ar[j]
        del ar[i]
        count += 1
        i = 0
        j = 1
    else:
        j += 1
        if j == len(ar):
            del ar[i]
            j = 1
    if len(ar) <= 1:
        break
print(count)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
n = 1
while n <= 2 * A[0]:
    n *= 2
n //= 2
ans = 0
while n > 0:
    for a in A:
        if cnt[a] == 0:
            continue
        b = n - a
        if b > a:
            break
        c = 0
        if b == a and cnt[a] > 1:
            c = cnt[a] // 2
        elif b != a and cnt[b] > 0:
            c = min(cnt[a], cnt[b])
        cnt[a] -= c
        cnt[b] -= c
        ans += c
    n //= 2
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split()))
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
n = 1
m = max(A)
while n <= 2 * m:
    n *= 2
n //= 2
ans = 0
while n > 0:
    for a in A:
        if cnt[a] == 0:
            continue
        b = n - a
        c = 0
        if b == a and cnt[a] > 1:
            c = cnt[a] // 2
        elif b != a and cnt[b] > 0:
            c = min(cnt[a], cnt[b])
        cnt[a] -= c
        cnt[b] -= c
        ans += c
    n //= 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
used = [False] * n
ans = 0

def judge(x):
    while x % 2 == 0:
        x //= 2
    return x == 1

for i in range(n):
    if used[i]:
        continue
    else:
        for j in range(i+1, n):
            if used[j]:
                continue
            if judge(a[i] + a[j]):
                used[i] = True
                used[j] = True
                ans += 1
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
used = [False] * n
ans = 0

def judge(x):
    while x % 2 == 0:
        x //= 2
    return x == 1

for i in range(n):
    if used[i]:
        continue
    else:
        for j in range(i+1, n):
            if used[j]:
                continue
            if judge(a[i] + a[j]):
                used[i] = True
                used[j] = True
                ans += 1
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
*l, = map(int, input().split())
c = Counter(l)
ks = c.keys()
ans = 0

for i in sorted(ks)[::-1]:
    while c[i]:
        a = i.bit_length()
        v = 2**a - i
        if v in ks and (v!=i or (v==i and c[v]>=2)):
            c[v] -= 1
            c[i] -= 1
            ans += 1
        else:
            break
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
*l, = map(int, input().split())
c = Counter(l)
ks = c.keys()
ans = 0

for i in sorted(ks)[::-1]:
    while c[i]:
        for j in range(i.bit_length()+1):
            v = (2**j)-i
            if v in ks:
                if v!=i or (v==i and c[v]>=2):
                    c[v] -= 1
                    c[i] -= 1
                    ans += 1
                    break
        else:
            break


print(ans)