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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000000)

def powers_of_2(n):
    while True:
        if n%2 == 0:
            n = n/2
        else:
            return False
        if n == 1:
            return True

n = int(input())
a = list(map(int, input().split()))
p = [[] for _ in  range(n)]
b = [True for _ in  range(n)]

for i in range(n-1):
    for j in range(i+1, n):
        if powers_of_2(a[i]+a[j]):
            p[i].append(j)

def pair(_i, b):
    _max = 0
    for i in range(_i, n-1):
        if not b[i]:
            continue
        if p[i] != []:
            for j in p[i]:
                if not b[j]:
                    continue
                b[j] = False
                _max = max(_max, 1+pair(i+1, b))
                b[j] = True
    return _max
print(pair(0, b))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(int(math.log2(max(A))) + 1, -1, -1)]

A.sort()
already = set()

def is_in(t):
    i = bisect.bisect_left(A, t)
    if i < len(A):
        while t == A[i]:
            if i not in already:
                already.add(i)
                return i
    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    already.add(n)
    a = A[n]
    T2 = [t - a for t in T if a < t <= 2 * a]
    for t in T2:
        i = is_in(t)
        if i != -1:
            res += 1
            break

print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            debug("hoge", used)
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            res = bisect(val, start, mid)
            return res
        else:
            used[mid] = True
            debug("fuga", used)
            return mid
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i]  == val):
    #         used[i] = True
    #         return i
    return None


def _find(b, end, e):
    "slow!!!!"
    # debug(b, end, e)
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i] + b == 2**e):
    #         used[i] = True
    #         return i
    # return None


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        debug("found: ", b, j)
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

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


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


ii = 0
m = ali[ii]
while bool(c):
    n = pow2(m) - m
    c[m] -= 1
    if c[m] == 0:
        c += Counter()
        ii += 1
        m = ali[ii]
    if n in c:
        c[n] -= 1
        ans += 1
    c += Counter()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


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


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

count = 0
i = len(A)
while i > 0:
    i -= 1
    comp = getComp(A[i])
    j = bisect_left(A, comp)
    if i == j or A[j] != comp:
        continue
    if i < j:
        A.pop(j)
        A.pop(i)
    else:
        A.pop(i)
        A.pop(j)
    count += 1
    i -= 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    for i, j in Ad.copy().items():
        if 2*i == k:
            ans += Ad[i]//2
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            Ad[i] -= m
            ans += m
        else:
            H[i] = j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

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

ans = 0
for A in As:
    if cnt[A] <= 0: continue
    cnt[A] -= 1
    for P in Ps:
        if cnt[P - A] > 0:
            ans += 1
            cnt[P - A] -= 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

c = 0
for k in range(0,30)[::-1]:
  if a[-1]<2**k:
    continue
  i = 0
  j = len(a)-1
  while i < j:
    if a[i]+a[j] < 2**(k+1):
      i += 1
    elif a[i]+a[j] > 2**(k+1):
      j -= 1
    else:
      c += 1
      a.pop(j)
      a.pop(i)
      j -= 2
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(int(math.log2(max(A))) + 1, -1, -1)]

A.sort()

def is_in(t):
    i = bisect.bisect_left(A, t)
    if i < len(A) and t == A[i]:
        return i
    return -1

res = 0
while A:
    a = A.pop()
    T2 = [t - a for t in T if a < t <= 2 * a]
    for t in T2:
        i = is_in(t)
        if i != -1:
            res += 1
            del A[i]
            break

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    for i, j in Ad.copy().items():
        if 2*i == k:
            m = Ad[i]//2
            Ad[i] -= 2*m
            ans += m
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            Ad[i] -= m
            ans += m
        else:
            H[i] = j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000000)

def powers_of_2(n):
    while True:
        if n%2 == 0:
            n = n/2
        else:
            return False
        if n == 1:
            return True

n = int(input())
a = list(map(int, input().split()))
b = [True for _ in  range(n)]

def pair(n, a, b, _i, ans):
    list_ans = []
    for i in range(_i, n-1):
        if b[i] == False:
            continue
        for j in range(i+1, n):
            if b[j] == False:
                continue
            if powers_of_2(a[i]+a[j]):
                b[j] = False
                list_ans.append(pair(n, a, b, i+1, ans+1))
                b[j] = True
    return max(list_ans) if list_ans != [] else ans

print(pair(n, a, b, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

c = 0
for k in range(0,30)[::-1]:
  i = 0
  j = len(a)-1
  while i < len(a):
    if a[i] > 2**k:
      break
    elif a[i] == 2**k:
      if i+1 < len(a):
        if a[i+1] == 2**k:
          c += 1
          a.pop(i+1)
          a.pop(i)
          continue
      else:
        break
    else:
      #exit()
      j = min(j, len(a)-1)
      while a[i]+a[j] > 2**(k+1):
        j -= 1
      if j == i:
        break
      if a[j] == 2**(k+1)-a[i]:
        c += 1
        a.pop(j)
        a.pop(i)
      else:
        i += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(int(math.log2(max(A))) + 1, -1, -1)]

A.sort()

def is_in(t):
    i = bisect.bisect_left(A, t)
    if i < len(A) and t == A[i]:
        return i
    return -1

res = 0
while A:
    a = A.pop()
    T2 = [t - a for t in T if t > a]
    for t in T2:
        i = is_in(t)
        if i != -1:
            res += 1
            A.pop(i)
            break

print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

a.sort()
memo = [0 for i in range(n)]

count = 0
for t in reversed(range(1, 31)):
    for i in reversed(range(n)):
        if memo[i] == 1:
            continue
        front = bisect.bisect_left(a, (1 << t) - a[i])
        back = bisect.bisect_right(a, (1 << t) - a[i])
        while front != back:
            if i <= front:
                break
            if memo[front] == 0:
                memo[i] = 1
                memo[front] = 1
                count += 1
                break
            front += 1

print(count)

Submission status: Time Limit Exceeded

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)
    while True:
        if A[j] != comp:
            break
        if i == j or not avail[j]:
            j += 1
            continue
        avail[i] = False
        avail[j] = False
        count += 1
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a.sort(key=lambda x:-x)
d = defaultdict(int)
for i in a:
    d[i] += 1
beki = [2**i for i in range(60,0,-1)]
ans = 0
for i in a:
    if d[i] == 0:
        continue
    for j in beki:
        if j <= i:
            break
        ni = j - i
        if ni == i:
            if d[i] >= 2:
                ans +=1
                d[i]-=2
                break
        elif d[ni] > 0:
            ans += 1
            d[ni]-=1
            d[i]-=1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import log,floor
N = int(input())
A = list(map(int, input().split()))

# log(10**9 + 10**9)/log(2) = 30.89 < 31
#print(log(2 * 10**9) / log(2))

A.sort(reverse=True)
usedI = [0] * N
cnt = 0

for i in range(N):
  if usedI[i] == 1:
    continue
  #print(i, log(A[i]) / log(2) )
  x = floor(log(A[i]) / log(2)) + 1 #実現可能なべき上
  search_x = 2 ** x - A[i]
  for j in range(N-1,i,-1):
    if search_x == A[j]:
      if usedI[j] == 1:
        continue
      else:
        cnt += 1
        usedI[i] = 1
        usedI[j] = 1
        break
    elif search_x < A[j]:
      break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

c = 0
for k in range(0,30)[::-1]:
  i = 0
  while i < len(a):
    # exit()
    if a[i] > 2**k:
      # exit()
      break
    elif a[i] == 2**k:
      #exit()
      if i+1 < len(a):
        if a[i+1] == 2**k:
          c += 1
          a.pop(i+1)
          a.pop(i)
          continue
      else:
        break
    else:
      #exit()
      j = bisect.bisect_left(a, 2**(k+1)-a[i])
      # print(a, i,j,k)
      if j == len(a):
        i += 1
        continue
      if a[j] == 2**(k+1)-a[i]:
        c += 1
        a.pop(j)
        a.pop(i)
      else:
        i += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
from math import log,floor
N = int(input())
A = list(map(int, input().split()))

# log(10**9 + 10**9)/log(2) = 30.89 < 31
#print(log(2 * 10**9) / log(2))

A.sort(reverse=True)
usedI = [0] * N
cnt = 0

for i in range(N):
  if usedI[i] == 1:
    continue
  #print(i, log(A[i]) / log(2) )
  x = floor(log(A[i]) / log(2)) + 1 #実現可能なべき上
  search_x = 2 ** x - A[i]
  for j in range(i+1,N):
    if search_x == A[j]:
      if usedI[j] == 1:
        continue
      else:
        cnt += 1
        usedI[i] = 1
        usedI[j] = 1
        break
    elif search_x > A[j]:
      break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy

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


x = 1
beki = []
while x <= 2*10**9:
    x *= 2
    beki.append(x)

useA = copy.deepcopy(A)

pairs = 0
for i in range(len(beki)):
    full = beki[len(beki)-i-1]
    for j in range(N):
        firsthalf = A[j]
        otherhalf = full - firsthalf
        if firsthalf in useA and otherhalf in useA:
            pairs += 1
            useA.remove(firsthalf)
            
            try:
                useA.remove(otherhalf)
            except:
                useA.append(firsthalf)
                pairs -= 1

print(pairs)

Submission status: Time Limit Exceeded

Solution code:
import bisect

import collections


n = int(input())
a = list(map(int, input().split()))
a_counter = collections.Counter(a)
a_keys = sorted(a_counter.keys(), reverse=True)

targets = []

t = 0
vt = 1
for v in a:
    while v >= vt:
        t += 1
        vt *= 2
        targets.append(vt)
targets.reverse()


cnt = 0
for key in a_keys:
    if a_counter[key] <= 0:
        continue
    for t in targets:
        if key == t-key:
            p = max(0, min(a_counter[key], a_counter[t-key])) // 2
        else:
            p = max(0, min(a_counter[key], a_counter[t-key]))
        a_counter[key] -= p
        a_counter[t-key] -= p
        cnt += p
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def powers_of_2(n):
    while True:
        if n%2 == 0:
            n = n/2
        else:
            return False
        if n == 1:
            return True

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

def pair(n, a, ans):
    list_ans = []
    for i in range(n-1):
        for j in range(i+1, n):
            if powers_of_2(a[i]+a[j]):
                _a = a[i+1:]
                _a.pop(j-i-1)
                list_ans.append(pair(n-i-2, _a, ans+1))
    return max(list_ans) if list_ans != [] else ans

print(pair(n, a, 0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

edges = [None for _ in range(n)]
for a, i_set 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
    for i in i_set:
        ts = tmp_set.copy()
        ts.discard(i)
        edges[i] = ts


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)) // 2)

Submission status: Time Limit Exceeded

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 j in range(i + 1, N):
        for k in range(30):
            if i != j and A[i] + A[j] == 2 ** k:
                G[i].append(N + j)
                G[j].append(N + i)
                break
            if A[i] + A[j] < 2 ** k:
                break

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: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

edges = [set() for _ in range(n)]
for i, a in enumerate(aaa):
    k = 2
    while k <= ma2:
        if k > a:
            b = k - a
            if b in rd:
                edges[i].update(j for j in rd[b] if i != j)
        k <<= 1


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)) // 2)

Submission status: Time Limit Exceeded

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 j in range(i + 1, N):
        for k in range(30):
            if i != j and A[i] + A[j] == 2 ** k:
                G[i].append(N + j)
                G[j].append(N + i)
                break
            if A[i] + A[j] < 2 ** k:
                break


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: Time Limit Exceeded

Solution code:
# B
N = int(input())
A_list = list(map(int, input().split()))

A_dict = dict()
for a in A_list:
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

res = 0
A_list_ = list(reversed(sorted(A_list)))
for a in A_list_:
    # partner
    r = 1
    while r < a:
        r *= 2
    if a == r:
        res += A_dict[a] // 2
        A_dict[a] = 0
    else:
        b = r - a
        if A_dict[a] > 0 and A_dict.get(b, 0) > 0:
            A_dict[a] -= 1
            A_dict[b] -= 1
            res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

H = defaultdict(lambda: [])
N = int(input())
A = inpl()
k = 2**30
ans = 0
for j in range(30,0,-1):
    k = 2**j
    t = []
    H = defaultdict(lambda: [])
    for i in A:
        if H[k-i]:
            t.append(H[k-i].pop())
            t.append(i)
            ans += 1
        else:
            H[i].append(i)
    for p in t:
        A.remove(p)
print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

dic = DD(int)
for a in A:
  dic[a] += 1
  
kieru = DD(int)

A.sort(reverse = True)

ans = 0
for a in A:
  if kieru[a]:
    kieru[a] -= 1
    continue
  dic[a] -= 1
  if a == (1<<(a.bit_length()-1)):
    if dic[a]:
      kieru[a] += 1
      dic[a] -= 1
      ans += 1
  else:
    b = (1<<a.bit_length()) - a
    if dic[b]:
      kieru[b] += 1
      dic[b] -= 1
      ans += 1
print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    alst = list(map(int, input().split()))
    alst.sort(reverse = True)
    max_a = alst[0]
    dd = defaultdict(int)
    for a in alst:
        dd[a] += 1
    i = 1
    while i <= max_a:
        i *= 2
    ans = 0
    for a in alst:
        if dd[a] <= 0:
            continue
        while i > a * 2:
            i /= 2
        dd[a] -= 1
        num = i - a
        if dd[num]:
            ans += 1
            dd[num] -= 1
    print(ans)
    
main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = sorted(in_nl())[::-1]

    a_cnt = Counter(A)

    ans = 0
    for i in range(N):
        if a_cnt[A[i]] == 0:
            continue
        pow_two = 2 ** A[i].bit_length()
        search = pow_two - A[i]
        a_cnt[A[i]] -= 1
        if a_cnt[search] >= 1:
            ans += 1
            a_cnt[search] -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    INF = 10**10
    N = NI()
    a = LI()
    a.sort()
    u = 2 ** 31
    ans = 0
    while u > 2:
        u /= 2
        j = N-1
        for i in range(N):
            if a[i] == INF: continue
            while j > i and a[i] + a[j] > u:
                j -= 1
            if j <= i: break
            if a[i] + a[j] == u:
                ans += 1
                a[i] = a[j] = INF

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
l = sorted(list(map(int,input().split())))
d = Counter(l)
ans = 0
for i in range(n-1,-1,-1):
    if d[l[i]] == 0:
        continue
    d[l[i]] -= 1
    x = 2**(l[i].bit_length())
    y = x-l[i]
    if d[y] > 0:
        d[y] -= 1
        ans += 1
            
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
res = 0
for x in reversed(A):
    y = (1 << x.bit_length()) - x
    if x == y:
        k = cnt[x]//2
    else:
        k = min(cnt[x], cnt[y])
    res += k
    cnt[x] -= k
    cnt[y] -= k

print(res)

Submission status: Accepted

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, 32)):
                target = 2**i
                if 2*v < target:
                    continue
                if target < v:
                    break
                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: Accepted

Solution code:
def main():
	from math import log,ceil
	n=int(input())
	a=list(map(int,input().split()))
	num={}
	for x in a:
		if x in num:
			num[x]+=1
		else:
			num[x]=1
	ans=0
	cnt=ceil(log(max(a),2)+1e-7)
	for i in range(cnt,0,-1):
		b=set(2**i-x for x in num)
		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)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def main():
	from math import log,ceil
	n=int(input())
	a=list(map(int,input().split()))
	num={}
	for x in a:
		if x in num:
			num[x]+=1
		else:
			num[x]=1
	ans=0
	cnt=ceil(log(max(a),2)+1e-9)+1

	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)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    MAX = A[-1] * 2
    D = Counter(A)
    res = 0
    for i in reversed(range(n)):
        if D[A[i]] == 0:
            continue
        target = 2
        while target <= MAX:
            if D.get(target - A[i], 0) != 0:
                if A[i] != target - A[i]:
                    D[A[i]] -= 1
                    D[target - A[i]] -= 1
                    res += 1
                    break
                else:
                    if D[A[i]] != 1:
                        D[A[i]] -= 2
                        res += 1
                        break
            target *= 2
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
A=sorted(map(int,input().split()),reverse=True)
c=Counter(A)
ans=0
for i in range(N):
    if c[A[i]]==0:
        continue
    c[A[i]]-=1
    k=1<<A[i].bit_length()
    v=k-A[i]
    if v in c and c[v]>0:
        ans+=1
        c[v]-=1
print(ans)