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:
# -*- 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 = deque([])

A.sort(reverse = True)

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

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
from collections import defaultdict

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 /= a
    dd[a] -= 1
    num = i - a
    if dd[num]:
        ans += 1
        dd[num] -= 1
print(ans)

Submission status: Wrong Answer

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())

    N = NI()
    r = collections.Counter()
    a = LI()
    for x in a:
        z = 2**(x.bit_length())-x
        r[z] += 1 + (z != x)
    ans = 0
    for x in a:
        if r[x] > 1:
            ans += 1
            r[x] -= 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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):
    c = cnt[x]
    if c == 0:
        continue
    y = (1 << x.bit_length()) - x
    if x == y:
        res += c//2
        cnt[y] = c%2
    else:
        k = min(c, cnt[y])
        res += k
        cnt[y] -= k

print(res)

Submission status: Wrong Answer

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):
    c = cnt[x]
    if c == 0:
        continue
    y = (1 << x.bit_length()) - x
    if x == y:
        res += c//2
    else:
        k = min(c, cnt[y])
        res += k
        cnt[y] -= k

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
P = [set() for _ in range(N)]
for i,a in enumerate(A):
    for k in range(1,31):
        P[i].add(2**k-a)
Q=[1]*N
res = 0
for i in range(N):
    if Q[i] == 0: continue
    for j in range(i+1,N):
        if Q[j]==1 and A[i] in P[j]:
            Q[j]=0
            res += 1
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
P = [set() for _ in range(N)]
for i,a in enumerate(A):
    for k in range(1,31):
        P[i].add(2**k-a)
Q=[1]*N
res = 0
for i in range(N):
    for j in range(i+1,N):
        if Q[j]==1 and A[i] in P[j]:
            Q[j]=0
            res += 1
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
P = [set() for _ in range(N)]
for i,a in enumerate(A):
    for k in range(1,31):
        P[i].add(2**k-a)
Q=[1]*N
res = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] in P[j] and Q[j]==1:
            Q[j]=0
            res += 1
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def adj(v):
    t = 1
    while t <= 2*10**9:
        if t > v:
            yield t-v
        t *= 2

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

cnt = defaultdict(int)
for a in A:
    cnt[a] += 1

degree = defaultdict(int)
for v in cnt.keys():
    for u in adj(v):
        if u == v:
            degree[v] += int(cnt.get(u,0) >= 2)
        else:
            degree[v] += int(cnt.get(u,0) >= 1)

stack = [v for v,c in degree.items() if c == 1]
res = 0
while stack:
    v = stack.pop()
    c = cnt.get(v,0)
    if c == 0:
        continue
    for u in adj(v):
        if u == v and c >= 2:
            res += c//2
            break
        elif u != v and cnt.get(u,0) >= 1:
            k = min(cnt[u],c)
            res += k
            cnt[u] -= k
            cnt[v] -= k
            degree[u] -= 1
            if degree[u] == 1:
                stack.append(u)
            break
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def adj(v):
    t = 1
    while t <= 2*10**9:
        if t > v:
            yield t-v
        t *= 2

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

cnt = defaultdict(int)
for a in A:
    cnt[a] += 1

degree = defaultdict(int)
for v in cnt.keys():
    for u in adj(v):
        if u == v:
            degree[v] += int(cnt.get(u,0) >= 2)
        else:
            degree[v] += int(cnt.get(u,0) >= 1)

stack = [v for v,c in degree.items() if c == 1]
res = 0
while stack:
    v = stack.pop()
    c = cnt.get(v,0)
    if c == 0:
        continue
    for u in adj(v):
        if u == v and cnt.get(u,0) >= 2:
            res += c//2
            break
        elif cnt.get(u,0) >= 1:
            k = min(cnt[u],c)
            res += k
            cnt[u] -= k
            degree[u] -= 1
            if degree[u] == 1:
                stack.append(u)
            break
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
P = []
for i in range(1,5):
    B = []
    cnt = 0
    for a in A:
        if not 2**i-a==a:
            B.append(2 ** i - a)
    P.append(Counter(B))
res = 0
for p in P:
    for a in A:
        if p.get(a,0):
            res += 1
            p[a] -= 1
            break
print(res)

Submission status: Wrong Answer

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={}
		f=0
		for x in a:
			if 2**i-x in b:
				b[2**i-x]+=1
			else:
				b[2**i-x]=1
		p=[]
		for x in num:
			if x in b:
				if x*2==2**i:
					ans+=num[x]*(num[x]-1)//2*2
					if num[x]*(num[x]-1)//2*2>0:
						p.append(x)
				else:
					ans+=num[x]*b[x]
					if num[x]*b[x]>0:
						p.append(x)
		for x in p:
			num[x]=0
	print(ans//2)
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from math import log,ceil
n=int(input())
a=list(map(int,input().split()))
pair=set()
cnt=ceil(log(max(a),2)+1e-9)+1
for i in range(cnt,0,-1):
	b=[]
	for x in a:
		if x!=2**i-x:
			b.append(2**i-x)
	r=set(b)&set(a)
	if len(r)>0:
		pair|=set(r)
print(len(pair)//2)

Submission status: Wrong Answer

Solution code:
from math import log,ceil
n=int(input())
a=list(map(int,input().split()))
pair=set()
cnt=ceil(log(max(a),2)+1e-9)+1
for i in range(cnt,0,-1):
	b=[]
	for x in a:
		if x!=2**i-x:
			b.append(2**i-x)
	r=set(b)&set(a)
	if len(r)>0:
		pair|=set(r)
print(len(pair)//2)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
left,right=0,N-1
cnt=0
D=[1]*N
for i in range(N):
  if D[-1-i]==1:
    D[-1-i]=0
    for j in range(1,16):
      d=2**j
      if A[-1-i]<d:
        e=d
        break
    le=bisect.bisect_left(A,d-A[-1-i])
    ri1=bisect.bisect_right(A,d-A[-1-i])
    ri2=bisect.bisect_right(A,A[-1-i])
    ri=min(ri1,ri2)
    if ri-le>0:
      for k in range(le,ri):
        if D[k]==1:
          D[k]=0
          cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def solve(A):
    A.sort()

    vals = []
    cnt = []
    last = -1
    for a in A:
        if a != last:
            vals.append(a)
            cnt.append(1)
        else:
            cnt[-1] += 1

    res = 0
    total = 1 << vals[-1].bit_length()
    k = len(vals)-1
    while total > 1:
        t = 0
        while k >= 0 and vals[k]*2 > total:
            while t <= k and vals[k]+vals[t] < total:
                t += 1
            if vals[k]+vals[t] == total:
                c = min(cnt[k],cnt[t])
                res += c
                cnt[k] -= c
                cnt[t] -= c
            k -= 1
        if k >= 0 and vals[k]*2 == total:
            res += cnt[k]//2
            cnt[k] %= 2
        total //= 2
    return res



if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    print(solve(A))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def solve(A):
    A.sort()

    vals = []
    cnt = []
    last = -1
    for a in A:
        if a != last:
            vals.append(a)
            cnt.append(1)
        else:
            cnt[-1] += 1

    M = vals[-1]

    res = 0

    for i in reversed(range(len(vals))):
        v,c = vals[i],cnt[i]

        n = 1 << v.bit_length()
        if n == v*2:
            res += c//2
            c %= 2

        while c:
            n *= 2
            if n <= v*2:
                continue

            j = bisect_left(vals,n-v,lo=i)
            if j >= len(vals):
                break
            if vals[j] == n-v:
                m = min(c,cnt[j])
                res += m
                c -= m
                cnt[j] -= m

        cnt[i] = c
    return res



if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    print(solve(A))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def solve(A):
    A.sort()

    vals = []
    cnt = []
    last = -1
    for a in A:
        if a != last:
            vals.append(a)
            cnt.append(1)
        else:
            cnt[-1] += 1

    M = vals[-1].bit_length() + 1

    res = 0
    for i,v,c in zip(reversed(range(len(vals))), reversed(vals), reversed(cnt)):
        for k in reversed(range(M)):
            n = 1 << k
            r = n-v
            if r >= v:
                continue

            j = bisect_left(vals,r,hi=i)
            if j < 0:
                continue
            if vals[j] != r:
                continue

            p = min(c,cnt[j])
            res += p
            c -= p
            cnt[j] -= p

    return res



if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    print(solve(A))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def solve(A):
    A.sort()

    vals = []
    cnt = []
    last = -1
    for a in A:
        if a != last:
            vals.append(a)
            cnt.append(1)
        else:
            cnt[-1] += 1

    M = vals[-1].bit_length() + 1

    res = 0
    for i,v,c in zip(reversed(range(len(vals))), reversed(vals), reversed(cnt)):
        for k in reversed(range(M)):
            n = 1 << k
            r = n-v
            if r >= v:
                continue

            j = bisect_left(vals,r,hi=i)
            if vals[j] != r:
                continue

            p = min(c,cnt[j])
            res += p
            c -= p
            cnt[j] -= p

    return res



if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    print(solve(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
B = []
pow = 1
for a in A:
    while pow <= a:
        pow *= 2
    B.append(pow-a)
B.reverse()
 
i = 0
j = 0
ans = 0

while i != N and j != N and i + j <= N - 2:
    if A[i] == B[j]:
        if i == N - j - 1:
            i += 1
        else:
            i += 1
            j += 1
            ans += 1
    else:
        j += 1
 
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
B = []
pow = 1
for a in A:
    while pow <= a:
        pow *= 2
    B.append(pow-a)
B.reverse()

i = 0
j = 0
ans = 0
while i != N and j != N:
    if A[i] == B[j]:
        if i == N - j - 1:
            i += 1
        else:
            i += 1
            j += 1
            ans += 1
    else:
        j += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
import bisect as bi
Q=deque(A)
rui=[pow(2,i) for i in range(31)]
ans=0
C=Counter(A)
N={ i:0 for i in C.keys() }
while Q:
    k=Q.pop()
    for r2 in rui:
        if r2>2*k:break
        if N.get(r2-k,None)==None:continue
        if r2-k==k: 
            if N[r2-k]+1>=C[r2-k]:continue
        if N[r2-k] >= C[r2-k]: continue
        N[r2-k]+=1;N[k]+=1;ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
import bisect as bi
Q=deque(A)
rui=[pow(2,i) for i in range(31)]
ans=0
C=Counter(A)
N={ i:0 for i in C.keys() }
while Q:
    k=Q.pop()
    for r2 in rui:
        if N.get(r2-k,None)==None:continue
        if N[r2-k] >= C[r2-k]: continue
        N[r2-k]+=1;N[k]+=1;ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
import bisect as bi
Q=deque(A)
rui=[pow(2,i) for i in range(31)]
ans=0
i=-1
while Q:
    k=Q.pop()
    for r2 in rui:
        tmp=bi.bisect_left(A[:i],r2-k)
        if tmp == n:i-=1;continue
        if A[tmp]==r2-k: ans+=1;break
        i-=1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
import bisect as bi
Q=deque(A)
rui=[pow(2,i) for i in range(31)]
ans=0
while Q:
    k=Q.pop()
    for r2 in rui:
        tmp=bi.bisect_left(A,r2-k)
        if tmp == n:continue
        if A[tmp]==r2-k: ans+=1;break

print(ans//2)

Submission status: Wrong Answer

Solution code:
import math

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

A.sort(reverse=True)

ans = 0
alr = set()
for i in range(N-1):
    if not i in alr:
        x = A[i]
        p = math.ceil(math.log2(x))
        for j in range(i+1, N):
            if x + A[j] == 2**p and not j in alr:
                ans += 1
                alr.add(j)
                break
            if x + A[j] < 2**p:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = set(int(x) for x in input().split())

ans = 0
while A:
    m = max(A)
    A.discard(m)
    t = m.bit_length()
    pair = 2**t - m
    if pair in A:
        A.discard(pair)
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = set(int(x) for x in input().split())

ans = 0
while A:
    m = max(A)
    A.remove(m)
    t = m.bit_length()
    pair = 2**t - m
    if pair in A:
        A.remove(pair)
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
jisho = defaultdict(int)
for a in A:
    jisho[a] += 1
A.sort()
ans = 0
for i in range(n - 1, -1, -1):
    num = A[i]
    jisho[num] -= 1
    temp = num // (num & -num)
    keta = temp.bit_length()
    kouho = 1
    for i in range(1, keta):
        if (temp >> i) & 1 == 0:
            kouho += 1 << i
    kouho *= num & -num
    if jisho[kouho] > 0:
        # print(num, kouho)
        jisho[kouho] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys

input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
A.sort()
used = [False] * (n)
ans = 0
for i in range(n - 1, -1, -1):
    used[i] = True
    num = A[i]
    temp = num // (num & -num)
    keta = temp.bit_length()
    kouho = 1
    for i in range(1, keta):
        if (temp >> i) & 1 == 0:
            kouho += 1 << i
    kouho *= num & -num
    pos = bisect_left(A, kouho)
    if used[pos]:
        continue
    if A[pos] == kouho:
        # print(num, A[pos])
        used[pos] = True
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = max(a)*2
from collections import Counter, defaultdict
c = Counter(a)
kvs = [(k,v) for k,v in c.items()]
kvs.sort(reverse=True)
c = {}
for k,v in kvs:
    c[k] = v
ans = 0
vs = []
i = 2
while True:
    if i<=m:
        vs.append(i)
        i *= 2
    else:
        break
vs = vs[::-1]
for k in c:
    for v in vs:
        if k<v and v-k in c and c[v-k]>0:
            if c[k]<=c[v-k]:
                ans += c[k]
                c[v-k] -= c[k]
                c[k] = 0
            else:
                ans += c[v-k]
                c[k] -= c[v-k]
                c[v-k] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = max(a)*2
from collections import Counter, defaultdict
c = Counter(a)
kvs = [(k,v) for k,v in c.items()]
kvs.sort(reverse=True)
c = {}
for k,v in kvs:
    c[k] = v
ans = 0
vs = []
i = 2
while True:
    if i<=m:
        vs.append(i)
        i *= 2
    else:
        break
vs = vs[::-1]
ds = defaultdict(int)
for k in c:
    for v in vs:
        if k<v and v-k in c:
            ds[k] += c[v-k]
kvs = [(v,k) for k,v in ds.items()]
kvs.sort()
for _,k in kvs:
    for v in vs:
        if k<v and v-k in c and c[v-k]>0:
            if c[k]<=c[v-k]:
                ans += c[k]
                c[v-k] -= c[k]
                c[k] = 0
            else:
                ans += c[v-k]
                c[k] -= c[v-k]
                c[v-k] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = max(a)*2
from collections import Counter
c = Counter(a)
kvs = [(k,v) for k,v in c.items()]
kvs.sort(reverse=True)
c = {}
for k,v in kvs:
    c[k] = v
ans = 0
vs = []
i = 2
while True:
    if i<=m:
        vs.append(i)
        i *= 2
    else:
        break
vs = vs[::-1]
for v in vs:
    for k in c.keys():
        if k<v and v-k in c and c[v-k]>0:
            if c[k]<=c[v-k]:
                ans += c[k]
                c[v-k] -= c[k]
                c[k] = 0
            else:
                ans += c[v-k]
                c[k] -= c[v-k]
                c[v-k] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = max(a)*2
from collections import Counter
c = Counter(a)
kvs = [(k,v) for k,v in c.items()]
kvs.sort(reverse=True)
c = {}
for k,v in kvs:
    c[k] = v
ans = 0
vs = []
i = 2
while True:
    if i<=m:
        vs.append(i)
        i *= 2
    else:
        break
vs = vs[::-1]
for k in c.keys():
    for v in vs:
        if k<v and v-k in c and c[v-k]>0:
            if c[k]<=c[v-k]:
                ans += c[k]
                c[v-k] -= c[k]
                c[k] = 0
            else:
                ans += c[v-k]
                c[k] -= c[v-k]
                c[v-k] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = max(a)*2
from collections import Counter
c = Counter(a)
kvs = [(k,v) for k,v in c.items()]
kvs.sort(reverse=True)
c = {}
for k,v in kvs:
    c[k] = v
ans = 0
vs = []
i = 2
while True:
    if i<=m:
        vs.append(i)
        i *= 2
    else:
        break
for k in c.keys():
    for v in vs:
        if k<v and v-k in c and c[v-k]>0:
            if c[k]<=c[v-k]:
                ans += c[k]
                c[v-k] -= c[k]
                c[k] = 0
            else:
                ans += c[v-k]
                c[k] -= c[v-k]
                c[v-k] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    ac = collections.Counter(A)
    num_pairs = 0
    for i in range(N - 1, -1, -1):
        x = A[i]
        if ac[x] == 0:
            continue
        p = 1
        while p <= x:
            p <<= 1
        j = bisect.bisect_left(A, p - x, 0, i)
        if j >= i:
            continue
        y = A[j]
        if x + y != p:
            continue
        if ac[y] <= 0:
            continue
        ac[x] -= 1
        ac[y] -= 1
        num_pairs += 1
    return num_pairs


print(solve())

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    ac = collections.Counter(A)
    num_pairs = 0
    for i in range(N - 1, -1, -1):
        x = A[i]
        if ac[x] == 0:
            continue
        p = 1
        while p < x:
            p <<= 1
        ac[x] -= 1
        j = bisect.bisect_left(A, p - x, 0, i)
        if j >= i:
            continue
        y = A[j]
        if x + y != p:
            continue
        if ac[y] <= 0:
            continue
        ac[y] -= 1
        num_pairs += 1
    return num_pairs


print(solve())

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    ac = collections.Counter(A)
    num_pairs = 0
    for i in range(N - 1, -1, -1):
        x = A[i]
        if ac[x] == 0:
            continue
        p = 1
        while p < x:
            p <<= 1
        ac[x] -= 1
        j = bisect.bisect_left(A, p - x, 0, i)
        y = A[j]
        if x + y != p:
            continue
        if ac[y] <= 0:
            continue
        ac[y] -= 1
        num_pairs += 1
    return num_pairs


print(solve())

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
set_A = set(A)
ans = 0
use = [False for _ in range(N)]
beki_list = [pow(2, i) for i in range(1, 32)]
for a in A:
    index = bisect_right(beki_list, a)
    if (beki_list[index] - a) in set_A:
        if (use[A.index(beki_list[index] - a)] == False) & (a  != beki_list[index] - a):
            ans += 1
            use[A.index(beki_list[index] - a)] = True
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
import math
set_A = set(A)
ans = 0
use = [False for _ in range(N)]
for a in A:
    if (pow(2, math.ceil(math.log(a, 2))) - a) in set_A:
        if use[A.index(pow(2, math.ceil(math.log(a, 2))) - a)] == False:
            ans += 1
            use[A.index(pow(2, math.ceil(math.log(a, 2))) - a)] = True
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = set([int(i) for i in input().split()])
ans = 0
while A:
    a = A.pop()
    for i in range(2, 32):
        if (pow(2, i) - a) in A:
            ans += 1
            print(pow(2, i), a)
print(ans)