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:
import bisect
import math


n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
kari=[]
ma=[]
m2=[]
n2=[]
vt=[]
vp=[]
visited=[]
ans=0
for i in range(n):
  kari=[]
  for j in range(20):
    if(2**j>a[i]):
      for k in range(bisect.bisect_left(a,2**j-a[i]),bisect.bisect_right(a,2**j-a[i])):
        if(k==i):
          continue
        kari.append(k)
      break
  ma.append(kari)
rev=[n-1-i for i in range(n)]
for i in rev:
  if(i in visited):
    continue
  for j in ma[i]:
    if(j in visited):
      continue
    ans+=1
    visited.append(i)
    visited.append(j)
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
a = list(map(int,input().split()))
a.sort()
 
b = 1
while b <= a[n-1]:
    b = b*2
 
c = [None]*n #使ったら1
 
res = 0
 
for i in range(n-1,-1,-1):
    if c[i] == None:
        
        while b > a[i]:
            b = b//2
        b = b*2
        w1 = bisect.bisect_left(a,b-a[i])
        w2 = bisect.bisect_right(a,b-a[i])
        if w2 >w1:
            for p in range(w1,w2):
                if c[p] == None and i != p:
                    res += 1
                    c[p] = 1
                    c[i] = 1
                    break
                
 
print(1)

Submission status: Wrong Answer

Solution code:
# cook your dish here
def bisect_left(a,x):
    s = 0
    t = n-1
    while t-s >= 2:
        m = (s+t)//2
        if a[m] < x:
            s = m
        else:
            t = m
    return s

def bisect_right(a,x):
    s = 0
    t = n-1
    while t-s >= 2:
        m = (s+t)//2
        if a[m] <= x:
            s = m
        else:
            t = m
    return t
            


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

c = [0]*n #使ったら1
 
res = 0
 
for i in range(n-1,-1,-1):
    if c[i] == 0:
        b = 1
        while b <= a[i]:
            b = b*2
        w1 = bisect_left(a,b-a[i])
        w2 = bisect_right(a,b-a[i])
        if w2 >w1:
            for p in range(w1,w2):
                if c[p] == 0 and i != p:
                    res += 1
                    c[p] = 1
                    c[i] = 1
                    break
                

print(res)

Submission status: Wrong Answer

Solution code:
import collections

N = input()
A = map(int, raw_input().split())
C = collections.Counter(A)
K = C.keys()
K.sort(reverse=1)
res = 0
for i in K:
    for j in xrange(31):
        p = 2 ** j
        if i > p:
            continue
        elif i == p:
            res += C[i] // 2
            C[i] = C[i] // 2 * 2
        else:
            num = min(C[i], C[p - i])
            res += num
            C[i] -= num
            C[p - i] -= num
print res

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
list_ = [2 ** i for i in range(30)]
A.sort(reverse=True)

ans = 0
while(len(A) > 0):
    a = A.pop()
    tmp = [i - a for i in list_ if i - a > 0]
    for b in tmp:
        i = bisect.bisect_left(A, b)
        if i < len(A) and A[i] == b:
            ans += 1
            A.pop(i)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

N = input()
A = map(int, raw_input().split())
A.sort(reverse=1)
c = collections.Counter(A)
res = 0
for i in A:
    for j in xrange(1, 31):
        p = 2 ** j
        if i > p:
            continue
        elif i == p:
            res += c[i] // 2
            c[i] = c[i] // 2 * 2
        else:
            num = min(c[i], c[p - i])
            res += num
            c[i] -= num
            c[p - i] -= num
print res

Submission status: Wrong Answer

Solution code:
import collections

N = input()
A = map(int, raw_input().split())
A.sort()
c = collections.Counter(A)
res = 0
for i in reversed(A):
    for j in range(1, 31):
        p = 2 ** j
        if i > p:
            continue
        elif i == p:
            res += c[i] // 2
            c[i] = c[i] // 2 * 2
        else:
            num = min(c[i], c[p - i])
            res += num
            c[i] -= num
            c[p - i] -= num
print res

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
Ae1=[]
Ao1=[]
for i in range(N):
    if A[i]%2==0:
        Ae1.append(A[i])
    else:
        Ao1.append(A[i])
if Ao1!=[]:
    s=0
    Ao=sorted(Ao1,reverse=True)
    i=0
    while i<=len(Ao)-1:
        a=int(math.log2(Ao[i]))
        try:
            Ao.pop(Ao.index(2**(a+1)-Ao[i]))
            s+=1
            i+=1
        except:
            i+=1
else:
    s=0
if Ae1!=[]:
    t=0
    Ae=sorted(Ae1,reverse=True)
    j=0
    while j<=len(Ae)-1:
        b=int(math.log2(Ae[j]))
        try:
            Ae.pop(Ae.index(2**(b+1)-Ae[j]))
            t+=1
            j+=1
        except:
            j+=1
else:
    t=0
print(s+t)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
list_ = [2 ** i for i in range(30)]
A.sort()

ans = 0
while(len(A) > 0):
    a = A.pop()
    tmp = [i - a for i in list_ if i - a > 0]
    for b in tmp:
        i = bisect.bisect_left(A, b)
        if i < len(A) and A[i] == b:
            ans += 1
            A.pop(i)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

ans = 0
flag = False
for i in range(n):
    if c[A[i]] == 0:
        continue

    pow_2 = 2 ** len(format(A[i], "b"))
    if c[pow_2 - A[i]] > 0 and pow_2 - A[i] != A[i]:
        c[pow_2 - A[i]] -= 1
        ans += 1
    elif c[pow_2 - A[i]] > 1 and pow_2 - A[i] == A[i]:
        if flag is True:
            c[A[i]] -= 2
            ans += 1
            flag = False
        else:
            flag = True

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

ans = 0
flag = False
for i in range(n):
    if c[A[i]] == 0:
        continue

    pow_2 = 2 ** len(format(A[i], "b"))
    if pow_2 - A[i] != A[i]:
        c[pow_2 - A[i]] -= 1
        ans += 1
    elif c[pow_2 - A[i]] > 1 and pow_2 - A[i] == A[i]:
        if flag is True:
            c[A[i]] -= 2
            ans += 1
            flag = False
        else:
            flag = True

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

ans = 0
for i in range(n):
    if c[A[i]] == 0:
        continue

    pow_2 = 2 ** len(format(A[i], "b"))
    if c[pow_2 - A[i]] != 0 and pow_2 - A[i] != A[i]:
        c[pow_2 - A[i]] -= 1
        ans += 1
    elif c[pow_2 - A[i]] > 1 and pow_2 - A[i] == A[i]:
        c[A[i]] -= 2
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

from collections import Counter

acnt = Counter(a)

ans = 0
temp = 0
for ai in sorted(a,reverse=True):
    pair = (1<<(ai.bit_length())) - ai
    
    if acnt[ai] > 0 and acnt[pair] > 0:
        if ai == pair:
            temp = (acnt[ai] // 2)
            ans += temp
            acnt[ai] -= temp
            
        elif ai > pair:
            temp = min(acnt[ai], acnt[pair])
            ans += temp
            acnt[ai] -= temp
            acnt[pair] -= temp
            
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

from collections import Counter

acnt = Counter(a)

ans = 0
for ai in sorted(a,reverse=True):
    pair = (1<<(ai.bit_length())) - ai
    
    if acnt[ai] > 0 and acnt[pair] > 0:
        if ai == pair:
            temp = (acnt[ai] // 2)
            
        elif ai > pair:
            temp = min(acnt[ai], acnt[pair])
        
        ans += temp
        acnt[pair] -= temp
            
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

from collections import Counter

acnt = Counter(a)

ans = 0
for ai in sorted(a,reverse=True):
    pair = (1<<(ai.bit_length())) - ai
    print(ai, pair)
    
    if acnt[ai] > 0 and acnt[pair] > 0:
        if ai == pair:
            temp = (acnt[ai] // 2)
            
        elif ai > pair:
            temp = min(acnt[ai], acnt[pair])
        
        ans += temp
        acnt[pair] -= temp
            
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

from collections import Counter

acnt = Counter(a)

ans = 0
for ai in sorted(a,reverse=True):
    pair = (1<<(ai.bit_length())) - ai
    
    if acnt[ai] > 0 and acnt[pair] > 0:
        if ai == pair:
            ans += (acnt[ai] // 2)
            
        elif ai > pair:
            temp = min(acnt[ai], acnt[pair])
            ans += temp
            acnt[pair] -= temp
            
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

from collections import Counter

acnt = Counter(a)
akey = set(acnt.keys())

ans = 0
for ai in sorted(a,reverse=True):
    pair = (1<<(ai.bit_length())) - ai
    
    if acnt[pair] > 0:
        if ai == pair:
            ans += (acnt[ai] // 2)
            
        else:
            temp = min(acnt[ai], acnt[pair])
            ans += temp
            acnt[pair] -= temp
            
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter
from bisect import bisect_right

bekis = [2**i for i in range(40)]

n = ni()
a = list(li())
acnt = Counter(a)
aset = set(a)

ans = 0
for ai in sorted(a,reverse=True):
    idx = bisect_right(bekis, ai)
    pair = bekis[idx] - ai
    
    if ai == pair:
        continue
    
    if acnt[ai]>0 and acnt[pair]>0:
        ans += 1
        acnt[ai] -= 1
        acnt[pair] -= 1
                
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter
from bisect import bisect_right

bekis = [2**i for i in range(40)]

n = ni()
a = list(li())
acnt = Counter(a)
aset = set(a)

ans = 0
for ai in sorted(a,reverse=True):
    idx = bisect_right(bekis, ai)
    pair = bekis[idx] - ai
    
    if acnt[ai]>0 and acnt[pair]>0:
        ans += 1
        acnt[ai] -= 1
        acnt[pair] -= 1
                
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)
dic={}
for a in A:
    dic[a]=dic.get(a,0)+1
print(dic)

ans=0

for a in A:
    small=(1<<(len(format(a,"b")))) -a
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a]-=1
        dic[small]-=1
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import copy
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1


pow2 = 1
while pow2 <= a[0]:
    pow2 *= 2
# print(a, pow2)
cnt = 0
for aa in a:
    while  aa < (pow2//2):
        pow2 //= 2
    
    v = aa
    rem = pow2 - aa
    # print(aa, pow2, v, rem)
    if (not v in b) or (not rem in b):
        continue

    if rem != v and (b[v] > 0 and b[rem] > 0):
        hit = min(b[v], b[rem])
        cnt += hit
        b[v] -= hit
        b[rem] -= hit
    elif rem == v and b[v] > 1:
        cnt += b[v]//2
        b[v] -= b[v]%2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2
#         d.append(c[n])
#     except:
#         pass
# d.sort(key=lambda x:len(x))
# d.reverse()

# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:
#             if p in j:
#                 try:
#                     d.pop(e+1)
#                 except:
#                     pass

# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1


# sum = 0
# for n in twopowerlist:
#     try:
#         sum += c[n]
#     except:
#         pass
# print("list: ", c)
# print(sum)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import copy
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1


pow2 = 1
while pow2 <= a[0]:
    pow2 *= 2

cnt = 0
for aa in a:
    while  aa < (pow2//2):
        pow2 //= 2
    v = aa
    rem = pow2 - aa
    if (not v in b) or (not rem in b):
        continue

    if rem != v and (b[v] > 0 and b[rem] > 0):
        # hit = min(b[v], b[rem])
        cnt += 1
        b[v] -= 1
        b[rem] -= 1
    else:
        cnt += 1
        b[v] -= 2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2
#         d.append(c[n])
#     except:
#         pass
# d.sort(key=lambda x:len(x))
# d.reverse()

# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:
#             if p in j:
#                 try:
#                     d.pop(e+1)
#                 except:
#                     pass

# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1


# sum = 0
# for n in twopowerlist:
#     try:
#         sum += c[n]
#     except:
#         pass
# print("list: ", c)
# print(sum)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import copy
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1


pow2 = 1
while pow2 <= a[0]:
    pow2 *= 2

cnt = 0
for aa in a:
    while  aa < (pow2//2):
        pow2 //= 2
    v = aa
    rem = pow2 - aa
    if (not v in b) or (not rem in b):
        continue

    if rem != v:
        hit = min(b[v], b[rem])
        cnt += hit
        b[v] -= hit
        b[rem] -= hit
    else:
        cnt += b[v]//2
        b[v] -= b[v]%2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2
#         d.append(c[n])
#     except:
#         pass
# d.sort(key=lambda x:len(x))
# d.reverse()

# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:
#             if p in j:
#                 try:
#                     d.pop(e+1)
#                 except:
#                     pass

# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1


# sum = 0
# for n in twopowerlist:
#     try:
#         sum += c[n]
#     except:
#         pass
# print("list: ", c)
# print(sum)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import copy
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1


pow2 = 1
while pow2 <= a[0]:
    pow2 *= 2

cnt = 0
for aa in a:
    while not aa >= (pow2//2):
        pow2 //= 2
    v = aa
    rem = pow2 - aa
    if (not v in b) or (not rem in b):
        continue

    if rem != v:
        hit = min(b[v], b[rem])
        cnt += hit
        b[v] -= hit
        b[rem] -= hit
    else:
        hit = b[v] // 2
        cnt += int(hit)
        b[v] -= b[v]%2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2
#         d.append(c[n])
#     except:
#         pass
# d.sort(key=lambda x:len(x))
# d.reverse()

# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:
#             if p in j:
#                 try:
#                     d.pop(e+1)
#                 except:
#                     pass

# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1


# sum = 0
# for n in twopowerlist:
#     try:
#         sum += c[n]
#     except:
#         pass
# print("list: ", c)
# print(sum)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        num = nums[cur]
        if nums_cnt[num] <= 0:
            continue

        power_of_2 = 1 << math.ceil(math.log2(num))

        pair = power_of_2 - num


        if pair != 0 and nums_cnt[pair] > 0:
            nums_cnt[pair] -= 1
            nums_cnt[num] -= 1
            cnt += 1
        elif pair == 0 and nums_cnt[pair] >= 2:
            nums_cnt[num] -= 2
            cnt += 1


        '''
        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            #print('continue',pair, idx)
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums, used)
        '''

        #print(nums_cnt)

    print(cnt)

    return

main()

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()
    used = [False] * n

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        num = nums[cur]
        if nums_cnt[num] == 0:
            continue

        power_of_2 = 1 << math.ceil(math.log2(num))

        pair = power_of_2 - num

        if nums_cnt[pair] != 0:
            nums_cnt[pair] -= 1
            nums_cnt[num] -= 1
            cnt += 1


        '''
        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            #print('continue',pair, idx)
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums, used)
        '''

    print(cnt)

    return

main()

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()
    used = [False] * n

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        num = nums[cur]
        power_of_2 = 1 << math.ceil(math.log2(num))

        pair = power_of_2 - num

        if nums_cnt[pair] != 0:
            nums_cnt[pair] -= 1
            nums_cnt[num] -= 1
            cnt += 1


        '''
        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            #print('continue',pair, idx)
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums, used)
        '''

    print(cnt)

    return

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for t in reversed(range(1, 31)):
    for i in reversed(range(n)):
        if memo[a[i]] == 0:
            continue
        if memo[(1 << t) - a[i]] == 0:
            continue
        memo[a[i]] -= 1
        memo[(1 << t) - a[i]] -= 1
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import bisect
import math
from collections import defaultdict

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()
    used = [False] * n

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        if used[cur]:
            continue
        num = nums[cur]
        power_of_2 = 1 << math.ceil(math.log2(num))

        pair = power_of_2 - num

        if nums_cnt[pair] != 0:
            nums_cnt[pair] -= 1
            cnt += 1


        '''
        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            #print('continue',pair, idx)
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums, used)
        '''

    print(cnt)

    return

main()

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()
    used = [False] * n
    
    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        if used[cur]:
            continue
        num = nums[cur]
        power_of_2 = 1 << len("{:b}".format(num))

        pair = power_of_2 - num

        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            #print('continue',pair, idx)
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums, used)

    print(cnt)

    return

main()

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict

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

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

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

print(count)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict

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

a.sort()
memo = defaultdict(int)

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

print(count)

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()
    used = [False] * n

    #print(n)
    #print(nums)

    num_bin_digits = [1 << len("{:b}".format(x)) for x in nums]
    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        if used[cur]:
            continue
        num = nums[cur]
        power_of_2 = num_bin_digits[cur]
        pair = power_of_2 - num

        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            #print('continue',pair, idx)
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums, used)

    print(cnt)

    return

main()