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 collections import defaultdict

def get_smallest_power_of_2_over_N(N):
    return 2**N.bit_length()

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


A = sorted(A)

ans=0
D=defaultdict(int)

for a in A:
    D[a]+=1

for i in reversed(range(N)):
    if D[A[i]]<=0:
        continue
    else:
        pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
        if D[pair_val]>0:
            ans+=1
            D[pair_val]-=1
            D[A[i]]-=1
        elif pair_val==A[i] and D[pair_val]>1:
            ans+=1
            D[pair_val]-=1
            D[A[i]]-=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def get_smallest_power_of_2_over_N(N):
    i=2
    while i<N:
        i*=2
    return i

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


A = sorted(A)

ans=0
D=defaultdict(int)

for a in A:
    D[a]+=1

for i in reversed(range(N)):
    if D[A[i]]<=0:
        continue
    else:
        pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
        if D[pair_val]>0:
            ans+=1
            D[pair_val]-=1
        D[A[i]]-=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import log2,ceil

def get_smallest_power_of_2_over_N(N):
    i=2
    while i<N:
        i*=2
    return i

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


pair_cand=[set() for _ in range(N)]
A = sorted(A)

ans=0
D=defaultdict(int)

for a in A:
    D[a]+=1

for i in reversed(range(N)):
    if D[A[i]]<=0:
        continue
    else:
        pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
        if D[pair_val]>0:
            ans+=1
            D[pair_val]-=1
            D[A[i]]-=1


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import log2,ceil

def get_smallest_power_of_2_over_N(N):
    return 2**(ceil(log2(N)))

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


pair_cand=[set() for _ in range(N)]
A = sorted(A)

ans=0
D=defaultdict(int)

for a in A:
    D[a]+=1

for i in reversed(range(N)):
    if D[A[i]]<=0:
        continue
    else:
        pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
        if D[pair_val]>0:
            ans+=1
            D[pair_val]-=1
            D[A[i]]-=1


print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
from math import log2,ceil

def get_smallest_power_of_2_over_N(N):
    return 2**(ceil(log2(N)))

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


pair_cand=[set() for _ in range(N)]
A = sorted(A)

ans=0
D=defaultdict(int)

for a in A:
    D[a]+=1

for i in reversed(range(N)):
    if D[A[i]]==0:
        continue
    else:
        pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
        if D[pair_val]!=0:
            ans+=1
            D[pair_val]-=1
            D[A[i]]-=1


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
cnt = Counter(A)
A = sorted(A, reverse=True)
ans = 0
for a in A:
    if a & (a - 1) != 0:
        cand = (1 << ((a - 1).bit_length()))
        if cnt[a] == 0 or cnt[cand] == 0: continue
    else:
        cand = a
        if cnt[a] < 2: continue
    ans += 1
    cnt[a] -= 1; cnt[cand] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
cnt = Counter(A)
A = sorted(A, reverse=True)
ans = 0
for a in A:
    cand = (1 << ((a - 1).bit_length())) - a
    if cnt[a] == 0 or cnt[cand] == 0: continue
    ans += 1
    cnt[a] -= 1; cnt[cand] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import heapq
import bisect

n = ni()
a = na()
ls = []
nibeki = [2**i for i in range(1,31)]

for i in a:
    heapq.heappush(ls,-i)

s = {}
ans = 0

for _ in range(n):
    m = -heapq.heappop(ls)
    if m in s and s[m] > 0:
        s[m] -= 1
        ans += 1
        continue
    b = bisect.bisect_right(nibeki,m)
    dif = 0 if b > 0 and nibeki[b-1] == m else nibeki[b]-m
    if dif in s:
        s[dif] += 1
    else:
        s[dif] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import heapq
import bisect

n = ni()
a = na()
ls = []
nibeki = [2**i for i in range(1,31)]

for i in a:
    heapq.heappush(ls,-i)

s = set()
ans = 0

for _ in range(n):
    m = -heapq.heappop(ls)
    if m in s:
        s.discard(m)
        ans += 1
        continue
    b = bisect.bisect_right(nibeki,m)
    dif = 0 if b > 0 and nibeki[b-1] == m else nibeki[b]-m
    s.add(dif)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import heapq
import bisect

n = ni()
a = na()
ls = []
nibeki = [2**i for i in range(1,31)]

for i in a:
    heapq.heappush(ls,-i)

s = set()
ans = 0

for i in range(n):
    m = -heapq.heappop(ls)
    if m in s:
        s.discard(m)
        ans += 1
        continue
    dif = nibeki[bisect.bisect_right(nibeki,m)]-m
    s.add(dif)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

blist=[]
for a in alist:
  a2=a
  digit_a2=0
  while(a2>0):
    a2>>=1
    digit_a2+=1
  b=2**(digit_a2)-a
  blist.append(b)
#print(alist)
#print(blist)

dic_a={}
for a in alist:
  if a in dic_a:
    dic_a[a]+=1
  else:
    dic_a[a]=1

answer=0
for i in range(N):
  a=alist[i]
  b=blist[i]
  if a==b:
    if dic_a[a]>1:
      dic_a[a]-=2
      answer+=1
      #print(a,a)
  else:
    if b in dic_a and dic_a[b]>0:
      dic_a[a]-=1
      dic_a[b]-=1
      answer+=1
      #print(a,b)
    
print(answer)

Submission status: Wrong Answer

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

cand_list=[]
for i in range(1,N):
  a=a2=alist[i]
  digit_a2=0
  while(a2>0):
    a2>>=1
    digit_a2+=1  
  b=2**(digit_a2)-a
  #print(a,b)
  
  x=bisect.bisect_left(alist,b,hi=i-1)
  if alist[x]==b:
    #print(a,alist[x])
    cand_list.append((a,alist[x]))

cand_list.sort(reverse=True)
#print(cand_list)
dic_a={}
for a in alist:
  if a in dic_a:
    dic_a[a]+=1
  else:
    dic_a[a]=1

answer_set=set()
for i,j in cand_list:
  if dic_a[i]>0 and dic_a[j]>0:
    answer_set.add((i,j))
    dic_a[i]-=1
    dic_a[j]-=1
    
#print(answer_set)
print(len(answer_set))

Submission status: Wrong Answer

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

cand_list=[]
for i in range(1,N):
  a=a2=alist[i]
  digit_a2=0
  while(a2>0):
    a2>>=1
    digit_a2+=1  
  b=2**(digit_a2)-a
  #print(a,b)
  
  x=bisect.bisect_left(alist,b,hi=i-1)
  if alist[x]==b:
    #print(a,alist[x])
    cand_list.append((a,alist[x]))

cand_list.sort(reverse=True)
#print(cand_list)

answer_set=set()
used_set=set()
for i,j in cand_list:
  if (not i in used_set) and (not j in used_set):
    answer_set.add((i,j))
    used_set.add(i)
    used_set.add(j)
    
#print(answer_set)
print(len(answer_set))

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
A = list(map(int,input().split()))
A.sort()
used = [False]*n
ans = 0
for i in range(n-1,-1,-1):
    temp = A[i]
    beki = 1
    while beki <= temp:
        beki *= 2
    counterpart = beki-temp
    k = bisect.bisect_right(A,counterpart)
    cur = k-1
    while A[cur] == counterpart:
        if used[cur] == False and used[i] == False and cur != i:
            used[cur] = True
            used[i] = True
            ans += 1
            break
        else:
            cur -= 1
            if cur == 0:
                break
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from bisect import *
N = int(input())
A = list(map(int, input().split()))
A.sort()
s = set()
ans = 0
for i in range(N):
    if N-i-1 in s:
        continue
    a = A[N-i-1]
    for j in range(32):
        if a&(1<<(31-j)):
            b = 1<<(32-j)
            break
    k = bisect_left(A[:N-i-1], b-a)
    if k < N-i-1 and b-a == A[k]:
        s.add(k)
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

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

for i in range(0,N):
    a=ord(2,A[i])
    A[i]=(a,A[i]//(2**a))

A.sort()


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

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

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

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

for i in range(0,N):
    a=ord(2,A[i])
    A[i]=(a,A[i]//(2**a))

A.sort()


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

data=defaultdict(int)
for i in range(len(q)):
    data[-q[i]]+=1
while q:
    x=-heapq.heappop(q)
    if data[x]==0:
        continue
    else:
        data[x]-=1
        y=2**(len(bin(x))-2)-x
        if data[y]!=0:
            data[y]-=1
            count+=1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

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

for i in range(0,N):
    a=ord(2,A[i])
    A[i]=(a,A[i]//(2**a))

A.sort()


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

data=defaultdict(int)
for i in range(len(q)):
    data[-q[i]]+=1
while q:
    x=-heapq.heappop(q)
    if data[x]==0:
        continue
    else:
        data[x]-=1
        y=2**(len(bin(x))-2)-x
        if data[y]!=0:
            data[x]-=1
            data[y]-=1
            count+=1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

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

for i in range(0,N):
    a=ord(2,A[i])
    A[i]=(a,A[i]//(2**a))

A.sort()


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

data=defaultdict(int)
for i in range(len(q)):
    data[-q[i]]+=1
while q:
    x=-heapq.heappop(q)
    if data[x]==0:
        continue
    else:
        y=2**(len(bin(x))-2)-x
        if data[y]==0:
            data[x]-=1
        else:
            data[x]-=1
            data[y]-=1
            count+=1

print(count)

Submission status: Wrong Answer

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

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

    print(ans)

    return


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

Submission status: Wrong Answer

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

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

    print(ans)

    return


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

Submission status: Wrong Answer

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

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

    print(ans)

    return


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

for a in As:
    n = 0
    d[a] -= 1
    while 2**n <= a:
        n += 1
    p = 2**n - a
    # print(a,p,d[p]) 
    if d[p] > 0:
        cnt += 1
        d[p] -= 1

print(cnt)

Submission status: Wrong Answer

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

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

for a in As:
    n = 0
    while 2**n <= a:
        n += 1
    p = 2**n - a
    # print(a,p,d[p]) 
    if d[p] > 0:
        cnt += 1
        d[p] -= 1
    d[a] -= 1

print(cnt)

Submission status: Wrong Answer

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

N = int(input())
As = sorted(list(map(int, input().split())),reverse=True)
d = defaultdict(int)
for a in As:
    d[a] += 1
cnt = 0
for a in As:
    n = 0
    while 2**n < a:
        n += 1
    p = 2**n - a 
    if d[p] > 0:
        d[p] -= 1
        cnt += 1
    d[a] -= 1
print(cnt)

Submission status: Wrong Answer

Solution code:
## 二部マッチング問題

import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)


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

from bisect import bisect_left
# print(As)
n = 0
while 2**n < 10**9:
    n += 1

# 二部グラフを作る
edges = defaultdict(list)

for x,a in enumerate(As):
    for i in range(n):
        ind = bisect_left(As,2**i-a)
        if ind == N or x >= ind:continue
        if 2**i-a == As[ind] :
            # print(x,ind)
            edges[x].append(ind)

def dfs(v, visited):
    """
    :param v: x側のマッチングしていない頂点
    :param visited: すでに探索した点かどうか判断
    :return: 増大路が見つかればTrue
    """
    next_vs = edges[v]
    # print(v,next_vs)
    for next_v in next_vs:
        if visited[next_v]:
            continue
        visited[next_v] = True
        # 増大路の交代を行っている
        # 新しい終点を発見するとTrueを返す
        # すでにmatchingされているならば、そこからさかのぼって増大路があるか検索
        if matched[next_v] == -1 or dfs(matched[next_v],visited):
            matched[next_v] = v
            return True
    return False


matched = [-1] * N
ans = 0
for i in range(N):
    ans += dfs(i, [False for i in range(N)])
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input());A=sorted(list(map(int,input().split())),reverse=True)
D={}
for a in A:
  if(str(a) in A):
    D[str(a)]+=1
  else:
    D[str(a)]=1
ans=0;p=2**64-1;
for i in range(len(A)):
  if(str(A[i]) in D and D[str(A[i])]>0):
    while(p//2>=A[i]):
      p//=2;
    x=(~(A[i]-1))&p
    if((str(x) in D and D[str(x)]>0) and (x!=A[i] or D[str(x)]>1)):
      ans+=1
      D[str(x)]-=1;D[str(A[i])]-=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input());A=sorted(list(map(int,input().split())),reverse=True)
D={}
for a in A:
  if(str(a) in A):
    D[str(a)]+=1
  else:
    D[str(a)]=1
ans=0;p=2**32-1;
for i in range(len(A)):
  if(str(A[i]) in D):
    while(p//2>=A[i]):
      p//=2;
    x=(~(A[i]-1))&p
    if((str(x) in D) and (x!=A[i] or D[str(x)]>1)):
      ans+=1
      D[str(x)]-=1;D[str(A[i])]-=1
      if(D[str(x)]==0):
        D.pop(str(x))
      if(D[str(A[i])]==0):
        D.pop(str(A[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

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

ans = 0
visited = [False]*n

while a:
    s = a.pop()
    if visited.pop():
        continue
    if s == -1:
        a.append(s)
        break
    m = 1
    while m <= s:
        m *= 2
    ind = bisect_right(a, m-s)
    if ind == 0:
        continue
    if a[ind-1] == m-s and not visited[ind-1]:
        visited[ind-1] = True
        ans += 1
    elif a[ind-1] == m-s and visited[ind-1]:
        j = 0
        while visited[ind-1-j] and ind-1-j > 1:
            j += 1
        if a[ind-1-j] == m-s:
            visited[ind-1-j] = True
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

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

while a:
    s = a.pop()
    if s == -1:
        a.append(s)
        break
    m = 1
    while m <= s:
        m *= 2
    ind = bisect_right(a, m-s)
    if ind == 0:
        continue
    if a[ind-1] == m-s:
        a[ind-1] = -1


print(-sum(a))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))

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

A.sort(reverse=~True)

ans = 0
for a in A:
    for j in range(32):
        t = 2**j - a
        if t in d:
            if t == a:
                if d[a] >= 2:
                    ans += 1
                    d[a] -= 1
                    break
            else:
                if d[a] >= 1:
                    ans += 1
                    d[a] -= 1
                    break
ans = ans//2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))

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

A.sort(reverse=~True)

ans = 0
for a in A:
    for j in range(32):
        t = 2**j - a
        if t in d:
            if t == a:
                if d[a] != 1:
                    ans += 1
                    break
            else:
                ans += 1
                break
ans = ans//2
print(ans)

Submission status: Wrong Answer

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)
    bi = [2**i for i in range(1, 31)]

    for b in A:
        if c[b] == 0:
            continue
        a = (bi[bisect(bi, b)]) - b
        if a == b:
            ans += c[b]//2
        else:
            if a in c.keys():
                ans += min(c[a], c[b])
                c[a] -= min(c[a], c[b])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

    for b in A:
        a = (1 << b.bit_length()) - b
        if a == b:
            ans += c[b]//2
        else:
            if a in c.keys():
                ans += min(c[a], c[b])
                c[a] -= min(c[a], c[b])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    from bisect import bisect

    _ = int(input())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    c = Counter(A)
    bi = [2**i for i in range(1, 31)]
    ans = 0

    for b in A:
        a = bi[bisect(bi, b)] - b
        if a == b:
            ans += c[b]//2
        else:
            if a in c.keys():
                ans += min(c[a], c[b])
                c[a] -= min(c[a], c[b])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort()

d = {}
ans = 0
for i in range(n):
    a = A[i]
    for j in range(32):
        t = 2**j - a
        if t in d:
            if d[t] == 0:
                continue
            else:
                ans += 1
                d[t] -= 1
                break
    else:
        if a not in d:
            d[a] = 1
        else:
            d[a] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort()

d = {}
ans = 0
for i in range(n):
    a = A[i]
    for j in range(32):
        t = 2**j - a
        if t in d:
            if d[t] == 0:
                continue
            else:
                ans += 1
                d[t] -= 1
    else:
        if a not in d:
            d[a] = 1
        else:
            d[a] += 1
print(ans)

Submission status: Wrong Answer

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

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

if __name__ == '__main__':
    main()